Title

Knuth's (1, 2, 1) Unstacking

Authors

Paul J. ZwierFollow

Document Type

Conference Proceeding

Publication Date

6-6-1993

Abstract

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.

Recommended Citation

Zwier, Paul J., "Knuth's (1, 2, 1) Unstacking" (1993). ACMS Conference Proceedings 1993. 6.
https://pillars.taylor.edu/acms-1993/6