Abstract
The star puzzle is a variant of the classical Tower of Hanoi problem, where, in addition to the three pegs, S, P and D, there is a fourth one such that all disc movements are either to or from the fourth peg. Denoting by MS(n) the minimum number of moves required to solve the star puzzle, MS(n) satisfies the following recurrence relation: { } 1 k n 1 MS(n) min 2MS(n k) 3 1 . k ≤ ≤ − = − + − This paper studies more closely the above recurrence relation and gives some new relationships, including some local-value relationships.
