The Riddler — Can You Solve This Elevator Button Puzzle?

 

The Rid­dler is a week­ly puz­zle series from Oliv­er Roed­er at FiveThir­tyEight that usu­al­ly involves some com­bi­na­tion of math, log­ic and probability.

This weeks FiveThir­tyEight Rid­dler, Can You Solve This Ele­va­tor Puz­zle was:

In a building’s lob­by, some num­ber (N) of peo­ple get on an ele­va­tor that goes to some num­ber (M) of floors. There may be more peo­ple than floors, or more floors than peo­ple. Each per­son is equal­ly like­ly to choose any floor, inde­pen­dent­ly of one anoth­er. When a floor but­ton is pushed, it will light up.

What is the expect­ed num­ber of lit but­tons when the ele­va­tor begins its ascent?

Sim­i­lar to last week, I want­ed to sim­u­late the prob­lem before jump­ing into the math. This’ll also help lat­er to check my work.

While cer­tain­ly not ele­gant, all I did here was cre­ate 10 arrays of 0’s of size 5 to 50 by 5. Array size rep­re­sents total num­ber of floors (M in con­text of the prob­lem). From there, I ran­dom­ly gen­er­at­ed an inte­ger from 1 to M, and changed the num­ber at that array index to 1 — rep­re­sent­ing a pushed but­ton. Repeat­ed the ran­dom num­ber gen­er­a­tion N times to rep­re­sent dif­fer­ent pas­sen­ger sizes (all the way until N = M). Final­ly I re-did this for each array 100 times at a giv­en M/N and then aver­aged the array sum (rep­re­sent­ing but­tons pushed. Again, not ele­gant, but it gave me a quick rep­re­sen­ta­tion of what the data should look like.

We’ll be using f_N to rep­re­sent expect­ed val­ue of pressed ele­va­tor but­tons through­out this post.

Ini­tial­ly let’s deal with a sit­u­a­tion where M (floors) = 5. The expect­ed pressed but­tons for the first pas­sen­ger (f₁) is fair­ly straightforward:

f₁ = 1

Since the next pas­sen­ger is equal­ly like­ly to select any of the 5 but­tons, the ele­va­tor con­fig­u­ra­tions after he press­es a but­ton are:

O

O

X

X

O

Where he selects a dif­fer­ent but­ton from pas­sen­ger 1 or

O

O

X

O

O

selects the same but­ton as pas­sen­ger 1. Giv­en that he has a 1/5 chance of select­ing the same but­ton as pas­sen­ger 1, we com­pute f₂ to be:

f₂ = 1 [num­ber of but­tons already pushed] + (1)*((M‑1)/M) [prob­a­bil­i­ty of select­ing unique button] 

@ M=5 this eval­u­ates to:

f₂ = 1 + (4/5)/5 = 9/5 = 1.8

The f₂ equa­tion can be more gen­er­al­ly writ­ten as:

f₂ = f₁ + (M‑f₁)/M

or

f_N = f_N‑1 + (M‑f_N‑1)/M

Now that we have an equa­tion, let’s test it against some of the data we gen­er­at­ed earlier.

So our equa­tion (dashed blue line) fits the sim­u­lat­ed data (coral sol­id line) fair­ly well. Now we can start try­ing to sim­pli­fy our equa­tion. Let’s start by eval­u­at­ing f_N in N = 1:4.

Let c = (M‑1)/M.

f₁= 1

f₂ = 1+f_N-1*c = 1 + f₁*c = 1 + c

f₃ = 1 + f_N-1*c = 1 + f₂*c = 1 + (1+c)*c = 1 + c + c²

f₃ =  1 + f_N-1*c = 1 + f₃*c = 1 + (1 + c + c²)*c = 1 + c + c² + c³

The trend is clear. It’s a geo­met­ric series that can be writ­ten as:

We go back and plug in c = (M‑1)/M and find the solu­tion to f_N

f_N = ((M‑1/M)^N ‑1)/((M‑1)-1) =M — M*((M‑1)/M)^N

Since we’re con­cerned with the pro­por­tion of pushed but­tons, and fN gives you the expect­ed num­ber of pushed but­tons, sim­ply divide out M and get the final solution

1 — ((M‑1)/M)

EDIT (05.13.2016): I mis­read the ques­tion, and we want expect­ed num­ber of but­tons pushed, not expect­ed pro­por­tion of but­tons pushed. There­fore the final answer is:

M — M*((M‑1)/M)^N