2
$\begingroup$

Alice and Bob play the following game: There are piles of stones and in each turn the player can do one of the following: Remove one stone from a pile, or take two piles with $x$ and $y$ stones in them and replace them with $1$ pile of $xy$ stones. The player who has no move loses. Who has the winning strategy?

The answer can depend on the number of piles and the number of stones in each pile. I think I got an extremely ugly inductive solution. What I got is that the first player wins if and only if there is an odd number of stones, or there is an even number of stones and a positive even amount of piles with even amount of stones in them. I might be mistaken somewhere though. Does anyone have something elegant?

$\endgroup$
6
  • $\begingroup$ Did you meant $x+y$? $\endgroup$
    – nonuser
    Oct 31, 2020 at 21:57
  • $\begingroup$ @Aqua No. I meant $xy$ $\endgroup$
    – Omer
    Oct 31, 2020 at 21:57
  • 1
    $\begingroup$ @BrianM.Scott You're right, I edited my post, the criterion was wrong. $\endgroup$
    – Omer
    Oct 31, 2020 at 22:04
  • $\begingroup$ If there is one or zero piles of stones with more than one stone, the first player wins if the total number of stones is odd and the second player wins if there are an even number of stones. $\endgroup$
    – quantus14
    Oct 31, 2020 at 22:32
  • 1
    $\begingroup$ @Omer That's why it's a comment not an answer. I don't see anything wrong with posting relevant information about the problem as a comment $\endgroup$
    – quantus14
    Oct 31, 2020 at 22:39

1 Answer 1

3
$\begingroup$

A situation consists of $e$ even-sized and $o$ odd-sized non-empty heaps. I claim that winning or losing depends only on $(e,o)$. Let $W$ be the set of positions $(e,o)$ that are winning and $L$ the set of $(e,o)$ that are losing positions.

Claim. We have $$W=\{\,(e,o)\mid o\text{ odd}\lor(e\text{ even}\land e\ne 0)\,\}$$ and $$L=\{\,(e,o)\mid o\text{ even}\land (e\text{ odd}\lor e=0)\,\}.$$

Proof. Since the game must end after finitely many moves, it ssuffices to show that every valid move from a situation $\in L$ leads to a situation $\in W$, and at for every situation $\in W$, there exists a valid move to a situation $\in L$.

Let us start with $(e,o)\in L$:

First case: $o$ is even and $e=0$. Removing a stone from any (necessarily odd) heap decreases $o$ to an odd number, hence takes us to $W$. Combining two (necessarily odd) heaps also decreases $o$ by one, hence takes us to $W$. We conclude that $(o,0)\in L$ for odd $o$.

Second case: $o$ is even and $e$ odd. Removing a stone from an odd heap or combining two odd heaps or combining an odd and an even heap, decreases $o$ to odd, hence takes us to $W$ Removing a stone from an even heap increases $o$ to odd, hence takes us to $W$. Finally, combining two even heaps (which is possible only if $e\ge 3$) takes us to $(e',o')=(e-1,o')$ with $e'$ even and positive, so again to $W$.

So indeed every valid move from a situation $\in L$ takes us to a situation $\in W$.

Next consider $(e,o)\in W$:

First case: $e$ is even and positive. If $o$ is even, we can combine two even heaps to arrive at $(e',o')=(e-1,o)\in L$. If $o$ is odd, we can remove a stone from one of the even heaps and arrive at $(e',o')=(e-1,o+1)\in L$.

Second case: $o$ is odd and $e=0$. By removing a stone from an odd heap, we arrive at either $(e',o')=(1,o-1)\in L$ or (if we emptied a heap) $(e',o')=(0,o-1)\in L$.

Third case: $o$ is odd and $e$ is odd. Combine an odd and an even heap to arrive at $(e',o')=(e,o-1)\in L$.

These cases logically cover all of $W$. So indeed, from every situation in $W$, there exists a valid move to $L$. $\square$

$\endgroup$
1
  • $\begingroup$ Very nice solution! Thank you! $\endgroup$
    – Omer
    Nov 1, 2020 at 7:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .