Maths Olympiad Prep

Library / /1 of 2

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Romanian Master of Mathematics (RMM)

Problem:

For an integer n5n \geq 5, two players play the following game on a regular nn-gon. Initially, three consecutive vertices are chosen, and one counter is placed on each. A move consists of one player sliding one counter along any number of edges to another vertex of the nn-gon without jumping over another counter. A move is legal if the area of the triangle formed by the counters is strictly greater after the move than before. The players take turns to make legal moves, and if a player cannot make a legal move, that player loses. For which values of nn does the player making the first move have a winning strategy?

Solution

Solution:

We shall prove that the first player wins if and only if the exponent of 22 in the prime decomposition of n3n-3 is odd.

Since the game is identical for both players, has finitely many possible states and always terminates, we can label the possible states Wins or Losses according as whether a player faced with that position has a winning strategy or not. A state is a Win if and only if there is some legal move taking the state to a Loss, and a state is a Loss if and only if all moves take that state to a Win (including the case where there are no legal moves).

Lemma. Any configuration in which the triangle formed by the three counters is not isosceles is necessarily a Win.

Proof. Label the positions of the counters X,Y,ZX, Y, Z so that the arc YZYZ of the circumcircle is shortest and the arcZX\operatorname{arc} ZX is longest. Begin by moving the counter at ZZ around the polygon on the arc YZXYZX until it forms an isosceles triangle XYZXYZ' with apex at YY (note that the arcXY\operatorname{arc} XY is less than half the circle, so that ZZ does not jump over the counter at XX). If this configuration is a Loss, we are done.

If instead this configuration is a Win, then the counters can be moved legally from triangle XYZXYZ' to reach a losing state. This cannot involve the counter at YY, so by symmetry a Loss state can be reached by moving the counter at ZZ' to a new location ZZ''. But then the counter at ZZ could have been moved to ZZ'' in the first place, so the original configuration was a Win as well.

For every nonzero integer xx, denote by v2(x)v_2(x) the exponent of 22 in the prime decomposition of xx. Now, given a configuration in which the triangle formed by the three counters is isosceles, the arcs between the vertices having lengths a,a,ba, a, b respectively (in appropriate units so that 2a+b=n2a + b = n), we show that the configuration is a Win if and only if aba \neq b and v2(ab)v_2(a-b) is odd.

Write b=a±abb = a \pm |a-b| and notice that the only other isosceles triangle that can be reached from the original configuration is one with arc lengths a,a±ab/2,a±ab/2a, a \pm |a-b|/2, a \pm |a-b|/2. If ab|a-b| is odd, this is of course impossible, so the configuration is a Loss, since all non-isosceles configurations are Wins, by the lemma.

If instead ab|a-b| is even, then all states that can be reached from the original configuration are Wins, except possibly the state with arc lengths a,a±ab/2,a±ab/2a, a \pm |a-b|/2, a \pm |a-b|/2. Consequently, (a,a,b)(a, a, b) is a Win if and only if (a,a±ab/2,a±ab/2)(a, a \pm |a-b|/2, a \pm |a-b|/2) is a Loss. Since the side lengths of this new triangle differ by ab/2|a-b|/2, the conclusion follows inductively once the exceptional and trivial case a=ba = b is dealt with.

As an immediate corollary, the configuration with arc lengths 1,1,n21, 1, n-2 (the starting configuration of the question) is a Win if and only if v2(n3)v_2(n-3) is odd.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.