Maths Olympiad Prep

Library / /61 of 62

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Ukraine

Vertices of a regular (6n+3)(6n+3)-gon, which are renumbered clockwise by numbers 1;2;;6n+31; 2; \ldots; 6n+3, are the game field. Vertices with numbers 2n+1;4n+2;6n+32n+1; 4n+2; 6n+3 are called holes. At the start of the game there are 33 chips on the field. 22 players in turn choose any one of the 33 chips and move it clockwise to a neighbouring vertex, if this one isn't occupied by another chip. The first player wins, if at least 22 chips get in holes after anyone's turn. Can the first player always win, if at the start of the game they are placed in the form of a regular triangle?
(Bogdan Rublyov)

Solution

Let's call a number of steps that each chip needs to reach the nearest hole, moving clockwise, if there are no other chips in the way, the distance to the hole. For example, for a chip that is placed on the vertex 4n4n the distance to the hole is 22, if positions 4n+14n+1 and 4n+24n+2 are free from other chips; if it's placed on a vertex with number 3n3n, then its distance is 4n+23n=n+24n+2-3n=n+2, if on vertices with numbers 3n+1;;4n+23n+1; \ldots; 4n+2 there are no chips.

Let's prove with MMI that the position when 22 chips have the same distance to the holes is the winning position for the first player. The induction will be done on this same distance to the holes. Let's say there are 22 chips that are placed at a distance kk from the hole. Let's call these chips hot, let's call the first - the hot chip on the way from which to other hot chip (let's call it second) there is a not hot chip. Let's call the last chip usual and third.

For k=0k=0 we have a situation when the first player wins.

For k=1k=1 let's consider the cases of the next step in this situation.
If in this situation it's the first player's turn, then, if there is such an opportunity, he makes a turn with a usual chip (if it's not situated near to the hot chip). And we come to the same situation with the second player's turn. Similarly in the next variation, the situation when the usual chip is situated near to the hot chip is analysed.
Thus in the described situation when it's the turn of the second player and he moves one of the hot chips and then gets it to the hole, the first player then moves another hot chip to the hole and wins.
So in order not to lose, the second player has to move the usual chip. First then also move the usual chip. It holds until the usual chip approaches the nearest hot chip and won't be able to move. We will not analyse situations, when in the process of the move of the usual chip the first player could have already won (for example, when the usual chip gets into the hole after the turn of the second player). Thus, without generality limitation, we have the following situation: the first chip is placed on the vertex 6n+26n+2, the third - on the vertex 6n+16n+1. For the second there are location options on vertices 2n2n or 4n+14n+1. Let's call this position zugzwang. In any case, after the second player's turn he will have lost because it's impossible to move the third chip. Thus, it remains to consider the case of the first player's turn. He moves the first chip. It gets to the hole. The second, in order not to immediately lose, moves the same first chip. Then the first player moves the third chip and we have the following situation. Again two hot chips are in positions 6n+26n+2 or 4n+14n+1. The third chip is in position 11. Thus, now the chip in the position 2n2n or 4n+14n+1 become the first, and the chip in the vertex 6n+26n+2 - the second. Both players have to move only the third chip, the second player is forced, and the first - due to his strategy. To situation zugzwang the third chip must reach the position 2n12n-1 or 4n4n. In the first case they together with the third chip will make 2n11=2n22n-1-1=2n-2 moves. When the second player starts, he must make a turn in a position zugzwang and he loses. In the second case both together with the third chip will make 4n1=4n14n-1=4n-1 moves. Here the first player has to make a turn in a zugzwang position. We have a following situation of chips location: 6n+2,4n+16n+2, 4n+1 - hot and 4n4n - third chip. Then the first player moves the second chip to the hole 4n+24n+2, the second player has to move the same chip, it gets in 4n+34n+3. Then the first player moves the third chip in 4n+14n+1, and we have a situation of the first case of zugzwang. The second loses. Base of induction is proved.

Let's say everything is proved for some kk. Let's consider the situation where two chips have k+1k+1 moves to the hole. Let's conditionally move the holes to the next position from the chips. Then we have the situation, which was considered in the case k=1k=1. Thus, we will always get to the situation when the hot chips will be on kk distance from the holes.

It remains to make clear that the initial situation satisfies the conditions of MMI, so the statement is proved.

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.