Ada and Charles play the following game:at the beginning, an integer n>1 is written on the blackboard.In turn, Ada and Charles remove the number k that they find on the blackboard.In turn Ad and Charles remove the number k that they find on the blackboard and they replace it : 1 -either with a positive divisor k different from 1 and k 2- or with k+1 At the beginning each players have a thousand points each.When a player choses move 1, he/she gains one point;when a player choses move 2, he/she loses one point.The game ends when one of the tho players is left with zero points and this player loses the game.Ada moves first.For what values Chares has a winning strategy?
Problem
Source: Itamo 2015
Tags: combinatorics, Game Theory
junioragd
01.06.2015 14:10
The problem is just analizing the game and stealing strategy,so I would call it rather bashy and pointless. The number $2$ is written:Player $1$ wins.$2-3-4-5-6-3$ etc.At each "cycle" he loses and wins a point and the second player loses $2$ points.So,in conclusion,a player who plays in when the numbers $3$ or $5$ loses the game and the palyer who plays on $2$,$4$ or on a number divisible with $3$ or $5$ and bigger than $3$ and $5$ wins.Now,if the number $7$ is written,player $1$ must write $8$ and then his opponent losses cause he can write $4,2,9$ which are all wining positions for player $1$(he forces a cycle $3-4-5-6$ and before that he losses a small number of points).Now,we have that all numbers of the form $3k$,$5k$ and $8k$($k>1$) and $2$ and $4$ are winning.Also,all primes of the form $3k+2$ and $5k+4$ are losing and $3$,$5$ and $8$.Now,$13$ is a winnig position cause you must play $14$ and then your opponent must play $2,7$ or $15$ which are all winning. Lemma 1:If a prime $p$ is winning,then $2p$ is losing. If $p$ is winning,then it is $3k+1$,so $2p+1$ divisble with $3$,so it is winning and $p$ and $2$ are winning. Lemma 2:$7$ and $13$ are the only winning primes. Consider a prime $p$($p>13$).Player $1$ must play $p+1$.Now,if $p+1$ is divisble with a losing prime it is winning and if not we have $3$ cases: $1$:It is a power of $2$.Since $p>13$,we can write $8$ and win. $2$:It is $2q$,where $q$ is a winning number.This is impossible cause $2*13-1=25$ os composite and $p>13$. $3$:Then it is of the form $2*q*k$($k>1$),where $q$ is winning. Now,$7^2$ and $13^2$ are losing,so all numbers of the form $49k$ and $169k$($k>1$) are winnig. Now,$7*13$ is losing,cause Player $1$ must write $92$ and then Player $2$ plays $23$. Lemma 3:If a number is composite and is not $26,14,8,49,169,91$, it is winning. If it has a losing prime that divides it,we are done.If it doesn't,then the only primes that divide it are $2,7,13$.Since it isn't $14,26,91,49,169$,it is obviously winnig. So Chares wins for all primes expect $2,7,13$ and for $8,14,26,49,91,169$.