8
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ For problem b), I don't really understand what you're asking. If A plays both roles, then how can they lose? Also, I don't understand what you're saying with the $\vdots$ in Note 2). $\endgroup$ – Mark S. Dec 21 '13 at 15:27
  • $\begingroup$ That's a nice and non-trivial nim game with very simple rules. $\endgroup$ – Xoff Dec 21 '13 at 17:18
  • $\begingroup$ @Mark S.: I'm sorry that it is more confusing than I thought. I have edited it. Btw, the symbol $\vdots$ means "to be divisible by". $\endgroup$ – Vincent J. Ruan Dec 21 '13 at 17:39
  • $\begingroup$ Just to be sure, when you choose two numbers in $S$, they have to be different ? Or can you choose the same twice ? $\endgroup$ – Xoff Dec 21 '13 at 19:44
  • $\begingroup$ @Xoff: They need to be different. $\endgroup$ – Mark S. Dec 22 '13 at 14:41
4
$\begingroup$

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}

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Usually, winning positions are positions that are a win for the first player. 1,2,2 for example is not. $\endgroup$ – Xoff Dec 22 '13 at 13:30
  • $\begingroup$ I think you're right - I was thinking of what positions we want to leave after our turn. Which is to say, I have the terminology 100% backwards? $\endgroup$ – Greg Martin Dec 23 '13 at 3:22
  • $\begingroup$ Yes :) But your answer is nice anyway. $\endgroup$ – Xoff Dec 23 '13 at 8:24
  • $\begingroup$ @GregMartin: About the parity condition, I think I make it clear in Note (2) that it's just an obvious condition in $\mathbb{W}$, nothing to do with (d). Moreover, the reason why I restricted $S$ ($\overline{\mathbb{L} \vee \mathbb{W}}$) is that (I think) if $S$ was either $\mathbb{L}$ or $\mathbb{W}$, (d) would be easily determined by consideration of sum of the set in modulo 4. It turns out to be wrong, namely (and only) for the case of $\mathbb{L}$ (as you show in your examples). So, I've updated a bit (d) towards your version. $\endgroup$ – Vincent J. Ruan Jan 1 '14 at 3:25
  • $\begingroup$ @GregMartin: Can you share the seeming algorithm you used to generate those examples of the case of the odd sum? $\endgroup$ – Vincent J. Ruan Jan 1 '14 at 5:23
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $\mathbb{W}$ is alright, but $\mathbb{L}$ seems to be not enough because of the strategy. For example, $\{ 3,3,4 \}$ is a "winnable" set ($ \rightarrow \{ 2,2,4 \} \rightarrow \; ... $) but is unable to be won by the strategy. Perhaps, we should find another algorithm, which can both maintain the quality of "not $\mathbb{L}$" and clear every set $\notin \mathbb{L}$ (suppose that your $\mathbb{L}$ is right). $\endgroup$ – Vincent J. Ruan Dec 29 '13 at 20:12
  • $\begingroup$ @VincentJ.Ruan, I don't understand your comment. Applied to $\{3,3,4\}$, the strategy I described goes $\{3,3,4\}\to\{2,3,3\}\to\{2,2,2\}\to\{1,1,2\}\to\{0,1,1\}\to\{0,0,0\}$. $\endgroup$ – Barry Cipra Dec 29 '13 at 20:55
  • $\begingroup$ Perhaps you include the case of choosing the same number in a turn, which we exclude by comments below my question. $\endgroup$ – Vincent J. Ruan Dec 29 '13 at 22:41
  • $\begingroup$ @VincentJ.Ruan, you're right, I did not notice the insertion of "different" in the statement of the problem. It looks like the change affects Greg Martin's answer as well. He has $\{1,1,1\}$ and $\{3,3,3\}$ in opposite categories, but requiring two numbers to be different means it's impossible to make a play from either position. Or do I not understand what you mean by "different"? $\endgroup$ – Barry Cipra Dec 30 '13 at 0:31
  • 1
    $\begingroup$ @VincentJ.Ruan, oh good. I had in mind that the induction was on the the sum of the numbers. A possibly useful way to think of the game is that it's played on partitions of numbers, where each move takes a partition of some $N$ and leaves a partition of $N-2$. $\endgroup$ – Barry Cipra Dec 31 '13 at 14:53
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.