Season 12 Episode 0

We're back from our break, and Ayliean joins us again on OOMC with everything you've ever wanted to know about the Tower of Hanoi.

Watch on YouTube

Further Reading

Oxford Maths Festival

Just in case anyone is in the Oxford area on Saturday 09 May, the Oxford Maths Festival is a free event that we run for families. On Saturday we’re at Templars Square Shopping Centre (East Oxford), and on Sunday we’re in the Mathematical Institute itself. 

Tetris

Ayliean is one of the generators of Finite Group, a mathematical community run jointly with Katie Steckles, Peter Rowlett, and Matthew Scroggs. Scroggs has recently made Wordle-Tetris and Wordle plays Pokemon which we mentioned at the start of the episode. Ayliean has made a short video about Wordle-Tetris.

There also exists 3D Tetris, in the form of a web game, for example this one. Note that there are three sorts of rotation. Good luck! There was also a version of 3D Tetris released in the 90s for Nintendo’s Virtual Boy, a largely unsuccessful early VR device. If you’ve got that then (a) wow and (b) good luck.

Tower of Hanoi

Ayliean was on Numberphile a fewyears ago with the Tower of Hanoi; Key to the Tower of Hanoi | Numberphile | YouTube .

We saw the fantastic Hanoi graph for all the positions  https://mathworld.wolfram.com/HanoiGraph.html

Here's the alternative challenge that Ayliean mentioned; with alternating pink/white discs, all starting on the left peg, we want to get to a state where the pink discs are all on the middle peg and the white discs are all on the right peg.

We mentioned that the “scenic route” is called a Hamiltonian path (a path that visits every vertex exactly once). There’s also something called a Hamiltonian cycle where you visit every vertex and get back to where you started, in a sort of loop. So the obvious question is; is there a Hamiltonian cycle for the Hanoi graph? Can you visit every position of the Towers of Hanoi and then with just one last move reset the puzzle to the starting position?

ABACABADABACABA

One place that you might see the pattern 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 is the "largest power of 2 that divides each number". That’s got the ABACABA shape to it too! The OEIS sequence that we saw on OOMC is a version of this with powers of 3 instead of powers of 2. Note that this includes an additional factor of 3 in the definition (“divides exactly $3n$” rather than $n$) and this sequence lists the exponent, not the actual power of 3.

Someone in chat mentioned the Vi hart Doodling in Maths Class: DRAGONS video. The ABACABA pattern governs which way the creases fold for a dragon curve made by folding a sheet of paper.

The L-shaped tiles that were on screen briefly are an example of a rep-tile (an excellent name for a tile that can be made out of repeats of itself).

There’s a semi-famous problem with these L-shaped tiles, and you’ve basically seen the solution on OOMC so we might as well state the question now.

Question; given a $2^n$ by $2^n$ chessboard and a large supply of L-shaped tiles (each covers three squares), suppose a random square on the chessboard is chosen. Can you cover the remaining $4^n-1$ squares with the tiles, no overlap, no other squares missed out?

The answer is one of "yes, always" or "no, never", or "maybe, sometimes".

Four pegs

You can play with Tower of Hanoi with up to 16 pegs at this website.

With four pegs, this is called Reve’s puzzle and there's an algorithm for it called the Frame–Stewart algorithm. This algorithm was proposed in 1941, but it was only proved in 2014 by Thierry Bousch that it's the optimal solution for four pegs.

These slides have the diagram for four pegs and four discs, which we thought about briefly on OOMC The Dudeney Algorithm | PDF.

With five or more pegs, no-one knows what the optimal solution is.

Gray codes

You might also be interested in the idea of a "Gray code". Consider the binary numbers $$000,\quad 001,\quad 010,\quad 011,\quad 100,\quad 101,\quad 110,\quad 111,$$ where I’ve made the slightly unusual choice to include zeros at the front of the number, so that they’re all three digits. Can you rearrange these numbers so that, for any pair of consecutive numbers, exactly one digit changes?

These have an application, because if you count in this weird order, then you can detect errors by looking out for occasions where two numbers change.

Spoilers for the question above on the Wikipedia page. Gray codes are named after Frank Gray, not the colour grey.