Can you prove that this puzzle game is always solvable?

Asked by PhiNotPi (12677) February 24th, 2013

There is a puzzle game that involves moving disks between stacks.

At the beginning, there are three stacks of disks. Each stack could initially have any number of disks, but each stack has at least one disk.

Each move consists of picking a set of two out of the three stacks. Disks are then moved form the larger stack to the smaller stack, as to exactly double the size of the smaller stack. This process generally means that there are three possible moves at any one time.

The game is won once at least two of the three stacks contain an equal number of disks.

Example game:
5, 7, 6
10, 7, 1 #stack 3 to stack 1
3, 14, 1 #stack 1 to stack 2
2, 14, 2 #stack 1 to stack 3
Game won

Is this puzzle game always winnable? Can you prove it? What is a general strategy to win?

This puzzle is adapted from a USAMTS competition. Supposedly, the game is in fact always winnable, regardless of the starting configuration. I didn’t manage to prove it before the submission deadline. Now I pose this question to you.

Observing members: 0 Composing members: 0

Response moderated