Let $n\ge 3$ be an integer. Lucas and Matías play a game in a regular $n$-sided polygon with a vertex marked as a trap. Initially Matías places a token at one vertex of the polygon. In each step, Lucas says a positive integer and Matías moves the token that number of vertices clockwise or counterclockwise, at his choice. a) Determine all the $n\ge 3$ such that Matías can locate the token and move it in such a way as to never fall into the trap, regardless of the numbers Lucas says. Give the strategy to Matías. b) Determine all the $n\ge 3$ such that Lucas can force Matías to fall into the trap. Give the strategy to Lucas. Note. The two players know the value of $n$ and see the polygon.
Problem
Source: 2020 Argentina OMA L3 p6
Tags: game, combinatorics, game strategy, winning strategy
26.12.2020 09:49
Does Matias know which vertex is the trap?
26.12.2020 09:56
, so I do not know. edit: I think that Matias knows, otherwise he might place the token in the trap at the start and lose at once
28.12.2020 06:14
a. If n is not a power of 2, Matias wins. Let p be an odd prime divisor of n, color the vertices modulo p. If the initial vertex does not have the same color as the trap vertex, then Matias can always choose a vertex that is not the same color as the trap vertex each step. b. If n is a power of 2, Lucas wins. Let n=2^m. At step k, Lucas calls the number 2^(m-1-v_2(k)), for a total of n-1 steps. (For example: if n=8, the numbers 4,2,4,1,4,2,4 are called.) In any number of consecutive positive integers, there is a unique number with the highest power of 2. Therefore, in any number of consecutive steps, there is a unique number called with the lowest power of 2 and these steps cannot sum to zero, and the token must visit each vertex once. This is exactly the same reasoning as 1±1/2±1/3±1/4±... cannot be an integer.
12.01.2021 20:13
https://artofproblemsolving.com/community/c6h1739464p11303581 similar problem