Let's say you have a variant of The Tower of Hanoi, where you have $4$ pegs and $4$ discs. The formula for $3$ pegs and $n$ discs is $2^n-1$ but how would you work out the minimum number of moves in which a variant with $4$ pegs and $4$ discs can be calculated?
At first I figuered you can just ignore one of the pegs and use the normal formula but I realized that with $4$ pegs, the tower can be solved in a less number of moves. And now I'm not sure.
Best Answer
I was actually doing this in my head to pass time on an aeroplane. The formula for any tower of Hanoi where the number of pegs and number of disks is the same is: 2n+1 or “2(n-1)+3”.
So 4 pegs and 4 disks the minimum number of moves would be 9.
To visualise why; The first step ‘n-1 moves’ is where you lay them out so all pegs are holding one disk.
The second step is to move the smallest disk out of the way, place the largest disk in that position, then move the smallest disk onto the now empty spot. ‘+3’
You now have all disks on individual pegs again but this time the base is in the final position and you can put the remaining disks into the final position for one move each ‘n-1 moves’.
Bonus: (x = peg number) (Y=minimum disk moves)
If x=3 then Y=(2^n)-1
IF n is less than x then Y=2n-1. [“2(n-1)+1”]
IF n=x then Y=2n+1 [“2(n-1)+3”]
I won’t spoil the fun of working out the formula for 4 pegs on your own but I will hint that;
A) Solving for n being one greater than x is what made me realise how to solve for an arbitrary number of pegs and disks.
B) (hint hint) You can group sets of moves together and treat moving the sets as one move. Ie ‘2n-1’ is unstacking and re-stacking a set of n-disks to a new peg.
I have no mathematical background so I can’t give specific terminology but I hope this is what you were after.