Problem of the Month (November 2009)

This month we examine a famous problem involving elevators. Suppose there are e elevators in a building, and each one stops at s of the floors. We call a building convenient if you can get from any floor to any other floor without changing elevators. What is the maximum number of floors f(e,s) of a convenient building? For example, f(4,3)≥5 since the 4 elevators could stop at floors {1,2,3}, {1,2,4}, {1,2,5}, and {3,4,5}. To see that f(4,3)<6, notice the elevators only make 4×3=12 stops, so some floor will only be visited by at most 2 elevators, and that floor will not be accessible from every floor. What are the values of f(e,s)? What can be proven about the function f(e,s)?

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?


ANSWERS

It is easy to see f(e+1,s) ≥ f(e,s), since an extra elevator can't hurt, and f(e,s+1) ≥ f(e,s)+1, since the extra stop for each elevator can be a new floor. It is harder to see that f(e,ks) ≥ k f(e,s). To do so, pile k copies of a convenient building with f(e,s) floors on top of one another, and link the corresponding elevators so that each stops at ks 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.

Maximum number of floors with e elevators and s stops
e \ s12345678910111213141516
1 12345678910111213141516
2 12345678910111213141516
3 13467910121315161819212224
4 13568101113
5 13579101214
6 1468101214161820222426283032
7 14781114182125283235
8 1479
9 14710
10 15710
11 158
12 15918273645
13 15913263952
14 159
15 169
16 169

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(s2-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(s2+s,s)=s2 buildings exist. Both Evert Stenlund and Dave Langers then showed that omitting an elevator from a perfect f((s+1)2-(s+1)+1,s) building along with all floors that it visits constructs a perfect f(s2+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 pn 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.