WorksMathematics
Hanoi tilings with a prescribed number of bottom squares
Abstract
For each fixed integer , every sufficiently large integer square admits a Hanoi tiling with exactly squares on its bottom edge. We construct nearly equal columns from two coprime widths and prove a rectangle lemma to fill their remaining height.
A tiling for each sufficiently large square
Theorem 1.1. For every fixed integer , every sufficiently large integer square has a tiling by integer-sided squares with exactly on the bottom. The entire lower edge of every other tile rests on strictly larger tiles.
Proof. Take relatively prime squarefree , with for , where is the sum of positive divisors. Indeed, the divergence of lets us select two disjoint finite sets of primes with in each. Their respective prime products work.
For each list the divisors . Stop immediately before the first partial sum that reaches . Call the sum so far and its last term . The deficit satisfies . The first three terms sum to at most , so at least three terms have been included and .
Write with every . Choose the first widths as nearest multiples of . For the penultimate width choose a multiple of congruent to (mod ), nearest to . The Chinese remainder theorem bounds this error by . The remaining width is a multiple of and has bounded error too. All widths are positive for large .
In a column of width , stack full rows with square sides . Each side divides and the first row is a single square. The remaining height is
The parenthesis stays bounded, so eventually and . A Hanoi tiling of the top -by- rectangle exists by the lemma below. Each cap tile resting on the last complete row has side at most . Putting the columns together proves the theorem. The at-least-one version also follows by taking . □
For a small example, split a 60-square into two columns of width 30. In each, use full rows of sides 30, 15, 10, 5. Their heights sum to 60 and their respective row counts are 1, 2, 3, 6.
Lemma 1.2. A height and width suffice for a rectangular Hanoi tiling in this orientation.
Proof. A bottom square of width makes a usable strip if and the -wide cap of height is tilable. Height zero needs no tiles, height one admits all positive widths, and height two admits even widths. For , the accompanying exact recurrence starts at width zero and adds every usable strip width. It checks the consecutive widths beginning at . Adding width- strips extends the result indefinitely. For , induction makes every integer strip width in usable. The intervals cover every integer from onward, since . Also . Both estimates follow from .
Erich Friedman posed the fixed-base question. His original page credits Dean Hickerson and describes the stronger wide-rectangle lemma used in their earlier unprescribed-base results [1, 2].
Finite check for the rectangle lemma. For put and let be true when there is a usable with . Here is usable when , , and the upper rectangle of width and height is available from a smaller height. The certificate stores one such at each certified pair . Extract cap_certificates.py and hanoi-caps.json together from the supplementary files to check every decomposition. The second Python program calculates reachability independently.
References
References
- [1]E. Friedman, Problem of the month, November 2003, Math Magic, original problem and previous constructions.
- [2]E. Friedman, Unsolved problems from Math Magic, questions 9 and 30, problem list.