The number $2015$ has been written in the table. Two friends play this game: In the table they write the difference of the number in the table and one of its factors. The game is lost by the one who reaches $0$. Which of the two can secure victory?
Problem
Source: Kosovo MO 2014 Grade 9, Problem 4
Tags: combinatorics
07.06.2021 21:32
Why are you posting so many Kosovo problems? Are these problems you need help on or are you posting to make it available for other people to learn from?
07.06.2021 21:42
quit post-farming. this is HSO, not MSM
07.06.2021 22:36
in order not to flood the HSO with so many problems posted at once, there is always the option to post as many problems you like in order to complete the contest collections in Old High School Olympiads forum
10.06.2021 03:12
PickleSauce wrote: quit post-farming. this is HSO, not MSM This is in HSO because this problem was asked in a High School Olympiad of a country. pinkpig wrote: Why are you posting so many Kosovo problems? Are these problems you need help on or are you posting to make it available for other people to learn from? I believe it is perfectly okay to post several questions one by one as long as a trivial to slightly non-trivial search doesn't lead to a post with the same question and discussions there after. Also I strongly believe the quoted posts are far more typical of examples of post-farming than the originally posted question. So my suggestion is that please stop criticising such things because it is unhealthy for the entire community here.
10.06.2021 03:38
Com10atorics wrote: The number $2015$ has been written in the table. Two friends play this game: In the table they write the difference of the number in the table and one of its factors. The game is lost by the one who reaches $0$. Which of the two can secure victory? We prove that the second player wins. Let $A,B$ be the two players, $k \in \mathbf{N}$ and $2k+1$ be written on the table. Players $A,B$ move as mentioned (at each step they subtract a divisor of the number currently written on the table from the number which is written and write this difference on the table until one of them reaches 0; the one reaching 0 loses). Now, since $2k+1$ is odd so every divisor of $2k+1$ is odd, and thus $A$ has to initially subtract an odd number from $2k+1$ and so the value $B$ receives is even. Let $x$ be the divisor of $2k+1$ which is subtracted from $2k+1$ by $A$ in step 1. Then $2k+1 = x \cdot d$ for some integer $d$ and thus $x| 2k+1 - x$ and so $B$ enjoys the impunity to subtract $x$ from $2k+1-x$ and give this value to $A.$ Now, notice that this value produced by $B$ is not zero since it must be the difference of an even number $2k+1-x$ and an odd number $x$ thus it must be odd. Now, in step 2, $A$ again has to produce an even number since $A$ receives an odd number and all its divisors are odd. Thus, following a similar procedure as in step 1, $B$ can ensure that at in step 2 he produces an odd number. Thus, we see that irrespective ofwhat $A$ does in step 1 at each step $B$ can ensure producing an even number for himself/herself and force $A$ to produce an even number. Also notice that at each step the value produced by $A$ is $\ge 0$ and the sequence of values produced by $A$ in successive steps is strictly decreasing. Thus, it must be $A$ who reaches $0$ first. So, $B$ has this winning strategy. Since $2015$ is odd so for the original problem the second player will have a winning strategy. If instead of $2k+1$ an even number $2k$ was written on the board in the first step, then notice that $A$ can subtract $1$ from the number to make it $2k-1$ and give it to be. Thus, we are in a setting of the previous case with just the roles of $A$ and $B$ interchanged. So, in this case $A$ will have a winning strategy.