Given an integer $n\geq 2$. There are $N$ distinct circle on the plane such that any two circles have two distinct intersections and no three circles have a common intersection. Initially there is a coin on each of the intersection points of the circles. Starting from $X$, players $X$ and $Y$ alternatively take away a coin, with the restriction that one cannot take away a coin lying on the same circle as the last coin just taken away by the opponent in the previous step. The one who cannot do so will lost. In particular, one loses where there is no coin left. For what values of $n$ does $Y$ have a winning strategy?
Problem
Source: CHKMO
Tags: combinatorics
08.01.2016 18:33
Is the answer all $n \neq 2,3$ ?
23.02.2016 11:39
Could you please give me some guidance ? Thank you.
24.02.2016 11:11
Help me please...
24.02.2016 12:39
Sorry I miss this condition as the last coin just taken away by the opponent in the previous step
24.02.2016 15:10
The answer is all $n\ge 4$. Clearly $X$ will win for $n=2,3$. We rewrite the game as such: Two players $X,Y$ take turns writing $2$ distinct numbers on a board among $\{1,2,\ldots ,n\}$ with $X$ going first. They cannot write a number written in the last turn by their opponent and each pair of numbers can be written at most twice. We show $Y$ can always win for $n\ge 4$. We pair the pair of numbers, such that whenever $X$ writes a pair $Y$ can write a corresponding pair. For $n=4$, pair as such: $\{(1,2),(3,4)\}, \{(1,3),(2,4)\}, \{(1,4),(2,3)\}$. For $n=5$, $\{(1,2),(3,4)\}, \{(1,3),(2,5)\}, \{(1,4),(3,5)\}, \{(1,5),(2,4)\}, \{(2,3),(4,5)\}.$ For $n=6$, $\{(1,3),(2,5)\}, \{(1,4),(2,6)\}. \{(1,5),(3,6)\}, \{(1,6),(4,5)\}, \{(2,3),(4,6)\}, \{(2,4),(3,5)\}, \{(1,2),(3,4),(5,6)\}$. For the final triplet, $Y$ must ensure that (s)he does not use the same pair until the last matchup to win(e.g. if $X$ writes $(1,2)$, $Y$ writes $(3,4)$, if $X$ writes $(1,2)$ again(may be some time later) $Y$ must write $(5,6)$(not the same pair $Y$ written previously))(note that each pair can be written twice). For $n=7$, $\{(1,3),(4,6)\}, \{(1,4),(5,7)\}. \{(1,5),(4,7)\}, \{(1,6),(2,7)\}, \{(1,7),(3,5)\}, \{(2,3),(4,5)\}, \{(2,4),(6,7)\}, \{(2,5),(3,6)\}, \{(2,6),(3,7)\}, \{(1,2),(3,4),(5,6)\}$. Hence $Y$ wins for $n=4,5,6,7$. We now show if $Y$ can win for $n$, then $Y$ wins for $n+4$. Within $n+1$ to $n+4$ we can pair as such: $\{(n+1,n+2),(n+3,n+4)\}, \{(n+1,n+3),(n+2,n+4)\}, \{(n+1,n+4),(n+2,n+3)\}$. For the others, we pair $\{(n+1,1),(n+2,2)\},\{(n+1,2),(n+2,3)\},\ldots ,\{(n+1,n),(n+2,1)\}$ and $\{(n+3,1),(n+4,2)\},\{(n+3,2),(n+4,3)\},\ldots ,\{(n+3,n),(n+4,1)\}$. Hence $Y$ can win for all $n\ge 4$.
26.02.2016 06:36
nice solution thank you