There are $N$ piles each consisting of a single nut. Two players in turns play the following game. At each move, a player combines two piles that contain coprime numbers of nuts into a new pile. A player who can not make a move, loses. For every $N > 2$ determine which of the players, the first or the second, has a winning strategy.
Problem
Source:
Tags: symmetry, combinatorics unsolved, combinatorics
26.04.2011 23:11
N must be a definite number. Without knowing N and assuming N to be infinite, which is the impression I get from the problem, either player can combine any two piles into a new pile that currently has a single nut, and the process repeats forever. No one will win.
05.11.2014 17:35
Does anyone know how to solve this for $N \in \mathbb{Z}_{>2}$?
06.11.2014 13:54
Player 2 can win for all odd $n$. Whatever the first player does, player 2 just copies the move. For example, player 1 chooses 1 and 1 to make 2. (Then player 2 chooses another 1 and 1 to make two). Then player 2's move is always valid because player 1's move has to be valid. If player two cannot copy the move, it must be because player one just took two of the last three number "1"s to make a "2". Then player two adds the "1" to "2". So we have the following number of nuts: $a_1,a_1,a_2,a_2,...,a_n,a_n,3$. Now, if player one adds $c$ and $d$ to get $e$, then player two can just add whichever of $c$ and $d$ is left (they cannot both be gone). So for odd $n$, player $2$. Ah, it feels nice to be on AoPS after 2 and a half months. Posting the even case later. EDIT: well, it happens I dont know the even case.
21.11.2014 11:09
SMOJ, I'm not sure how your argument continues after you have a 3 and double numbers. If the first player joins the 3 and some other pile, how do you proceed to maintain symmetry? Player 2 can win all games for $n > 2$. Lemma: If a player is to move on a configuration that contains $k \ge 2$ piles of 1 nut each and one pile of an odd number ($t$) of nuts (I'll denote this configuration as math=inline]$k \times 1, t$[/math), he cannot prevent that he will be confronted on his next move with the configuration math=inline]$(k-2) \times 1, (t+2)$[/math if his opponent so desires. That's because his only moves are to join two piles of 1 nut, or to join the pile with t nuts with a 1-nut pile. This gives the configurations math=inline]$(k-2) \times 1, 2, t$[/math and math=inline]$(k-1) \times 1, (t+1)$[/math, resp. By joining the 2-nut and $t$-nut pile in the first case, and a 1-nut and the $(t+1)$-nut pile in the second case, the opposing player can always reach configuration math=inline]$(k-2) \times 1, (t+2)$[/math after his move. Because $t$ is odd, 2 and $t$ are co-prime in the first case, and because $k \ge 2$, there is guaranteed to be a 1-nut pile in the second case. Note that the always reachable configuration math=inline]$(k-2) \times 1, (t+2)$[/math in the lemma is of of the same type as the original math=inline]$k \times 1, t$[/math (with the exception that for $k=2,3$ the reachable configuration no longer contains at least 2 1-nut piles). If $n$ is odd, that's already enough to prove that player 2 can win. The starting configuration math=inline]$n \times 1$[/math can also be written as math=inline]$(n-1) \times 1, 1$[/math and is of the type mentioned in the lemma. So player 2 can make sure that when player 1 is to move, he will find the configurations math=inline]$(n-3) \times 1, 3$[/math, math=inline]$(n-5) \times 1, 5$[/math,..., math=inline]$2 \times 1, (n-2)$[/math, math=inline]$n$[/math. On the last one, player 1 cannot make a legal move as there are no longer 2 different piles to join. If $n$ is even, then application of the lemma shows that player 2 can force player 1 to face configurations from the starting configuration math=inline]$n \times 1$[/math to math=inline]$3 \times 1, (n-3)$[/math (here we need $n > 2$) . As shown in the lemma, player 1's only options at math=inline]$3 \times 1, (n-3)$[/math are to go to math=inline]$1,2,(n-3)$[/math or math=inline]$2 \times 1, (n-2)$[/math. Player 2 joins a 1-nut pile with the ($n-3$)-pile in the first case or with another 1-nut pile in the second case. Both times we get configuration math=inline]$2,(n-2)$[/math. As $n$ is even, player 1 now cannot make a legal move. EDIT: typos
23.11.2014 05:45
Ingix wrote: SMOJ, I'm not sure how your argument continues after you have a 3 and double numbers. If the first player joins the 3 and some other pile, how do you proceed to maintain symmetry? If player one joins $3$ and $a$ to make $3+a$, then player two joints $3+a$ and $a$ to make $3+2a$