A Nim-like game with conditions and strategies

Question

The game:

Given $S = \{ a_1,..., a_n \}$ of positive integers ($n \ge 2$). The game is played by two people. At each of their turns, the player chooses two different non-zero numbers and subtracts $1$ from each of them. The winner is the one, for the last time, being able to do the task.

The problem:

Suppose that the game is played by $\text{A}$ and herself.

$\text{a)}$ Find the necessary and sufficient conditions of $S$ (called $\mathbb{W}$), if there are any, in which $\text{A}$ always clear the set regardless of how she plays.

$\text{b)}$ Also, find the necessary and sufficient conditions of $S$ (called $\mathbb{L}$) in which $\text{A}$ is always unable to clear the set regardless of how she plays.

$\text{c)}$ Then, find the strategies/algorithm by which $\text{A}$ can clear the set with $S$ that doesn't satisfy $\mathbb{L} \vee \mathbb{W}$.

Next, suppose that the game is played by $\text{A}$ and $\text{B}$ respectively and $S$ that doesn't satisfy $\mathbb{W}$.

$\text{d)}$ Is there any of them having the strategies/algorithm to win the game? If so, who is her and what is her winning way? (It's possible to suppose that $\text{A}$ and $\text{B}$ play the game optimally)

$\;$

Note:

$\text{1)}$ This is not an assignment. I have just create this out of a familiar thing in my life. So, I haven't known whether there is an official research or even names for the game. If so, I'd be very appreciated if you shared those.

$\text{2)}$ The case of $n = 2$ is so obvious that we can eliminate that from consideration. We can do the same thing to an obvious condition in $\mathbb{W}$ (if $\mathbb{W} \neq \varnothing$): $\left ( \sum_{i \in S} i \right ) \; \vdots \; 2$.

Thanks in advance.

${}$

Update 1: To clear many people's misunderstanding and to avoid it for new ones, I emphasize the word "different" above. And by "different", I mean different indices of numbers, not their values. If this is still not clear, I think we should consider $S$ as a finite natural sequence ($a_1$ to $a_n$) and not delete any of them once they become $0$.

Update 2: (d) has been renewed a little, thank to Greg Martin.

Answer 1

I'm more interested in the competitive part of the question, so my answer deals with the following modification to (d): The starting position can be any sequence of $n\ge3$ positive integers, regardless of whether the total sum is even or odd (although that overall parity cannot change during the game, of course). The first player to be unable to move loses, regardless of whether all the numbers are $0$ yet. For this game, here are some emperical observations.

If $n=3$ and the parity of the total is even: the losing positions are precisely those where all three numbers are individually even. So a winning strategy, once I make a move that results in all three numbers being even, is to subtract from the same two numbers my opponent does.

If $n=4$ and the parity of the total is even: the losing positions are precisely those where all four numbers are even or all four numbers are odd. One winning strategy (there are others) is to always subtract from the two odd numbers.

If $n=5$ and the parity of the total is even: the losing positions are precisely those where all five numbers are even, or the smallest number is even and all other numbers are odd. Winning strategy: if my opponent leaves two odd numbers, subtract from them; otherwise subtract from the smallest number (which will be odd) and the unique even number.

When the parity of the total is odd, already the game seems more complicated. When $n=3$, for example, losing positions include the rows of \begin{array}{ccc} 1 & 2 & 2 \\ 1 & 4 & 4 \\ 1 & 6 & 6 \\ 1 & 8 & 8 \\ 1 & 10 & 10 \\ 2 & 2 & 5 \\ 2 & 2 & 7 \\ 2 & 2 & 9 \\ 2 & 3 & 4 \\ 2 & 4 & 7 \\ 2 & 4 & 9 \\ 2 & 5 & 6 \\ 2 & 6 & 9 \\ 2 & 7 & 8 \\ 2 & 9 & 10 \\ 3 & 3 & 3 \\ 3 & 4 & 6 \\ 3 & 5 & 5 \\ 3 & 6 & 8 \\ 3 & 7 & 7 \\ 3 & 8 & 10 \\ 3 & 9 & 9 \\ 4 & 4 & 5 \\ 4 & 4 & 9 \\ 4 & 5 & 8 \\ 4 & 6 & 7 \\ 4 & 7 & 10 \\ 4 & 8 & 9 \\ 5 & 5 & 7 \\ 5 & 6 & 6 \\ 5 & 6 & 10 \\ 5 & 7 & 9 \\ 5 & 8 & 8 \\ 5 & 10 & 10 \\ 6 & 6 & 9 \\ 6 & 7 & 8 \\ 6 & 9 & 10 \\ 7 & 7 & 7 \\ 7 & 8 & 10 \\ 7 & 9 & 9 \\ 8 & 8 & 9 \\ 9 & 10 & 10 \end{array} while winning positions include the rows of \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 3 \\ 1 & 1 & 5 \\ 1 & 1 & 7 \\ 1 & 1 & 9 \\ 1 & 2 & 4 \\ 1 & 2 & 6 \\ 1 & 2 & 8 \\ 1 & 2 & 10 \\ 1 & 3 & 3 \\ 1 & 3 & 5 \\ 1 & 3 & 7 \\ 1 & 3 & 9 \\ 1 & 4 & 6 \\ 1 & 4 & 8 \\ 1 & 4 & 10 \\ 1 & 5 & 5 \\ 1 & 5 & 7 \\ 1 & 5 & 9 \\ 1 & 6 & 8 \\ 1 & 6 & 10 \\ 1 & 7 & 7 \\ 1 & 7 & 9 \\ 1 & 8 & 10 \\ 1 & 9 & 9 \\ 2 & 2 & 3 \\ 2 & 3 & 6 \\ 2 & 3 & 8 \\ 2 & 3 & 10 \\ 2 & 4 & 5 \\ 2 & 5 & 8 \\ 2 & 5 & 10 \\ 2 & 6 & 7 \\ 2 & 7 & 10 \\ 2 & 8 & 9 \\ 3 & 3 & 5 \\ 3 & 3 & 7 \\ 3 & 3 & 9 \\ 3 & 4 & 4 \\ 3 & 4 & 8 \\ 3 & 4 & 10 \\ 3 & 5 & 7 \\ 3 & 5 & 9 \\ 3 & 6 & 6 \\ 3 & 6 & 10 \\ 3 & 7 & 9 \\ 3 & 8 & 8 \\ 3 & 10 & 10 \\ 4 & 4 & 7 \\ 4 & 5 & 6 \\ 4 & 5 & 10 \\ 4 & 6 & 9 \\ 4 & 7 & 8 \\ 4 & 9 & 10 \\ 5 & 5 & 5 \\ 5 & 5 & 9 \\ 5 & 6 & 8 \\ 5 & 7 & 7 \\ 5 & 8 & 10 \\ 5 & 9 & 9 \\ 6 & 6 & 7 \\ 6 & 7 & 10 \\ 6 & 8 & 9 \\ 7 & 7 & 9 \\ 7 & 8 & 8 \\ 7 & 10 & 10 \\ 8 & 9 & 10 \\ 9 & 9 & 9. \end{array}

Answer 2

This answers parts a)-c).

The set $\mathbb{W}$ is fairly small: It consists of sets $S=\{a,a\}$ and $S=\{1,\ldots,1\}$ with an even number of $1$'s. Every other set can, by (in)judicious play, lead to a losing position of the form $S=\{a\}$. This can be proved by induction on the total of the integers in $S$: If $S$ is not one of the two specified types (and not yet a single number), it can be made smaller, yet still not of either type in $\mathbb{W}$, by subtracting $1$ from each of the two smallest numbers, unless $S=\{1,1,a,a\}$ with $a\gt1$, in which case subtracting $1$ from $1$ and $a$, which leaves $\{1,a-1,a\}$, does the trick.

The set $\mathbb{L}$ consists of sets $S$ for which the total of the integers is odd and sets for which the largest integer is greater than the sum of the others. This is again proved by induction, based on the fact that whatever you do, the smaller set after a play has been made will still either have an odd sum or its largest number will still exceed the sum of the other numbers.

As for a solitaire strategy for clearing the set (when possible), it simply amounts to always subtracting $1$ from the largest element; the other $1$ can be subtracted from anything.

Answer 3

An old thread, but I noticed it in the "related"s for another question, and found it interesting.

Let me introduce the game of "raindrops": You have a vertical track of some finite number of "levels" and at each level is a finite number of raindrops. During each player's turn, they either move one raindrop down two levels, or two raindrops down 1 level each, with the restriction that the two raindrops cannot both start at the same level. Raindrops at the bottom of the track move off the board (which counts as 1 level, not two). Play continues until a player cannot make his or her two moves, in which case the other player wins.

Why introduce this other game? Because it is the same game in disguise. After each move in the game for this thread, rearrange the piles in a vertical row in ascending order as you move down. I.e., the smallest piles on top, and the largest on the bottom. This is immaterial to the game play of this game, as it does not depend in any way on the arrangement of the piles. Now translate it to my game by subtracting from each pile the amount of stones in the pile immediately above it. The top pile is unchanged. Under this metamorphosis, a move in your game becomes a move in mine, and vice versa if you reverse the process.

So what can we figure out from raindrops? Call the bottom level the "pool". Clearly, the game ends when all levels other than the pool have been emptied. Also, if we number the levels, starting with the pool = level $0$, and increasing as we go up, and if $r_i$ is the number of raindrops in level $i$ at the start of the game, and $D$ is the number of raindrops "drained from the pool" (i.e., removed from the board) during the game, then the total number of moves is $\left(\sum nr_n\right) + D$, and the total number of turns is half of that. If the number of turns is odd, then Player 1 won. If it is even, then Player 2 won. It follows that the game is completely determined by the initial position and how many raindrops are completely removed from the board.

I believe that the question of which positions are wins can be determined from this but am out of time right now to pursue it further.