Nim piles

Call the state of a nim game $W$ if the player about to give a move has a winning strategy, and call it $L$ if the player about to give a move loses irrespective of how he plays (assuming both players play rationally).

We'll first prove that any $4$ pile nim game starting with initial configuration $(4k, 4k+1, 4k+2, 4k+3)$ is in state $L$ . To do this, note that the states of the games $(a, b, c, d)$ and $(a+4, b+4, c+4, d+4)$ are same. Using the fact that the state of the game $(4, 5, 6, 7)$ is $L$ (this can be proven by analyzing the possible moves; the proof is omitted because of its sheer length), the result immediately follows.

Now we shall prove by induction that all integers of the form $4k-1$ dissatisfy the given conditions. We shall also prove that all the other integers satisfy the condition. The base case will be to prove that the game $(1, 2, 3)$ is in state $L$ , while the games $(1, 2, 3, 4)$ , $(1, 2, 3, 4, 5)$ , and $(1, 2, 3, 4, 5, 6, 7)$ are in state $W$ . I did it tediously by analyzing the possible moves, and the proof is omitted here.

Now the induction step; let the statement be true for $4j-5$ . We have to show that it is true for $4j-1$ . Note that a nim game with initial configuration $(1, 2, ..., 4j-1)$ can be thought has a combination of two nim games, one with configuration $(1, 2, ..., 4j-5)$ , and the other with configuration $(4j-4, 4j-3, 4j-2, 4j-1)$ . Both the games are in state $L$ . Note that unlike a simple nim game, there is a complication here. A move a player gives is either a move to the first nim game, or a move to the second nim game. But here, from the perspective of any one nim game, one player can give consecutive moves.

Now note that if a player gives two consecutive moves, the state of the game changes. So if one player wants to change the state of a game, he can do it by taking out a stone from the set where he played last. Now note that one of these games will end before another. If, at this phase, the states of these two games are different, the first player will win. If the states of these two games are same, the second player will win. However, the second player knows how to manipulate the state of each games, and after the first player has given his move, he can manipulate the state of the games so that the states of both games are equal. Hence this configuration has state $L$ .

Similar arguments show that all other integers satisfy the given condition. The total number of these integers from $1$ to $1000$ (both inclusive) is $750$ . Hence, the required probability is $\frac{750}{1000}$ .

The positions with $4n-1$ stones lose, and all other positions win. We will prove the following lemmas, where $L$ is the set of losing positions, and $W$ is the set of winning positions, $L_i$ is a position in $L$ etc., $L_i L_j$ means the composition of those two positions, and $m, n$ are non-negative integers: $L_i L_j \in L$ $L_i W_j \in W$ $(m, m) \in L$ $(2m, 2m+1, 2n, 2n+1) \in L$

Given those lemmas, the proof runs as follows:

$(1, 2, ..., 4n-1)$ loses by decomposing it into other losing positions (Lemma 1): $(0, 1, 2, 3)$ , $(4, 5, 6, 7)$ , ..., $(4n-4, 4n-3, 4n-2, 4n-1)$ which all lose according to Lemma 4.

$(1, 2, ..., 4n-2)$ must win, otherwise appending $4n-1$ would generate a winning position (Lemma 2)

$(1, 2, ..., 4n-3)$ must win, otherwise appending $(4n-2, 4n-1)$ would generate a winning position (Lemma 2)

$(1, 2, ..., 4n)$ must win, as it is a losing position with the winning position $(4n)$ appended (Lemma 2).

This covers all cases. Now to prove the lemmas:

Lemma 1: If the position can be decomposed into two losing positions, then the second player's strategy is: "whichever of the two positions the first player moves on, then play the winning move on that position." Such a move must exist because the sub-position is losing, and the result of this is another position $L_k L_j$ .

Lemma 2: The definition of a winning position is one in which there is such a move that leaves a losing position. Therefore, the first player wins here by making that move on the winning sub-position, leaving $L_i L_k$ .

Lemma 3: $m, m$ loses because whatever move the first player makes, the second player makes the same move on the other pile, therefire the first player must be faced with $p, p$ where $p \lt m$ . If $p = 0$ here then the player has lost.

Lemma 4: If the first player moves $2m+1 \rightarrow 2m$ then this is now a position covered by Lemma 2, so the second player wins. Otherwise, the possibilities are:

If the first player moves: $2m \rightarrow 2p$ for some $p$ , then the second player moves $2m+1 \rightarrow 2p+1$ . Or if the first player moves $2m \rightarrow 2p+1$ then the second player moves $2m+1 \rightarrow 2p$ . Similarly $2m+1 \rightarrow 2p$ is met by $2m \rightarrow 2p+1$ and $2m+1 \rightarrow 2p+1$ is met by $2m \rightarrow 2p$ .

So the second player can always leave the first player with another position of this category. The smallest such position is $(0,1,0,1)$ = $(1,1)$ which loses by Lemma 3. QED.

The total number of winning positions is then the number of numbers from $1$ to $1000$ which are not of the form $4n-1$ , that is clearly $1000 * \frac{3}{4} = \boxed{750}$ since $1000$ is a multiple of 4.

First, we imagine Calvin and Lino follow a strategy: in each turn, a player remove exacly 1 stone, Lino will win if k is an odd number. In fact, it's obvious that they will never follow this strategy since it is not optimal, but we can infer something from this no-optimal strategy: in optimal strategy, each player will try to make the total number of stones to be an even number after his turn; if one player can keep doing that until the end of the game, he will remove the last stone. But how can they do that?

In each pile of stones, we have some "pairs of stone" with the rule that no 2 "pairs of stone" have 1 stone in common. For example, 1-stones-pile has 0 "pairs of stone", 2-stones-pile and 3-stones-pile have 1 "pair of stone", 4-stones-pile and 5-stones-pile have 2 "pairs of stone", ... Now, the optimal strategy will be: Lino, in his first turn, try to make the total number of stones to be an even number, also make the total "pairs of stone" to be an even number; Calvin, in turn, also try to make the total number of stones to be an even number by remove a number of "pairs of stone".

Lino can't keep following this strategy until Calvin has no "pairs of stone" if $k \equiv 3 (mod 4)$ . Therefore, there are 250 numbers of piles that cannot ensure that Lino wins and the answer is 750.