The Pentagon Problem

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 g_i is a straight line.  By construction, two lines g_i and g_j 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 g_1, g_2, g_3 each intersect one another (in distinct points) and therefore they lie in a common plane.  Since line g_4 intersects lines g_1 and g_2 in distinct points, it must lie in the same plane.  The line g_4 cannot be parallel to g_3, since their projections to the page (corresponding to forgetting the time dimension) intersect.  Thus g_3 and g_4 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 x, y, z respectively, and y is negative, you may replace x, y, z by x+y, -y, z+y, 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. Pentagon Problem_1There 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 (x_1 - x_3)^2 + (x_2 - x_4)^2 + (x_3 - x_5)^2 + (x_4 - x_1)^2 + (x_5 - x_2)^2 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

\sum_{j=1}^5 \left( |x_j| + |x_j + x_{j+1}| + |x_j + x_{j+1} + x_{j+2}| + |x_j + x_{j+1} + x_{j+2} + x_{j+3}| \right),

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 G be a connected finite graph, let V = \{ v_1,\ldots, v_n \} be the set of vertices of G, and let Q be the Laplacian matrix of G, which has rank n-1.  For a fixed vertex v_i, let Q_i be the (n-1)\times (n-1) minor of Q corresponding to deleting row i and column i from Q, and let L_i be the inverse of the matrix Q_i.  Finally, for a column vector \vec{w} \in {\mathbf Z^n} let \vec{w}_i denote \vec{w} with row i removed.  Then the energy function 

{\mathcal E}(\vec{w}) = \sum_i \vec{w_i}^T L_i \vec{w_i}

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 G.  If G is an n-cycle and \vec{w} is the vector corresponding to the labels on each vertex, then the formula from our paper shows that a legal operation which changes -y < 0 to y (and subtracts y from each neighbor so that the sum s > 0 of the labels stays constant) reduces the energy by exactly 2sy > 0.  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 n-gon).  Let x(0),\ldots,x(n-1) be the labels and let s > 0 be their sum.  Define a function b : {\mathbf Z} \to {\mathbf Z} by setting b(0)=0 and b(i) = b(i-1) + x(i {\rm \; mod \; } n).  By construction, we have b(i+n)=b(i) + s for all i.

Pentagon Solution_1

From Peter Winkler’s book “Mathematical Puzzles”

If x(i) is negative, then b(i)<b(i-1) and flipping x(i) has the effect of swapping b(i) and b(i-1), so that they are now in ascending order.  It does the same for all pairs which differ from these by a multiple of n.  So flipping labels amounts to sorting b(\cdot) by adjacent transpositions.  To keep track of how far away b(\cdot) is from being sorted, let i^+ denote the number of indices j > i for which b(j) < b(i), and let i^- denote the number of indices j < i for which b(j) > b(i).  Then both i^+ and i^- are finite, depend only on i modulo n, and \sum_{i=0}^{n-1} i^+ = \sum_{i=0}^{n-1} i^-; we denote this common sum by P.   When x(i+1) is flipped, i^+ decreases by 1 and every other j^+ is unchanged, so P goes down by exactly 1.  When P gets to zero, the sequence b(\cdot) 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 P 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 b(i) from the original sequence will end up in position i + i^+ - i^- 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 n=5 (the original pentagon problem), the energy function above is

\mathbb{E} (x_1,x_2,x_3,x_4,x_5) = 4(x_1^2 + x_2^2 + x_3^2 +x_4^2+x_5^2) + 4(x_1x_2+x_2x_3+x_3x_4+x_4x_5+x_5x_1) + 2(x_1x_3+x_2x_4+x_3x_5+x_4x_1+x_5x_2).

It is easy to check directly that each move reduces the energy by 2sy 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 v_i-energy function {\mathcal E}_i(\vec{w}) = \vec{w_i}^T L_i \vec{w_i} to show that the unique v_i-reduced divisor D' equivalent to a given divisor D on a graph G has minimal v_i-energy among all divisors equivalent to D which are effective outside v_i.  (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 D' given D.

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

One thought on “The Pentagon Problem

  1. I updated this post a bit today, adding a few paragraphs from Smirnov’s chapter in “An Invitation to Mathematics” and a couple of additional links. In addition, my student Spencer Backman sent me the following comments:

    Eriksson pursues a graph theoretic investigation of the numbers game, which eschews the use of Weyl groups, and reobtains several of Mozes’ original results:
    http://www.sciencedirect.com/science/article/pii/002437959290274E

    An investigation of looping in the numbers game by Gashi, Schedler, and Speyer:
    http://www.math.uchicago.edu/~qendrim/looping-poset.pdf

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s