Say we are given n piles of stones. Sizes are $s_{1}, s_{2}, .. , s_{n}$, they can be any positive integer numbers. The game is played by two players, they alternate their moves. The allowed moves are: 1. Take exactly 1 stone from 1 pile. 2. Take all stones from 1 pile.
Wins the player who mades the last move. Both play optimally.
Is it possible to find the winner for some state? I was thinking about Grundy numbers, but stuck with definitions and do not know can it be applied here.
On
It’s possible to calculate the nim values of small positions by hand by working up from $0$ stones. Here I’ve done it for every position with at most $6$ stones. A distribution $1^{n_1}2^{n_2}3^{n_3}\ldots$ describes a game with $n_1$ piles of size $1$, $n_2$ piles of size $2$, and so on.
$$\begin{array}{|c|c|c|} n\text{ stones}&\text{distribution}&\text{nim value}\\ \hline 0&-&0\\ \hline 1&1^1&1\\ \hline 2&1^2&0\\ &2^1&2\\ \hline 3&1^3&1\\ &1^12^1&3\\ &3^1&1\\ \hline 4&1^4&0\\ &1^22^1&2\\ &2^2&0\\ &1^13^1&0\\ &4^1&2\\ \hline 5&1^5&1\\ &1^32^1&3\\ &1^12^2&1\\ &1^23^1&1\\ &2^13^1&3\\ &1^14^1&3\\ &5^1&1\\ \hline 6&1^6&0\\ &1^42^1&2\\ &1^22^2&0\\ &2^3&2\\ &1^33^1&0\\ &1^12^13^1&2\\ &3^2&0\\ &1^24^1&2\\ &2^14^1&0\\ &1^15^1&0\\ &6^1&0\\ \hline \end{array}$$
The $0$ positions are wins of the second player; the others are all wins for the first player. It’s very noticeable that (so far, at least) the nim value of a position always has the same parity (even or odd) as the total number of stones. If this situation continues, the first player can always win when the total number of stones is odd. The situation when the total number of stones is even is clearly more complicated: some positions are wins for the first player, and some are wins for the second player. Let’s single out the ones that are wins for the first player:
$$2^1,1^22^1,4^1,1^42^1,2^3,1^12^13^1,1^24^1$$
Since we’ve already seen a distinction between odd and even, we might notice that every one of these positions has an odd number of piles. A quick check shows that the positions with an even number of stones and an even number of piles are all (so far) wins for the second player. This leads to the
Conjecture: The second player wins if and only if both the number of stones and the number of piles are even.
Proof. Let $n$ be the number of stones and $p$ the number of piles. Let $\mathscr{P}$ be the set of positions in which $n$ and $p$ are both even. Any move either reduces $n$ by $1$ or reduces $p$ by $1$; removing a pile of size $1$ does both. Thus, if $n$ and $p$ are both even, any move makes at least one of them odd; in other words, every move from a position in $\mathscr{P}$ results in a position not in $\mathscr{P}$. Now suppose that at least one of $n$ and $p$ is odd, so that the position is not in $\mathscr{P}$. There are three cases to consider.
If $n$ is odd and $p$ is even, then $n\ne p$, so there is at least one pile with more than $1$ stone. If we remove $1$ stone from that pile, we decrease $n$ by $1$, making it even, and don’t change $p$, so we end up in a position in $\mathscr{P}$.
Suppose that $n$ is even and $p$ is odd. Since $n$ is even, the number of piles with an odd number of stones must be even, so there must be at least one pile with an even number of stones. If we remove that pile, we leave a position in $\mathscr{P}$.
If $n$ and $p$ are both odd, there must be at least one pile with an odd number of stones. If we remove that pile, we leave a position in $\mathscr{P}$.
Let $\mathscr{N}$ be the set of positions not in $\mathscr{P}$. We’ve just shown that every move from a position in $\mathscr{P}$ leaves a position in $\mathscr{N}$, while every position in $\mathscr{N}$ admits at least one move to a position in $\mathscr{P}$. Moreover, the basic lost position, the one with no stones, is in $\mathscr{P}$. Thus, a player $A$ confronted with a position in $\mathscr{N}$ can always win by leaving the other player a position in $\mathscr{P}$: the other player is forced to leave $A$ another position in $\mathscr{N}$, and the sequence repeates until the other player has lost. It follows that the first player can win if the initial position is in $\mathscr{N}$, and the second player can win if the initial position is in $\mathscr{P}$. $\dashv$
If both the number of piles with an odd number of sticks and the number of non-empty piles with an even number of sticks are even, the first player loses. Otherwise the first player wins.
Proof:
Let's label the game positions with (parity of number of odd-stick piles, parity of number of even-stick piles). With that,the condition above can be reformulated as: If the position is (even,even), the first player loses, otherwise the first player wins.
Also, since for a pile with only one stick, taking one stick and taking the whole pile is obviously the same move, I'll stick to the convention that "taking one stick" does not include "taking the last stick of a pile".
If at your turn no non-empty piles are left, you've obviously lost. That obviously is an (even,even) state.
If you are presented with another (even,even) state, you obviously have only the following four possibilities (not all of them may be available):
You remove a single stick from some pile, turning that pile's parity, and thus resulting in an (odd,odd) state. Then your opponent can do the same (note that there is at least one pile with more than one stick, as there is at least one non-empty even-sticks pile, which has at least two sticks), and thus again prevent you with a (even,even) state.
You remove a complete even-sticks pile, resulting in an (even,odd) state. Again, your opponent can do the same, presenting you an (even,even) state again.
Finally, you may remove a complete odd-stick pile, resulting in an (odd,even) state. Also in this case, your opponent can do the same, presenting you an (even,even) state again.
So if you get an (even,even) state, your opponent can make sure that whatever you do, you will get an (even,even) state again. Since every move reduces the number of sticks, you'll eventually be presented with thew (even,even) state of no heaps left, that is, you will lose.
Now if you are not presented an (even,even) state, you will be presented one of the following:
(even,odd): Remove one of the even-stick piles.
(odd,even): Remove one of the odd-stick piles.
(odd, odd): Remove a single stick from a pile with more than one pile.
In all cases the opponent will then get an (even,even) state, and therefore lose, so you win.