A Combinatorial Game Riddle - two players dividing towers

Question

I have recently been struggling on a riddle- it's a Nim type of game.

In front of two players, there are $n_1, n_2, \dots, n_k$ height towers ($k$ towers, each of them of some integer height). On each turn, a player divides all towers into two smaller towers, except ot the towers of height 1. Meaning: $$5 \rightarrow (4,1) \rightarrow ((2,2),1) \rightarrow(((1,1),(1,1),1))$$ are three sequential valid moves, of player A, then B, and A again.

For instance: 19, 7, 8, can be divided this way: $19 \rightarrow (3,16), 7 \rightarrow (1,6), 8 \rightarrow (4,4). $

$5 \rightarrow (0,5)$ isn't a valid division

The player that on his turn "flattens" the towers (all towers of height 1) is the winner. What's the strategy to win the game, and shall that player choose to go first or second in the game?

I do know that there is some invariant- I just can't find it. Also, I'm almost certainly sure the solution has to do something with the highest tower.

Any help would be greatly appreciated!

Answer 1

Instead of solving the problem for you, this answer gives you the tools you need to solve it.

$\newcommand{\cc}{\operatorname{\Delta}}$Your problem falls into a broader class of problems in combinatorial game theory. Suppose that $G_1,\dots,G_n$ are combinatorial games (meaning perfect information, players take turns, games certainly end, and the first player without a move loses). Define the continued conjunctive compound $G_1\cc G_2 \cc \dots \cc G_n$ to be the game where $G_1,\dots,G_n$ are played simultaneously, and each player moves in all components which have not yet ended. In your problem, if we let $T_i$ denote the game played on a single tower, then your game is of the form $T_1 \cc \dots \cc T_n$. This is notation used by Conway in On Numbers and Games. Conway derived the general rule for solving the $n$-fold continued conjunction $G_1\cc \dots\cc G_n$ using the information from the component games.

Here is the general theory for continued conjunctive compounds. To solve continued conjunctive compounds, we need to calculate a certain piece of information about each component known as the suspense number. Imagine two players playing a combinatorial game $G$ with the following additional incentive; if they game lasts for $k$ turns, then the loser has to pay the winner $k$ dollars. This means that a player who can win the game will try to prolong it, and a player who is in a losing position will try to make the game end quickly. The suspense number, $S(G)$, is the number of turns the game will last under optimal play with this incentive. It can be calculated inductively as follows:

• If $G$ has no options, then the suspense number is zero.

• If any option of $G$ has an even suspense number, then $S(G)$ is one more than the maximal even suspense number of $G$'s options.

• If all options of $G$ have an odd suspense number (and there is at least one odd option), then $S(G)$ is one more than the minimal odd suspense number of $G$'s options.

The suspense number is useful for two reasons. First, it gives the outcome of a game; a position is winning when its suspense number is odd, and losing when its suspense number is even. Secondly, the suspense number plays nicely with the continued conjunction operation:

Rule: The suspense number of $G_1 \cc \dots \cc G_n$ is the maximum of the suspense numbers of the components.

Therefore, you can follow this action plan to solve your problem:

1. Work out the suspense numbers for a single tower of height $n$, for various small values of $n$. Continue doing this until a pattern (hopefully) appears.

2. Prove that the pattern holds by induction.

3. Use the rule to leverage this to give a general solution to the tower game.

Here is the start of doing task one:

Tower height	$1$	$2$	$3$	$4$	$5$	$6$	$7$
Suspense number	$0$	$1$	$2$	$3$	$3$

For example, here is how you work out that the suspense number of a five-high tower is $3$. There are two options; either a $(4,1)$ split or a $(3,2)$ split.

• For the $(4,1)$ split, we know from previously computed values that the two components games have suspense numbers of $3$ and $0$. By the rule, the suspense number of their combination is the maximum, $3$.

• For the $(3,2)$ split, we know from previously computed values that the two components games have suspense numbers of $2$ and $1$. By the rule, the suspense number of their combination is the maximum, $2$.

Since there is at least one option with even suspense, the suspense number is one more than the largest even suspense option, which is $1+2$, which is $3$ as claimed.