We call a building perfect if each pair of floors is linked by exactly one elevator. The only perfect buildings known are the trivial e=1 and s=k, and e=k(k-1)/2 and s=2, and the non-trivial pairs e=7 and s=3, e=12 and s=3, and e=13 and s=4. Can you find the designs of these perfect buildings? Can you find any others? Are there many other perfect buildings if we relax the rule that every elevator has to visit the same number of floors, but insist that every elevator visits at least 3 floors?

Another very useful upper bound for f(e,s) is given by f(e,s)(f(e,s)–1)/(s–1) ≤ es. This comes from the fact that we need at least (f(e,s)–1)/(s–1) elevators to visit each floor.

Jeremy Galvagni gave the lower bound f(e,s) ≥ 1/2 + √(2es + 1/4) that comes from the fact that f(e,s)[f(e,s)–1]/2 ≥ es.

Jeremy Galvagni also noted that if x<y, then f(x,y) ≤ f(y,x).

Here are some more general results:

f(1,s) = s
f(2,s) = s
f(3,2k) = 3k
f(3,2k+1) = 3k+1
f(6,s) = 2s (for s≥2)
f(7,3k) = 7k
f(7,3k–1) = 7k–3
f(12,3k) = 9k
f(13,4k) = 13k

f(e,1) = 1
f(e,2) = 1/2 + √(2e+1)

The known specific results are summarized in the table below. The results shown in black come from David Rhee and Jerry Lo, who wrote a survey paper on this problem in the marvelous book "Mathematical Wizardry for a Gardner". The results shown in red are my contributions. The blue results are due to Jeremy Galvagni.

Jeremy Galvagni found perfect elevator designs for f(7,3) and f(12,3). Joe DeVincentis found perfect elevator designs for f(7,3), f(12,3), and f(13,4).

Joe DeVincentis generalized the perfect f(7,3) and f(13,4) buildings to perfect f(s²–s+1,s) buildings for all s. He also showed that e=f(f–1)/s(s–1) and (f–1)/(s–1) need to be integers for a perfect building. Based on this, he conjectured that perfect f(s²+s,s)=s² buildings exist. Both Evert Stenlund and Dave Langers then showed that omitting an elevator from a perfect f((s+1)²–(s+1)+1,s) building along with all floors that it visits constructs a perfect f(s²+s,s) building.

Dave Langers noticed that if there are perfect f(d,s) and f(e,s) and these numbers are coprime, then there is some perfect f(c,s) = f(d,s) f(e,s). Therefore if there is a perfect building with a prime p number of floors, there is a prefect building with pⁿ floors for any number n.

Evert Stenlund found perfect elevator designs for f(20,4) and f(21,5), shown below:

   

Dave Langers also gave designs for perfect f((2n+1)(3n+1,3)=6n+3 buildings (derived from Bose) and perfect f(n(6n+1),3)=6n+1 buildings (derived from Skolem). Thus the only small cases to resolve are f(50,4)=25, f(63,4)=28, f(69,6)=46, f(82,5)=41, f(85,6)=51, and f(99,5)=45.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 11/13/09.