Vertices of a regular -gon, which are renumbered clockwise by numbers , are the game field. Vertices with numbers are called holes. At the start of the game there are chips on the field. players in turn choose any one of the 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 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 the distance to the hole is , if positions and are free from other chips; if it's placed on a vertex with number , then its distance is , if on vertices with numbers there are no chips.
Let's prove with MMI that the position when 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 chips that are placed at a distance 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 we have a situation when the first player wins.
For 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 , the third - on the vertex . For the second there are location options on vertices or . 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 or . The third chip is in position . Thus, now the chip in the position or become the first, and the chip in the vertex - 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 or . In the first case they together with the third chip will make 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 moves. Here the first player has to make a turn in a zugzwang position. We have a following situation of chips location: - hot and - third chip. Then the first player moves the second chip to the hole , the second player has to move the same chip, it gets in . Then the first player moves the third chip in , 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 . Let's consider the situation where two chips have 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 . Thus, we will always get to the situation when the hot chips will be on distance from the holes.
It remains to make clear that the initial situation satisfies the conditions of MMI, so the statement is proved.