Variation on the similar-size disk tower of hanoi puzzle

International Seminar on Mathematics, Science, and Computer Science Education 2016

数学;自然科学;计算机科学

Zuchri, S.^1

SMP Negeri 1 Batujajar, Jl. SMP No 12, Batujajar, Bandung Barat

40561, Indonesia^1

关键词: Different sizes;    Tower of Hanoi;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/812/1/012079/pdf
DOI  :  10.1088/1742-6596/812/1/012079

来源: IOP

【 摘 要 】

The famous Tower of Hanoi puzzle was invented by Edouard Lucas in 1883. This puzzle proposed three pegs, and the number of disks with different size. The puzzle starts with the disks in a neat stack in ascending order of size on one peg, the smallest at the top. The objective of the puzzle is to move the entire stack to another peg, by following these simple rules: (1) only one disk can be moved at a time; (2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack; (2) No disk is placed on the top of a smaller disk and the minimum number of move is the goal of this puzzle. Many variations have been proposed as exercises and challenges. Some have more than three pegs and some with colours. This paper poses a new variation. There are two or more disks with similar size. The goal is to move each stack of the disk from its initial location to its final location. As usual, disk must be moved one at a time and a disk can never sit above a disk of smaller. Let n be a number of disks and there are p similar size disks. The disks are labelled from 1 to n - p + 1 in increasing order of size so the disk with similar size has the same label. If m is the label of the similar disks, so Mp(n; m) is the minimum number moves needed to move all the disks in original peg to destination peg. We have, M2(n; m) = 2n-1+ 2n-m-1- 1 M3(n; m) = 2n-2+ 2n-m-1- 1 Mp(n; m) = 2n-p+2+ (p-1)2n-m-p+1- 1 The number moves needed to move if there are p1similar size disks m1and p2similar size disks m2is Mp1,p2(n; m1, m2) = 2n-p1-p2+ 2[(p12-m1+ p22-m2) - (2-m1+ 2-m2+ 1] - 1