Pyramid puzzle

Many will be familiar with this puzzle which exists also as an online game; its rules are simple: you can only move one disc at a time and cannot place a disc over a smaller one. The objective is to move all discs from the C to the A position.

The entertainment value of such puzzles lies in the utter uselessness of the objective, and while it is deceivingly simple, attempting to solve it without a method leads to failure; I found an extremely elegant, recursive way to solve it and to calculate the number of moves it will take.

Obviously, moving the topmost disc from C to anywhere requires one move; moving the top two involves three moves:

  1. move the smallest disc to B
  2. move the second-smallest disc to A
  3. move the smallest disc from B to A

Since we know this, we can immediately determine that moving the top THREE discs requires 7 moves:

In fact, moving the top “n” discs always requires 2n-1 moves, allowing us to say that moving all 8 discs can be achieved in 28-1=255 moves.

The things I HAVEN’T demonstrated are WHY the number of moves is always a power of 2 minus 1 and whether this is the MINIMUM number of moves to achieve the solution.

Leave a Reply

Fill in your details below or click an icon to log in:

You are commenting using your account.Log Out / Change )

You are commenting using your Google account.Log Out / Change )

You are commenting using your Twitter account.Log Out / Change )

You are commenting using your Facebook account.Log Out / Change )

Connecting to %s