0
$\begingroup$

Given the following game, what is the strategy to win?

Given $N$ towers of different heights. Two players play against each other. Each player (in his turn) divides each of the towers which are greater than 1 into two separate towers. The player who wins is the one that after his (last) turn all towers are of height 1.

Any help would be appreciated.

$\endgroup$
1

1 Answer 1

0
$\begingroup$

Are you familiar with Nim? As an impartial game, this is Nim in disguise. You need to figure out which positions are $N$ (wins for the next player) and $P$ (wins for the previous player). You only care about the largest stack because each player has to play in all stacks greater than $1$. A largest stack of size $1$ is $P$ by the rules. $2$ plays to $1$ and wins, so is $N$. $3$ has to leave a $2$, so is $P$. $4$ can move to $3$ and win, so is $N$. Keep going a while and try to find a pattern.

$\endgroup$
16
  • $\begingroup$ See also this Nim question, which is very similar. $\endgroup$
    – Théophile
    Commented Dec 8, 2014 at 15:48
  • 1
    $\begingroup$ Also, if each player were choosing a single tower to split on every turn, then the game would be Grundy's game, for which a complete solution has yet to be found. In this case, though, every large tower is split, so the game is different. $\endgroup$
    – Théophile
    Commented Dec 8, 2014 at 20:14
  • $\begingroup$ I've read the Nim question, I don't know how to use it though with my problem $\endgroup$
    – user114138
    Commented Dec 9, 2014 at 11:15
  • $\begingroup$ I've read the Nim question, I don't know how to use it though with my problem $\endgroup$
    – MS93
    Commented Dec 9, 2014 at 14:18
  • $\begingroup$ Can you figure out who wins for $5,6,7,8$? $\endgroup$ Commented Dec 9, 2014 at 14:19

You must log in to answer this question.

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