betaFeedback

WorksMathematics

Hanoi tilings with a prescribed number of bottom squares

Abstract

For each fixed integer k≥2k\geq 2, every sufficiently large integer square admits a Hanoi tiling with exactly kk 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 k≥2k \ge2, every sufficiently large integer square has a tiling by integer-sided squares with exactly kk on the bottom. The entire lower edge of every other tile rests on strictly larger tiles.

Proof. Take relatively prime squarefree DD, EE with σ(d)>kd\sigma(d)>kd for d=D,Ed=D,E, where σ\sigma is the sum of positive divisors. Indeed, the divergence of ∑p1/p\sum_p 1/p lets us select two disjoint finite sets of primes with ∏p(1+1/p)>k\prod_p(1+1/p)>k in each. Their respective prime products work.

For each dd list the divisors d=t1>t2>⋯d=t_1>t_2>\cdots. Stop immediately before the first partial sum that reaches kdkd. Call the sum so far SS and its last term tt. The deficit R=kd−SR=kd-S satisfies 1≤R≤tnext<t1\le R\le t_{\mathrm{next}}<t. The first three terms sum to at most d+d/2+d/3<2dd+d/2+d/3<2d, so at least three terms have been included and t≤d/3t\le d/3.

Write n=w1+⋯+wkn=w_1+\cdots+w_k with every wj=n/k+Ok(1)w_j=n/k+O_k(1). Choose the first k−2k-2 widths as nearest multiples of DD. For the penultimate width choose a multiple of DD congruent to n−∑i=1k−2win-\sum_{i=1}^{k-2}w_i (mod EE), nearest to n/kn/k. The Chinese remainder theorem bounds this error by DEDE. The remaining width is a multiple of EE and has bounded error too. All widths are positive for large nn.

In a column of width w=dqw=dq, stack full rows with square sides qt1,…,qtqt_1,\ldots,qt. Each side divides ww and the first row is a single square. The remaining height is

H=n−qS=qR+(n−kw).H=n-qS=qR+(n-kw).

The parenthesis stays bounded, so eventually 3≤H<qt3\le H<qt and w/H→d/R>3w/H\to d/R>3. A Hanoi tiling of the top ww-by-HH rectangle exists by the lemma below. Each cap tile resting on the last complete row has side at most H<qtH<qt. Putting the kk columns together proves the theorem. The at-least-one version also follows by taking k=2k=2. □

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 h≥3h \ge3 and width w≥⌈5h/2⌉w \ge\lceil5h/2 \rceil suffice for a rectangular Hanoi tiling in this orientation.

Proof. A bottom square of width s≤hs \le h makes a usable strip if h−s<sh-s < s and the ss-wide cap of height h−sh-s is tilable. Height zero needs no tiles, height one admits all positive widths, and height two admits even widths. For 3≤h<1003 \le h < 100, the accompanying exact recurrence starts at width zero and adds every usable strip width. It checks the hh consecutive widths beginning at ⌈5h/2⌉\lceil5h/2 \rceil. Adding width-hh strips extends the result indefinitely. For h≥100h \ge100, induction makes every integer strip width in [a,b]=[⌈5h/7⌉,h−3][a,b]=[\lceil5h/7 \rceil,h-3] usable. The intervals [ja,jb][ja,jb] cover every integer from 3a3a onward, since 3b+1≥4a3b+1 \ge4a. Also 3a≤⌈5h/2⌉3a \le\lceil5h/2 \rceil. Both estimates follow from a≤(5h+6)/7a \le(5h+6)/7. □\square

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 h≥3h \ge3 put Th(0)=1T_h(0)=1 and let Th(w)T_h(w) be true when there is a usable s≤ws \le w with Th(w−s)=1T_h(w-s)=1. Here ss is usable when 1≤s≤h1 \le s \le h, h−s<sh-s < s, and the upper rectangle of width ss and height h−sh-s is available from a smaller height. The certificate stores one such ss at each certified pair (h,w)(h,w). 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. [1]E. Friedman, Problem of the month, November 2003, Math Magic, original problem and previous constructions.
  2. [2]E. Friedman, Unsolved problems from Math Magic, questions 9 and 30, problem list.

Paper details

vlnc:W_bxj7p9vc
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents