This presentation is dedicated to Donald Knuth who has proposed many interesting and challenging problems in the Problems Section of The American Mathematical Monthly. The problem considered ist hat proposed by Barry Hayes, Knuth, and Carlos Subi (E3267 [1988,456]). The published solution, due to Albert Nijenhuis, just recently appeared in the March 1993 Monthly, pages 292-294.
The problem is as follows. Suppose that we are given n piles of blocks; the i-th pile having ai blocks, i = 1, 2, …, n. Dismantle the piles by choosing a pile having 2 or more blocks, removing 2 blocks and putting one block on the pile on the left and one block on the pile on the right. Continue the process until there are no more piles having more than one block. What is the final configuration like and how many moves are required?
My solution differs from that of Nijenhuis in that it pays closer attention to the evolution of the piles as the dismantling progresses. I also generalize to the (s, 2s, s) unstacking, where s ≥ 1.
Zwier, Paul J., "Knuth's (1, 2, 1) Unstacking" (1993). ACMS Conference Proceedings 1993. 6.
Applied Mathematics Commons, Computer Sciences Commons, Higher Education Commons, History of Science, Technology, and Medicine Commons, Mathematics Commons, Science and Mathematics Education Commons, Teacher Education and Professional Development Commons