In this post I’ll talk about another favorite recreational math puzzle, the (in)famous “Pentagon Problem”.  First, though, I wanted to provide a solution to the Ghost Bugs problem from my last blog post.  The puzzle is the following:

You are given four lines in a plane in general position (no two parallel, no three intersecting in a common point). On each line a ghost bug crawls at some constant velocity (possibly different for each bug). Being ghosts, if two bugs happen to cross paths they just continue crawling through each other uninterrupted.  Suppose that five of the possible six meetings actually happen. Prove that the sixth does as well.

Here is the promised solution.  The idea (like in Einstein’s theory of general relativity) is to add an extra dimension corresponding to time.  We thus lift the problem out of the page and replace the four lines by the graph of the bugs’ positions as a function of time.  Since each bug travels at a constant speed, each of the four resulting graphs is a straight line.  By construction, two lines and intersect if and only if the corresponding bugs cross paths.

Suppose that every pair of bugs cross paths except possibly for bugs 3 and 4.  Then the lines each intersect one another (in distinct points) and therefore they lie in a common plane.  Since line intersects lines and in distinct points, it must lie in the same plane.  The line cannot be parallel to , since their projections to the page (corresponding to forgetting the time dimension) intersect.  Thus and must intersect, which means that bugs 3 and 4 do indeed cross paths.

Cool, huh?  As I mentioned in my last post, I can still vividly remember how I felt in the AHA! moment when I discovered this solution more than 15 years ago.

Here is another favorite problem.  It appeared in the 1986 International Math Olympiad in Warsaw, Poland and subsequently became known as “the Pentagon Problem”.

To each vertex of a regular pentagon an integer is assigned, so that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers respectively, and is negative, you may replace by , respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to an end after a finite number of steps. There are many different solutions to this problem (the answer to which is yes).  Most involve coming up with a “monovariant” (a quantity which is bounded below and decreases each time a legal operation is performed) out of thin air.  For example, one can check that has this property.  This was the argument found by all but one of the eleven people who solved the problem on the IMO (according to this paper).  One disadvantage of this solution is that it does not generalize to arbitrary n-gons (though the problem itself does).  Joseph G. Keane of the US team won a special prize at the competition for his ‘dissenting’ solution which does generalize to n-gons.  Keane’s solution is to instead look at the monovariant

where the indices are considered modulo 5.

A couple of years ago my former Ph.D. student Farbod Shokrieh (now a postdoc at Cornell) and I found a novel potential-theoretic solution to the Pentagon Problem which appears as Remark 4.3 in this paper.   Here is the basic idea (see our paper for further details).  Let be a connected finite graph, let be the set of vertices of , and let be the Laplacian matrix of , which has rank .  For a fixed vertex , let be the minor of corresponding to deleting row and column from , and let be the inverse of the matrix .  Finally, for a column vector let denote with row removed.  Then the energy function 

is always non-negative, and Proposition 4.1(a) in our paper gives a formula for how the energy changes when a “chip firing” move is performed on .  If is an -cycle and is the vector corresponding to the labels on each vertex, then the formula from our paper shows that a legal operation which changes to (and subtracts from each neighbor so that the sum of the labels stays constant) reduces the energy by exactly .  It follows that the labels must all become non-negative after a finite number of steps.

My favorite solution to the Pentagon Problem appears in Peter Winkler’s great book Mathematical Puzzles: A Connisseur’s Collection and is attributed to Bernard Chazelle of Princeton.  It goes as follows (and applies to any -gon).  Let be the labels and let be their sum.  Define a function by setting and .  By construction, we have for all .

From Peter Winkler’s book “Mathematical Puzzles”

If is negative, then and flipping has the effect of swapping and , so that they are now in ascending order.  It does the same for all pairs which differ from these by a multiple of .  So flipping labels amounts to sorting by adjacent transpositions.  To keep track of how far away is from being sorted, let denote the number of indices for which , and let denote the number of indices for which .  Then both and are finite, depend only on modulo , and ; we denote this common sum by .   When is flipped, decreases by 1 and every other is unchanged, so goes down by exactly 1.  When gets to zero, the sequence is fully sorted, which means that all labels are non-negative and the process terminates.

Note that this in fact proves more than the problem originally asked: it shows that the process terminates in exactly steps, regardless of any choices made.  Moreover, with a small amount of extra thought we see that the ending configuration is independent of all choices as well.  Indeed, it is easy to see that entry from the original sequence will end up in position when the sorting process is complete.

Finally, we quote from a chapter by Fields Medalist Stanislav Smirnov in the book An Invitation to Mathematics by Lackmann and Schleicher, in which he talks about the Pentagon Problem and his participation in the 1986 International Math Olympiad:

I was among the students, and it was a very nice problem to tackle, perhaps the hardest at that IMO. It is almost immediately clear that one should find some positive integer function of a configuration that decreases with each operation. Indeed, two such semi-invariants were found by participants, and since we cannot decrease a positive integer infinitely many times, the procedure will necessarily come to an end.

This is a classical combinatorics problem, and if you are into olympiads, you certainly have seen a few very similar ones. What is interesting is that its life was more like that of a research problem. It was originally motivated by a question that arose in research dealing with partial reflections of polygons. So even the motivating area, geometry, was very different.

The combinatorial structure of this game is interesting in itself, and studying it on graphs that are different from a pentagon could have led to a few IMO problems and perhaps a research paper. But connections with algebraic questions have surfaced, which made it much more interesting for mathematical research. I was very pleasantly surprised to hear a talk that originated from the Pentagon Game at a research seminar some twenty years after that IMO. The talk was by Qëndrim Gashi, who used a version of the game due to Shahar Mozes to prove the Kottwitz-Rapoport conjecture in algebra. So far, versions of the Pentagon Game have led to more than a dozen research papers — not bad for an IMO problem!

These kinds of unexpected links between different areas, and between simple and complicated subjects, are one of the best things about doing mathematical research. Unfortunately, they often pass unnoticed in IMO competitions.

[Post updated 3/3/2014]

Concluding remarks:

1. For (the original pentagon problem), the energy function above is

It is easy to check directly that each move reduces the energy by as claimed above.

2. There is a Java applet illustrating the Pentagon Problem at http://www.cut-the-knot.org/Curriculum/Algebra/IMO1986_3.shtml

3. In our paper, Shokrieh and I use the -energy function to show that the unique -reduced divisor equivalent to a given divisor on a graph has minimal -energy among all divisors equivalent to which are effective outside .  (See this post for a definition of all these terms.)  We also use a related function to bound the running time of an algorithm which calculates given .

4. In 1987, Shahar Mozes introduced a generalization of the Pentagon Problem which is now called Mozes’ Numbers Game.  This game turns out to be related to Kac-Moody algebras, Coxeter groups, and other unexpected things; see the last section of this survey paper and the references therein.  The paper of Q. Gashi mentioned by Smirnov above, proving a conjecture of Kottwitz and Rapoport, can be found here.  And here is a related paper by Gashi and Schedler, whose abstract we quote: “Fix a Dynkin diagram and let λ be a coweight. When does there exist an element w of the corresponding Weyl group such that w is λ-minuscule and w(λ) is dominant? We answer this question for general Coxeter groups. We express and prove these results using a variant of Mozes’s game of numbers.”

5. Although not strictly speaking a generalization, a variant of the Pentagon Problem which applies to any graph is provided by the fact that the dollar game (explained in this blog post) is winnable if the total number of dollars present is at least the genus of the graph.

6. The Pentagon Problem is mentioned in the following Math Overflow post: http://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics