The first thing I notice is that for each extra disc you can find the number of moves by doubling the number needed for the previous disc and the adding one.
So for four discs I predict I will take 15 moves as that would be the next result in the pattern.
Four Discs
- Four Discs = Fifteen Moves
Predictions and Pattern One (Part 2)
I was correct. Four discs require a minimum of fifteen moves. Now I have confirmed this theory I can try and work out why it works.
Let’s look more closely at the three discs puzzle:
- We start off by moving two discs onto another stack using the method in the two discs puzzle. (Three Moves – The Two Disc Puzzle)
- We then move the base disc. (One Move)
- Finally we move the tower of two onto the base using the same method as the two disc puzzle and the first step to solving this puzzle. (Three Moves – The Two Disc Puzzle)
This shows how our patterns are created.
We can see the same pattern for four discs:
- First we moved the top three discs onto another stack (Seven Moves – as in The Three Disc Level)
- We the move the base disc. (One Move)
- Then we move the three disc tower back on top of the base. (Seven Moves – as in the Three Disc Version)
So we can predict that for Five Discs we will need thirty one moves. The only problem with this is that if I want to find out how many moves with ten discs I must know how many moves nine discs take and to know that I must know how many moves eight discs take and so on. This means this method may not be the best one.
Predictions and Pattern Two
Our results so far:
- One disc = One move
- Two discs = Three moves
- Three discs = Seven moves
- Four discs = Fifteen moves
A way I often look for patterns is to look at the between results. I this case we get:
This is a clear pattern of a doubling difference. This could also be seen as powers of two.
-
Two = 21
-
Four = 22
-
Eight = 23
Both patterns predict thirty one moves for five discs.
Five Discs
- Five Discs = Thirty-One Moves
Predictions and Pattern Two (Part 2)
Our prediction was correct again. So now we have a method which does not need to know how many discs were used last time we can create a formula using powers of 2.
So now we have some patterns emerging in these formulas. We can put them together to say that when:
- n is the number of discs we’re using
The number of moves taken is:
2n - 1
This is good to have found out but why does it happen like this?
Pattern Two (Part 3)
How about tracking how many moves each disc makes? For example the largest disc moves only once.
Each disc moves exactly the same number of times no matter how many discs there are. Discs 2 takes double the moves of Disc 1 and Disc 5 takes double the moves of Disc 4. Disc n moves 2n-1 times.
Four Poles
The next challenge with this puzzle is to use four poles (or stacks) instead of three. The rules are exactly the same as before.
One Disc
With only one disc having four poles changes it nothing it still only takes one move.
Two Discs
Again two discs in no different to with three poles.
Three Discs
At three discs having four poles makes a difference.
Four Discs
Five Discs
- Five Discs = Thirteen Moves
Six Discs
- Six Discs = Seventeen Moves
Predictions and Pattern Three (Part 2)
So far we have seen no obvious patterns. One thing I tried was to subtract the number of moves required for 4 poles from that you needed for three poles. Again the numbers 0, 0, 2, 6 and 18 have no obvious pattern. After a lot of experimenting I realised that as 3 Poles used powers of two in the answer then four poles might use powers of three. This is what I came up with:
-
31 – 30 = 2
-
32 – 31 = 6
-
33 – 32 = 18
This also works for:
-
30 – 3-1 = 0
-
3-1 – 3-2 = 0
This comes out as:
So what is the actual formula?
We have:
We can rearrange this as:
So for 4 discs are formula is:
by Gregory Auger
