Elevator Math!
by greenturtle3141, Apr 5, 2024, 8:30 PM
Reading Difficulty: 1.5/5
Can you solve a real life math puzzle?
I currently I live in an apartment complex for my PhD program. My apartment building has
floors: 
("Terrace"), 
("Mezzanine"), 
, 
, 
and 
. Since it's a tall building, there are two elevators.
One day, I called an elevator and stepped in, but forgot to press a button to tell it to go to another floor. The elevator proceeded to automatically go to the Terrace. Interesting. This elevator seems to have a default floor:, that it goes to whenever it thinks nobody is using the elevator.
I guess it made sense for one elevator to default to the bottom-most floor. What about the other elevator? After stepping outside and messing around a bit, it was clear that the other elevator also had a default floor.
What floor does the other elevator default to when nobody is using the elevators?
(It may seem like you have basically no information to work with, and that's true! In real life, we often have to make some reasonable assumptions before math can be done. Good luck!)
Elevator math!
Alright let's get some math done.
The floor names are annoying so let's rename them to
. Then the default floor of the "first elevator" is 
and the default floor of the "second elevator" is 
, and we want to solve for such that travel time is optimized.
Choose a floor
from these 13 floors uniformly at random. Take a resident of floor that wants to use the elevators at some random point in the day. There are two cases.
Thus the expected travel time given a random resident at a random time of day (in terms of how many floors the elevator they use needs to travel) is
![$$\mathbb{E}\left[\frac12 \cdot X + \frac12 \cdot \left(\min(|a-X|, |X-0|) + X\right)\right].$$](//latex.artofproblemsolving.com/b/f/3/bf3a7da9dd55c895c97ef6866952bb9cd9fc8b12.png)
We want to find the value of that minimizes this.
First, note that we can rewrite this as
![$$\mathbb{E}\left[X + \frac12 \cdot \min(|a-X|, |X-0|) \right].$$](//latex.artofproblemsolving.com/b/f/8/bf800708783702feb4713dfe7a807e41ce8b01b0.png)
This makes sense because no matter what, a resident of a floor will always have to travel at least floors. So all we need to do is minimize the expression
because the only thing we can try to minimize is how long it would take for the nearest elevator to reach floor . All other time expenses are inevitable.
Now, using the definition of expected value, we want to minimize the quantity
At this point there's not much we can do besides listing out the values of this sum over all .
So it looks like the sum is minimized when
or 
. In the original problem, this corresponds to floors 
and 
. So if you answered , you get partial credit!
...so why is the answer? Was it just arbitrary?
Continuous abstraction
Let's put that question aside and instead try to make some general assertions when there are more floors. If there were, say,
floors, what's a very good educated guess for where the second elevator should be?
Obviously I don't want to list out different values. But is such a big number that we can effectively study the problem by making a sort of abstract "idealization": Let's just pretend that there are uncountably infinite many floors!
That is, let's model the building as the interval![$[0,1]$](//latex.artofproblemsolving.com/e/8/6/e861e10e1c19918756b9c8b7717684593c63aeb8.png)
. We choose a random "floor" ![$X \in [0,1]$](//latex.artofproblemsolving.com/d/d/6/dd602078998bf052ef4b971897696c004e96ce51.png)
uniformly at random, and we now want to minimize the expected value of 
, where is where the second elevator is. The expected value is given by the integral
Integrals are so much easier to deal with than sums, which is why we're motivated to make this abstraction. To evaluate this, we split up into three intervals to get
This is minimized when 
! So the general heuristic is that the second elevator should be 
of the way up the building.
So, in a building with floors, numbered through 
, we should expect that the second elevator defaults to the floor of the way up, which is . In the original problem, this corresponds to floor . That's why is the most reasonable answer.
Even more elevators
Now, what if instead of just two elevators, there were actually
elevators? Again, just for the sake of heuristics, let's assume that the apartment building's floors are given by the interval .
I leave it as an exercise to show that one of the elevators has to be at floor (intuitively, this is because half the time, people are coming home, and placing one elevator at minimizes all their travel times). So it remains to place the other 
elevators.
Let's say that the other elevators are at floors
with 
. We can draw a graph of how much time it takes for the nearest elevator to get to you.
![[asy]
size(6cm);
real[] a = {0.1, 0.3, 0.4, 0.7, 0.85};
int n = a.length;
real L = 5;
path gr = (0,0)--(a[0]/2*L,a[0]/2*L)--(a[0]*L,0);
for(int i=0; i<n-1; ++i){
gr = gr--((a[i]+a[i+1])/2*L,(a[i+1]-a[i])/2*L)--(a[i+1]*L,0);
}
gr = gr -- (L, L*(1-a[n-1])) -- (L,0);
fill(gr--cycle, p=rgb(1,0.8,0.8));
draw(gr,p=red);
draw((0,0)--(5,0));
dot("$0$", (0,0), S);
label("$1$", (L,0),S);
for(int i=0; i<n; ++i){
dot("$a_"+((string) (i+1))+"$", (a[i]*L,0),S);
}
[/asy]](//latex.artofproblemsolving.com/3/a/c/3ac28a6db5cd3ba2a136be9a4892f9beac4c6841.png)
We're trying to minimize the area under the graph. This area is comprised of triangular "mountains" and more triangle at the very end.
Let's consider two adjacent mountains: The one between
and 
, and the one between and 
, for some 
.
The base of the first mountain is
, and the base of the second mountain is 
.
![[asy]
size(6cm);
path gr = (0,0)--(1,1)--(2,0)--(3.5,1.5)--(5,0);
fill(gr--cycle, p=rgb(1,.8,.8));
draw(gr, p=red);
draw((0,0)--(5,0));
label("$x$", (1,0), N);
label("$y$", (3.5,0),N);
dot("$a_i$", (2,0), S);
dot("$a_{i-1}$", (0,0),S);
dot("$a_{i+1}$", (5,0),S);
[/asy]](//latex.artofproblemsolving.com/b/1/4/b14145227fab9bba9127c033c80b896f74af0c89.png)
The combined area of the mountains is then
. Where could we move so that this is minimized?
Aha! We are trying to minimize subject to the constraint 
. By the QM-AM inequality, the minimum is obtained exactly when 
. Therefore, in the minimum configuration, each pair of adjacent mountains must be of the same size! Because otherwise, there must be two adjacent mountains with different sizes, and then we can move the point in between them so that their area goes down.
Let's update what the full graph looks like now.
![[asy]
size(6cm);
real[] a = {0.15, 0.3, 0.45, 0.6, 0.75};
int n = a.length;
real L = 5;
path gr = (0,0)--(a[0]/2*L,a[0]/2*L)--(a[0]*L,0);
for(int i=0; i<n-1; ++i){
gr = gr--((a[i]+a[i+1])/2*L,(a[i+1]-a[i])/2*L)--(a[i+1]*L,0);
}
gr = gr -- (L, L*(1-a[n-1])) -- (L,0);
fill(gr--cycle, p=rgb(1,0.8,0.8));
draw(gr,p=red);
draw((0,0)--(5,0));
dot("$0$", (0,0), S);
label("$1$", (L,0),S);
for(int i=0; i<n; ++i){
dot("$a_"+((string) (i+1))+"$", (a[i]*L,0),S);
}
[/asy]](//latex.artofproblemsolving.com/b/6/7/b678c07ca5c9431ddf60c574ac2a45fe4abbb6bf.png)
With the above positions for the elevators, we can't move
to make the area go down. So we can only move the elevator at the end, 
(in the above picture, this is 
).
Where do we move the final elevator to minimize the area of the two triangles next to it? We could do another QM-AM-type argument. But we actually don't have to do any work: We've done this before! This just reduces to the case with two elevators (restricted to just the interval![$[a_{n-2},1]$](//latex.artofproblemsolving.com/e/2/f/e2f57134cda208e0a2f722fbc429a7a7701f0e80.png)
)! So, it is optimal to put exactly of the way between 
and .
Therefore, in the optimal configuration, we must have
and
![[asy]
size(6cm);
real[] a = {2/11, 4/11, 6/11, 8/11, 10/11};
int n = a.length;
real L = 5;
path gr = (0,0)--(a[0]/2*L,a[0]/2*L)--(a[0]*L,0);
for(int i=0; i<n-1; ++i){
gr = gr--((a[i]+a[i+1])/2*L,(a[i+1]-a[i])/2*L)--(a[i+1]*L,0);
}
gr = gr -- (L, L*(1-a[n-1])) -- (L,0);
fill(gr--cycle, p=rgb(1,0.8,0.8));
draw(gr,p=red);
draw((0,0)--(5,0));
dot("$0$", (0,0), S);
label("$1$", (L,0),S);
for(int i=0; i<n; ++i){
dot("$a_"+((string) (i+1))+"$", (a[i]*L,0),S);
}
[/asy]](//latex.artofproblemsolving.com/c/9/6/c961a6e32f2d1298191629aad5ef7e79130f3b17.png)
Some basic algebra reveals the final answer: When there are elevators, it is optimal to place them at the following floors:
It's always a great joy to discover compelling and intricate mathematics in the wild!
Can you solve a real life math puzzle?
I currently I live in an apartment complex for my PhD program. My apartment building has
floors: 
("Terrace"), 
("Mezzanine"), 
, 
, 
and 
. Since it's a tall building, there are two elevators.One day, I called an elevator and stepped in, but forgot to press a button to tell it to go to another floor. The elevator proceeded to automatically go to the Terrace. Interesting. This elevator seems to have a default floor:
, that it goes to whenever it thinks nobody is using the elevator.I guess it made sense for one elevator to default to the bottom-most floor. What about the other elevator? After stepping outside and messing around a bit, it was clear that the other elevator also had a default floor.
What floor does the other elevator default to when nobody is using the elevators?
(It may seem like you have basically no information to work with, and that's true! In real life, we often have to make some reasonable assumptions before math can be done. Good luck!)
Elevator math!
Alright let's get some math done.
The floor names are annoying so let's rename them to
. Then the default floor of the "first elevator" is 
and the default floor of the "second elevator" is 
, and we want to solve for such that travel time is optimized.Choose a floor
from these 13 floors uniformly at random. Take a resident of floor that wants to use the elevators at some random point in the day. There are two cases.
- There is a
chance that this resident is coming home, in which case they start at floor and use the first elevator to go up floors. - There is a chance that this resident is leaving home, in which case they start at floor and call the nearest elevator, which has to travel
floors to reach floor , and then they use the elevator to go down floors.
chance that this resident is coming home, in which case they start at floor 
floors to reach floor Thus the expected travel time given a random resident at a random time of day (in terms of how many floors the elevator they use needs to travel) is
![$$\mathbb{E}\left[\frac12 \cdot X + \frac12 \cdot \left(\min(|a-X|, |X-0|) + X\right)\right].$$](http://latex.artofproblemsolving.com/b/f/3/bf3a7da9dd55c895c97ef6866952bb9cd9fc8b12.png)
We want to find the value of that minimizes this.First, note that we can rewrite this as
![$$\mathbb{E}\left[X + \frac12 \cdot \min(|a-X|, |X-0|) \right].$$](http://latex.artofproblemsolving.com/b/f/8/bf800708783702feb4713dfe7a807e41ce8b01b0.png)
This makes sense because no matter what, a resident of a floor will always have to travel at least floors. So all we need to do is minimize the expression
because the only thing we can try to minimize is how long it would take for the nearest elevator to reach floor . All other time expenses are inevitable.Now, using the definition of expected value, we want to minimize the quantity
At this point there's not much we can do besides listing out the values of this sum over all .
So it looks like the sum is minimized when
or 
. In the original problem, this corresponds to floors 
and 
. So if you answered , you get partial credit!...so why is the answer
? Was it just arbitrary?Continuous abstraction
Let's put that question aside and instead try to make some general assertions when there are more floors. If there were, say,
floors, what's a very good educated guess for where the second elevator should be?Obviously I don't want to list out
different values. But is such a big number that we can effectively study the problem by making a sort of abstract "idealization": Let's just pretend that there are uncountably infinite many floors!That is, let's model the building as the interval
![$[0,1]$](http://latex.artofproblemsolving.com/e/8/6/e861e10e1c19918756b9c8b7717684593c63aeb8.png)
. We choose a random "floor" ![$X \in [0,1]$](http://latex.artofproblemsolving.com/d/d/6/dd602078998bf052ef4b971897696c004e96ce51.png)
uniformly at random, and we now want to minimize the expected value of 
, where is where the second elevator is. The expected value is given by the integral
Integrals are so much easier to deal with than sums, which is why we're motivated to make this abstraction. To evaluate this, we split up into three intervals to get
This is minimized when 
! So the general heuristic is that the second elevator should be 
of the way up the building.So, in a building with
floors, numbered through 
, we should expect that the second elevator defaults to the floor of the way up, which is . In the original problem, this corresponds to floor . That's why is the most reasonable answer.Even more elevators
Now, what if instead of just two elevators, there were actually
elevators? Again, just for the sake of heuristics, let's assume that the apartment building's floors are given by the interval .I leave it as an exercise to show that one of the elevators has to be at floor
(intuitively, this is because half the time, people are coming home, and placing one elevator at minimizes all their travel times). So it remains to place the other 
elevators.Let's say that the other elevators are at floors
with 
. We can draw a graph of how much time it takes for the nearest elevator to get to you.![[asy]
size(6cm);
real[] a = {0.1, 0.3, 0.4, 0.7, 0.85};
int n = a.length;
real L = 5;
path gr = (0,0)--(a[0]/2*L,a[0]/2*L)--(a[0]*L,0);
for(int i=0; i<n-1; ++i){
gr = gr--((a[i]+a[i+1])/2*L,(a[i+1]-a[i])/2*L)--(a[i+1]*L,0);
}
gr = gr -- (L, L*(1-a[n-1])) -- (L,0);
fill(gr--cycle, p=rgb(1,0.8,0.8));
draw(gr,p=red);
draw((0,0)--(5,0));
dot("$0$", (0,0), S);
label("$1$", (L,0),S);
for(int i=0; i<n; ++i){
dot("$a_"+((string) (i+1))+"$", (a[i]*L,0),S);
}
[/asy]](http://latex.artofproblemsolving.com/3/a/c/3ac28a6db5cd3ba2a136be9a4892f9beac4c6841.png)
We're trying to minimize the area under the graph. This area is comprised of
triangular "mountains" and more triangle at the very end.Let's consider two adjacent mountains: The one between
and 
, and the one between and 
, for some 
.The base of the first mountain is
, and the base of the second mountain is 
.![[asy]
size(6cm);
path gr = (0,0)--(1,1)--(2,0)--(3.5,1.5)--(5,0);
fill(gr--cycle, p=rgb(1,.8,.8));
draw(gr, p=red);
draw((0,0)--(5,0));
label("$x$", (1,0), N);
label("$y$", (3.5,0),N);
dot("$a_i$", (2,0), S);
dot("$a_{i-1}$", (0,0),S);
dot("$a_{i+1}$", (5,0),S);
[/asy]](http://latex.artofproblemsolving.com/b/1/4/b14145227fab9bba9127c033c80b896f74af0c89.png)
The combined area of the mountains is then
. Where could we move so that this is minimized?Aha! We are trying to minimize
subject to the constraint 
. By the QM-AM inequality, the minimum is obtained exactly when 
. Therefore, in the minimum configuration, each pair of adjacent mountains must be of the same size! Because otherwise, there must be two adjacent mountains with different sizes, and then we can move the point in between them so that their area goes down.Let's update what the full graph looks like now.
![[asy]
size(6cm);
real[] a = {0.15, 0.3, 0.45, 0.6, 0.75};
int n = a.length;
real L = 5;
path gr = (0,0)--(a[0]/2*L,a[0]/2*L)--(a[0]*L,0);
for(int i=0; i<n-1; ++i){
gr = gr--((a[i]+a[i+1])/2*L,(a[i+1]-a[i])/2*L)--(a[i+1]*L,0);
}
gr = gr -- (L, L*(1-a[n-1])) -- (L,0);
fill(gr--cycle, p=rgb(1,0.8,0.8));
draw(gr,p=red);
draw((0,0)--(5,0));
dot("$0$", (0,0), S);
label("$1$", (L,0),S);
for(int i=0; i<n; ++i){
dot("$a_"+((string) (i+1))+"$", (a[i]*L,0),S);
}
[/asy]](http://latex.artofproblemsolving.com/b/6/7/b678c07ca5c9431ddf60c574ac2a45fe4abbb6bf.png)
With the above positions for the elevators, we can't move
to make the area go down. So we can only move the elevator at the end, 
(in the above picture, this is 
).Where do we move the final elevator to minimize the area of the two triangles next to it? We could do another QM-AM-type argument. But we actually don't have to do any work: We've done this before! This just reduces to the case with two elevators (restricted to just the interval
![$[a_{n-2},1]$](http://latex.artofproblemsolving.com/e/2/f/e2f57134cda208e0a2f722fbc429a7a7701f0e80.png)
)! So, it is optimal to put exactly of the way between 
and .Therefore, in the optimal configuration, we must have
and
![[asy]
size(6cm);
real[] a = {2/11, 4/11, 6/11, 8/11, 10/11};
int n = a.length;
real L = 5;
path gr = (0,0)--(a[0]/2*L,a[0]/2*L)--(a[0]*L,0);
for(int i=0; i<n-1; ++i){
gr = gr--((a[i]+a[i+1])/2*L,(a[i+1]-a[i])/2*L)--(a[i+1]*L,0);
}
gr = gr -- (L, L*(1-a[n-1])) -- (L,0);
fill(gr--cycle, p=rgb(1,0.8,0.8));
draw(gr,p=red);
draw((0,0)--(5,0));
dot("$0$", (0,0), S);
label("$1$", (L,0),S);
for(int i=0; i<n; ++i){
dot("$a_"+((string) (i+1))+"$", (a[i]*L,0),S);
}
[/asy]](http://latex.artofproblemsolving.com/c/9/6/c961a6e32f2d1298191629aad5ef7e79130f3b17.png)
Some basic algebra reveals the final answer: When there are
elevators, it is optimal to place them at the following floors:
It's always a great joy to discover compelling and intricate mathematics in the wild!
This post has been edited 4 times. Last edited by greenturtle3141, Apr 6, 2024, 1:13 AM
March 2025
November 2024