On a Recurrence Relation Related to The Reve’s Puzzle

Abstract

The 4-peg Tower of Hanoi problem, commonly known as the Reve’s puzzle, is well-known. Motivated by the optimality equation satisfied by the optimal value function M(n) satisfied in case of the Reve’s puzzle, (Matsuura et al. 2008) posed the following generalized recurrence relation

T(n, a) = min {aT(n-t, a)+S(t,3)}

            1≤ t ≤ n

where n ≥ 1 and a ≥ 2 are integers, and S(t, 3) = 2^t – 1 is the solution of the 3-peg Tower of Hanoi problem with t discs. Some local-value relationships are satisfied by T(n, a) (Majumdar et al. 2016). This paper studies the properties of  T(n+1, a) – T(n, a) more closely for the case when a is an integer not of the form 2ⁱ for any integer i ≥ 2.

Journal of Bangladesh Academy of Sciences, Vol. 42, No. 2, 191-199, 2018