7
$\begingroup$

We have 4 towers of cubes, each tower has one or more cubes (at least one). Two players play against each other. Each player in turn removes one cube from one of the towers, or two cubes from two towers - one from each tower of his choice. The game ends when the height of all towers is 0 (no more cubes). Wins the player who makes the last move.

What strategy for winning the game could be developed?

$\endgroup$
  • 1
    $\begingroup$ Welcome to Math SE. What have you tried? What are your thoughts on this problem? $\endgroup$ – Alain Remillard Dec 2 '19 at 18:09
  • $\begingroup$ Are you familiar with impartial games like Nim? This is Nim in disguse. The challenge is figuring out the disguise. If somebody takes two cubes, are they required to come from different towers? $\endgroup$ – Ross Millikan Dec 2 '19 at 19:36
6
$\begingroup$

Assuming that if a player takes two blocks they must be from different towers, then:

If

A) the smallest tower has an even number of blocks, and the other towers either all have an even number of blocks or all have an odd number of blocks,

then the player whose turn it is must lose against best play by the other side. Otherwise the player whose turn it is will win with best play. (If more than one tower is tied for smallest, arbitrarily designate one as the smallest.)

The proof is by strong induction on the total number of blocks. Designate the player whose turn it is as Player 1, and the other as Player 2. If the total number of blocks is zero, then Player 1 automatically loses, and condition A is satisfied, so the proposition is true in this case.

For the induction step, let the total number of blocks be greater than zero, and assume the proposition is true for all positions with a smaller total number of blocks. Then in particular it will be true for all positions reachable from the given position. We have three cases:

Case I: the smallest tower has an odd number of blocks. Then condition A is not satisfied. The player whose turn it is takes one block from the smallest tower, and if necessary takes one block from one of the other three towers to make them all even or all odd. The new position satisfies condition A, and by the inductive hypothesis Player 2 must lose, therefore in the original position Player 1 will win.

Case II: The smallest tower has an even number of blocks, but condition A is not satisfied. Then either two of the other three towers are even and one is odd, or two are odd and one is even. In either case, by removing a block from either one or two of the other towers, Player 1 can make them all odd or all even without making any of them smaller than the smallest tower. The new position satisfies condition A, so as in case I, Player 1 wins.

Case III: Condition A is satisfied. If Player 1 takes a block from the smallest tower, or a tower equal in size to this tower, then the smallest tower will now be odd, and condition A will no longer be satisfied. Otherwise, Player 1 must take a block from one or two of the other three towers. In the resulting position the smallest tower will still be smallest, and either two of the other three towers will be even and one odd, or two of them will be odd and one even. Thus condition A will again not be satisfied. So whatever move Player 1 makes, the resulting position will not satisfy condition A, and by the inductive hypothesis Player 2 will win. Thus Player 1 must lose.

In each of these cases, the proposition holds. Thus the inductive step is valid, and the proof is complete.

$\endgroup$
  • 1
    $\begingroup$ Very tiny simplification: In case II, you can always make all the towers be even, which always satisfies the condition. $\endgroup$ – Matt Dec 3 '19 at 14:09
  • $\begingroup$ Nice solution! If there are five towers, it appears the losing positions are those that look like EEEEE, EEOOO, OOEEO, or OOOOE when sorted in increasing order (E = even, O = odd). I wonder if there is a nice pattern as the number of towers increases. Is it always true that the outcome of a position is determined solely by the parities of the sorted list of tower sizes? $\endgroup$ – Mike Earnest Dec 3 '19 at 18:14

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.