Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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). –  Mark S. Dec 21 '13 at 15:27
    
That's a nice and non-trivial nim game with very simple rules. –  Xoff Dec 21 '13 at 17:18
    
@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". –  Vincent J. Ruan Dec 21 '13 at 17:39
    
Just to be sure, when you choose two numbers in $S$, they have to be different ? Or can you choose the same twice ? –  Xoff Dec 21 '13 at 19:44
    
@Xoff: They need to be different. –  Mark S. Dec 22 '13 at 14:41
show 1 more comment

2 Answers

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}

share|improve this answer
    
Usually, winning positions are positions that are a win for the first player. 1,2,2 for example is not. –  Xoff Dec 22 '13 at 13:30
    
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? –  Greg Martin Dec 23 '13 at 3:22
    
Yes :) But your answer is nice anyway. –  Xoff Dec 23 '13 at 8:24
    
@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. –  Vincent J. Ruan Jan 1 at 3:25
    
@GregMartin: Can you share the seeming algorithm you used to generate those examples of the case of the odd sum? –  Vincent J. Ruan Jan 1 at 5:23
show 2 more comments

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.

share|improve this answer
    
$\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). –  Vincent J. Ruan Dec 29 '13 at 20:12
    
@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\}$. –  Barry Cipra Dec 29 '13 at 20:55
    
Perhaps you include the case of choosing the same number in a turn, which we exclude by comments below my question. –  Vincent J. Ruan Dec 29 '13 at 22:41
    
@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"? –  Barry Cipra Dec 30 '13 at 0:31
1  
@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$. –  Barry Cipra Dec 31 '13 at 14:53
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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