Tower of Hanoi, the Hard Way

The rules of the game don't prohibit silly moves like moving the little ring from one peg to another and then back again, i.e. wasting two moves, but if you want to solve the game with as few moves as possible you don't want to waste moves.

A variation of the game is to solve the game using as many moves as possible without returning to a previous configuration of the rings.

One way of doing this is:

Solve(N, Src, Aux, Dst)
    if N is 0 
      exit
    else
      Solve(N-1, Src, Aux, Dst)
      Move from Src to Aux
      Solve(N-1, Dst, Aux, Src)
      Move from Aux to Dst
      Solve(N-1, Src, Aux, Dst)

This uses 3ⁿ - 1 moves. You can describe any configuration of n rings on three pegs as an n-digit number with the digits 0, 1 and 2 and conversely you can convert any such n-digit number into a configuration of the n rings. Thus there are 3ⁿ different configurations and so you can at most use 3ⁿ - 1 different moves to move the pegs without repeating any configuration.

So we have just proved that this is indeed the best way of wasting time.