The Preliminary Probe of 4-Peg Hanoi Tower

Abstract

Abstract: In 1941,J.S.Frame gave out an algorithm in American Mathematical Monthly to solve the problem of 4-peg Hanoi Tower, but he did not provide the proof for the final formulae. According to that algorithm, this article puts forward a formula to calculate the number of movements necessary for the 4-peg Hanoi Tower problem, and proves it using mathematical induction.

Key words: 4-peg Hanoi Tower, zone, the number of remaining disks R(n)

摘要： 1941年，J.S.Frame在《美国数学月刊》上提出了一种解决四柱汉诺塔问题的算法，但未给出最终公式的证明。本文按照这种算法总结出完成四柱汉诺塔游戏之最少步数的公式，并用数学归纳法证明了它。

关键词: 四柱汉诺塔, 区, 剩余盘数R(n)

CLC Number:

O224

YANG Kai,XU Chuan. The Preliminary Probe of 4-Peg Hanoi Tower[J]. Acta Scientiarum Naturalium Universitatis Pekinensis.

杨楷, 徐川. 四柱汉诺塔之初步探究[J]. 北京大学学报（自然科学版）.

[1]	FENG Jun, YAN Jiyuan, ZHAO Xiaoxia. Preliminary Investigation on the Surface Ruptures of the Turkey M7.8 Earthquake on February 6, 2023 [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(6): 945-950.
[2]	WU Yazhen, LI Danyang, ZHANG Lin, DAI Hancheng. Modeling Study on the Impact of Climate Change on Air Pollution [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(5): 854-870.
[3]	CAO Jiyang, GONG Yue, LI Jiheng, PENG Hui. Integration of Towns and Industrial Zones in Pearl River Delta: A Case Study of Shishan and Songshanhu [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(3): 489-500.
[4]	ZHANG Feng, LU Sihua, LI Congyi, SHAO Min, LI Yue, LÜ Daqi, LI Xin, LIU Ying. Emission Characteristics of Intermediate-Volatility Organic Compounds in Petrochemical Industrial Area [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(2): 281-289.
[5]	LI Yanchu, JING Jiwu, LEI Lingguang, WANG Yuewu, WANG Pingjian. An iRAM-based Light-Weight Cryptographic Algorithm Implementation Scheme against Physical Memory Disclosure Attacks [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2022, 58(6): 1023-1034.
[6]	YAO Yuan, YANG Zhousheng, JIANG Jinzhong, ZHOU Shiyong. Microseismicity in Central Xiaojiang Fault Zone, Yunnan: Application of PALM on Dense Seismic Network [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2022, 58(5): 829-838.
[7]	PEI Weilai, YANG Zhousheng, ZHOU Shiyong. Source Mechanisms of Small Earthquakes and Tectonic Stress Field in Xiaojiang, Yunnan [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2022, 58(4): 602-608.
[8]	LI Jiayin, ZHOU Ming, NING Miao, SHI Xurong, YAN Gang, MA Qiang, LU Keding. Characteristics and Source Apportionment of VOCs in Suzhou, China [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2022, 58(4): 771-781.
[9]	SHI Wenbin, QU Kun, YAN Yu, QIU Peipei, WANG Xuesong, DONG Huabin. Circulation Classification and Source Analysis of Summer Ozone Pollution in Chengdu [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2022, 58(3): 565-574.
[10]	WEI Chanjuan, MENG Jijun. Ecological Sensitivity Assessment and Spatial Pattern Analysis of Land Resources in China [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2022, 58(1): 157-168.
[11]	XU Nuanyin, LI Zhijian, ZENG Hui. Spatio-Temporal Dynamic Characteristics of Coupling and Coordination of Urbanization System: Case Study in the Coastal Zone of East China Sea [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2021, 57(3): 536-544.
[12]	CHEN Xinyue, YAO Xiaodong, ZENG Wenjing, WANG Wei. Spatial Pattern and Driving Factors of Soil Microbial Biomass Carbon in Grassland in Northern Agro-Pastoral Transition Zone [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2021, 57(2): 250-260.
[13]	DU Yunsong, HUANG Ran, WANG Xinlu, QIN Momei, ZHANG Wenxian, ZHANG Yuzhong, YANG Yao, ZHANG Wei, LUO Bin, HU Yongtao, Armistead G. Russell. Implementing Reduced Form Model to Construct Ozone Isopleths and Its Application [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2021, 57(2): 311-321.
[14]	YANG Xiuyun, GAO Yishen, CHENG Ying, WANG Hongya, LIU Hongyan. Response of Different Altitude Vegetation to Climate Change in Taibai Mountain Alpine Zone during the Past about 2000 Years [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2020, 56(5): 844-854.
[15]	QU Ping, LÜ Jie, GUO Zhen, YU Yong, CHEN Yongshun. Study on Crust and Upper Mantle Structure in Shandong Area [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2020, 56(4): 649-658.

The Preliminary Probe of 4-Peg Hanoi Tower

四柱汉诺塔之初步探究

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics