# Proving that this Game on Polygons Ends

About two years ago, I started thinking about the following problem: You're given an $N$ and an $S$, positive integers. You start with an $N$-gon that has positive integer labels at each vertex, such that the labels sum to $S$. A "move" is replacing the label at some vertex with the positive difference of the labels at its two adjacent vertices. You win if you can exhibit a sequence of moves such that all of the vertex labels are zero at the end.

This is a generalization of 2003 USAMO problem B3,

"A positive integer is written at each vertex of a hexagon. A move is to replace a number by the (non-negative) difference between the two numbers at the adjacent vertices. If the starting numbers sum to $2003^{2003}$, show that it is always possible to make a sequence of moves ending with zeros at every vertex."

The USAMO problem itself can be answered in the affirmative by doing a modified greedy algorithm for most of the moves, showing there's always a move where you can reduce the problem to a smaller sum while changing the parities systematically, then doing casework for the "end game" to show that each configuration of 1's and 0's (or k's and zeros, the cases are of course equivalent) can be gotten down to all zeros.

It's easy to check that for $n=4$ and $S$ odd, there's a winning strategy. I have lots of simulation/numerical evidence and some half baked ideas to suggest that, in general, there's a winning strategy if and only if $N$ and $S$ have opposite parities. But in two years of coming back to it on and off, I haven't really made progress. It's open, as far as I know, though I knew that more surely two years ago than I do now.

Ideas?

-
USAMO sets problems that they can't solve? – Charles Stewart Jul 25 '10 at 13:46
no, the problem is a generalization of the case for hexagons, which was what the USAMO question was limited to: the general version is unsolved, the hexagon one is. – Jamie Banks Jul 25 '10 at 19:18
"iff N and S have opposite parities" is not correct: if you have a solution for N=4 and S odd, then you may just double all label values and have a solution with N and S even. Probably you should add that GCD of all labels is 1. – mau Jul 28 '10 at 9:55

I like your problem. But your opposite parity conjecture doesn't seem to handle the case N=3 and S=2 (even when corrected as in Mau's comment by gcd), with a triangle labeled as follows:

        1

1     0


This position appears to be invariant under any move, so you cannot reach all 0s.

More generally, a similar obstacle works for any 3n-gon, with S=2n. If you repeat the pattern 1 1 0 all the way around, it is stable under any move. If $n$ is odd, these will have opposite parities.

-
hmm...right. Thanks :) I think I had a "for sufficient n" and apparently some other conditions I've now forgotten... – Jamie Banks Jul 29 '10 at 4:41