By Josh Feldman
During the dog days of summer, someone saw me struggling while running in the excessive heat and humidity that frequently blankets the Midwest, and asked me why I bother running during the hottest months of the year. I told him that even though there aren’t any major races during the summer, you will see lots of people training for the big races in autumn. Running is a yearlong sport; there is no offseason. If you aren’t running, you’re falling behind—your opponents are out there putting in the grueling miles.
That is why lots of fellow runners here in Columbia, Mo., ran in unrelenting heat, in weather better suited for sipping lemonade than for extreme physical exertion. But now that fall has arrived, everyone gets to see their fruits of their summer labor rewarded. Yes, cross country season is back! And with the state high school cross country meet moving to our fair city for the first time this year, even more people than normal have caught cross country fever here in the heartland.
So it wasn’t surprising to see huge crowds of spectators on hand for the annual cross country meet between the three public schools in the area. With glorious conditions, fall foliage, and three of the fastest teams in the state, everyone in the city seemed to congregate at the local cross country course for the most important tri-meet of the season. And when people watch the great sport of cross country, you know that the local bookies will be there as well, as betting and racing go hand in hand.
While last year the girl’s race took center stage, this year all eyes were on the boy’s race. For those who forgot, cross country team scoring is unique in that only the place of the runner matters. Each team has seven runners, and so in a tri-meet, each runner gets an ordinal finish between 1st and 21st place. The sum of the best five scoring places count as your team’s score; lowest score wins. In case there’s a tie between teams, the fastest 6th-place runner breaks the deadlock. The best score possible is 15 points for a team that has runners crossing the finish line in 1st through 5th place (1+2+3+4+5=15).
Notice that while only five runners “score” for a team, the sixth and seventh runners can worsen the score of the opposition if they finish ahead of enough runners. The great thing about cross country is that every runner matters, not just the runner who finishes first. Plenty of races have been decided by the sixth and seventh teammates.
With three truly stacked teams, I had no idea who would win the boys varsity race. So I asked my bookmaking friend Chef for his opinion. Chef told me that this race was the easiest race to book in his lifetime, as all 21 runners toeing the starting line were equally good. Literally anyone could win the whole thing, and anyone could come in dead freaking last. Even Chef knew that meant that each team had a one-in-three chance of coming home with the first-place trophy. Happy with the answer, I thanked him and made my way to get a good spot for the start of the race.
With less than five minutes to go before the start of the race, there was suddenly a lot of confusion near the starting line as one team looked downright distraught. I asked the person next to me what was going on. She said that one of the runners just got disqualified for a uniform violation; it seemed that the guy’s shirt didn’t quite match those of his teammates. As it was too late to make a substitution, this meant that one team would be competing with six runners instead of seven.
Fair to say, I have never seen so much chaos at a cross country meet in my life! And further, I never had seen Chef exert so much energy trying to sprint toward me. When an out-of-breath Chef finally caught up to me, he said, “I need your help! Now that one of the teams has only six runners, what are the new probabilities of each team winning the meet? I need to know—lots of people want to place a last-second wager!”
I told Chef that while I was in no mood to do his work for him, I am sure that many of my puzzle-reading friends would help him out.
Assuming that two squads have seven runners and one team has six runners, what is the probability of each team winning the meet?
How do the probabilities change if the short-handed team has an additional runner disqualified before the meet, so that team runs with five runners while the other two teams have a full complement of seven? Note that this team will lose any tie-breakers because it doesn’t have a 6th runner.
Solutions to Last Issue’s Puzzle, Snakes, Caterpillars, and Other Critters
The problem was stated in terms of numbering parts of animals so as to disguise it and minimize Google research. In fact, what you were asked to do was to “gracefully label” certain graphs. A graph with n edges has no more than n+1 vertices. Such a graph is called gracefully labeled if the vertices of the graph can be assigned distinct numbers (labels) from some subset of {0, 1, 2, …, n} such that the set of “induced edge” labels is equal to {1, 2, …, n}. The induced edge labels are the absolute differences of an edge’s two vertex labels. Because there are n edges, the induced edge labels must be distinct.
Not every graph can be gracefully labeled.1 But there is an open conjecture that all trees (connected graphs with no circuits) can be gracefully labeled. That conjecture has been shown true for large classes of trees. Diagrams 1, 2, and 3 showed trees that can be gracefully labeled; your problem was to provide those labelings.
For Diagram 1, 12 of the 14 submitted solutions followed the example of Diagram A, in the original statement of the problem with A=0, B=19, C=1, D=18, etc. The other two submitted solutions were: A=19, B=0, C=18, D=1, etc. They are dual solutions in the sense that the label of each vertex of the second solution is 19 minus the label of the corresponding vertex of the first solution. Two more solutions can be found by flipping the order of the labels of the two solutions already described. There are more solutions; I just don’t know how many.
As far as I can tell, all solvers used trial and error to solve the problems. For all three problems, there are certain constraints. Each solution must contain exactly one of the following four related sequences 0-19-1, 19-0-18, 1-19-0, 18-0-19. Clive Keatinge pointed out that solving mod 2 provides further constraints. Some tried to use a computer to generate and check all possible labelings but because there are 20! of them, that could take millions of years to complete. Even considering symmetries doesn’t shorten the time enough to be reasonable. What does seem to work is to guess at about half of the labeling—more if working by hand—and then begin enumerating possibilities. Fortunately, there seem to be a lot of solutions, so one is likely to bump into one in a reasonable length of time. Some solvers suggested starting out by picking vertex labels that induce large edge labels. Yan Fridman claimed that his solution to Diagram 3 was an easy rearrangement of his solution to Diagram 2, but that Diagram 2 was hard. Most solvers found Problem 3 harder than Problem 2.
For Diagram 2, 10 of the 14 solutions were either A=0, B=19, I=1, J=2, C=3, K=18, L=17, etc., its dual, or their flips. This is the solution contained in the literature for finding a graceful labeling for any caterpillar.2 Of the submitted solutions, three made the body of the caterpillar look like a solution to Diagram 1—A=0, B=19, C=1, D=18, etc.—then attached legs as needed. ,
For Diagram 3, none of the 11 solutions was similar to another, taking into account 71,628 symmetries. Clive suggested that E minus J has to be even, and evidence from the submissions supports that. Here is the solution that Yan claimed was easy: A=1, B=19, C=4, D=16, E=0, F=5, G=17, H=3, I=18, J=10, K=9, L=11, M=12, N=15, O=6, P=14, Q=8, R=13, S=13, T=2. Notice that all the triplets here are the same as the triplets in the first solution for Diagram 2.
Endnotes
[1] Consider two triangles connected at one vertex. Of course, this graph is not a tree.
[2] An Extensive Survey of Graceful Trees, Elina Robeva, Undergraduate Honors Thesis, Stanford University, June 1, 2011, (Downloaded from the Internet July 4, 2018)
