Some Local-value Relationships Related to the Star Puzzle
Local-Value Relations for the Star Puzzle
Keywords:
Star puzzle, three-in-a-row puzzle, recurrence relation, local-value relationshipsAbstract
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.
References
Stockmeyer, Paul K. Variations on the four-post tower of Hanoi puzzle. Congressus Numerantium 102: 3–12 (1994).
Scorer, J.S., P.M. Grundy & C.A.B. Smith. Some binary games. The Mathematical Gazette 280: 96–103 (1944).
Majumdar, A.A.K. The Classical Tower of Hanoi Problem and Its Generalizations, Vol. 2: Other Generalizations. Lambert Academic Publishing, USA (2013).
Majumdar, A.A.K. Some local-value relationships for the recurrence relation related to the Tower of Hanoi Problem. Proceedings of the Pakistan Academy of Sciences, A. Physical and Computational Sciences 53(2): 187−201 (2016).
Matsuura, A. Exact analysis of the recurrence relations generalized from the Tower of Hanoi. SIAM Proceedings in Applied Mathematics 129: 228–233 (2008).
