## Problem of the Day #304: Towers of Hanoi
*January 17, 2012*

*Posted by Alex in : potd , trackback*

This problem features a variation on the traditional Towers of Hanoi puzzle. Suppose we have two pegs and $7$ discs of size $1$, $2$, $3$, $4$, $5$, $6$, and $7$. Disc $7$ is under disc $6$, which is under disc $5$, and so on, all on the same peg. A disc of size $x$ can only be placed on top of a disc with size $x + k$, where $k$ is a positive odd integer. One step consists of moving a disc from one peg to another peg. The puzzle is solved when all the discs are moved from one peg to another. How many pegs must be added before the puzzle can be solved, and what is the length of the shortest sequence of steps needed to solve the puzzle?

## Comments»

show