Elevator button puzzle

This problem was originally posted on the Riddler blog. Here it goes:

In a building’s lobby, some number (N) of people get on an elevator that goes to some number (M) of floors. There may be more people than floors, or more floors than people. Each person is equally likely to choose any floor, independently of one another. When a floor button is pushed, it will light up.

What is the expected number of lit buttons when the elevator begins its ascent?

My solution:
[Show Solution]

A much more elegant solution, courtesy of Ross Boczar
[Show Solution]

11 thoughts on “Elevator button puzzle”

1. Ken Harlow says:

From the person who submitted the puzzle to The Riddler, congratulations on your clear and elegant solutions!

2. Alex says:

Great post! Could you elaborate more on how you obtain the 4th line in the derivation of theta(n + 1) = (1 – 1/M) theta(n): how do we know that k (k + 1) P(k + 1, n) = (k – 1) k P(k, n)?

Also minor typo: it should be “This means one of the (M – k) on-lights was pressed” instead of “This means one of the (k-M) on-lights was pressed”

1. Apologies for the delayed response; my spam filter misclassified your comment!

In the 4th line of the derivation, I replaced $k \mapsto k-1$, which does not change the expression because I am summing over all $k$ and first term in the new sum is zero anyway.

Fixed the typo. Thanks!

3. Bob Jenkins says:

If the number of buttons/floors (M) goes to infinity, then doesn’t the solution need to go to N (the number of people who boarded the elevator)? With an infinite number of floors, the odds any one elevator rider will want to duplicate a selection become infinitesimally small. So, it will approach a situation where each rider will almost definitely select their own button. When you check for infinite N, you get the solution M, which you expect, from the given equation. It’s the sanity check for infinite M the doesn’t seem to work here. You should get closer and closer to N for a solution, and this equation yields zero buttons pushed as we approach infinite M. Right?

I like to check at the extremes and zero to confirm for myself that the solution I arrived at could possibly be the solution. (With zero floors, you get zero buttons. Check. With zero people, you get zero buttons. Check.)

1. Great question — the limit of infinite $M$ does in fact work. To see why, expand the $(1-\tfrac{1}{M})^N$ term using the binomial theorem, which leads to $1-\tfrac{N}{M} + {N \choose 2}\tfrac{1}{M^2}-{N \choose 3}\tfrac{1}{M^3} + \dots + (-1)^N {N \choose N} \tfrac{1}{M^N}.$ Substituting this into the solution, you’re left with:

$N-{N \choose 2} \frac{1}{M} + \text{(higher powers of }\tfrac{1}{M}\text{)}$

So as $M\to\infty$, you do recover $N$, as expected. In fact, for very large $M$, the formula above tells you that the solution will be slightly smaller than $N$, which also makes sense.

1. Bob Jenkins says:

Thanks. I guess sanity checks aren’t always the “easy part”! Smart guys like you come in handy.

4. Zheng says:

Thanks for the two different solutions. Actually, this is just a very classic “coupon collection” problem.

1. Care to elaborate? I don’t see how this is a coupon collector problem…

1. Zheng says:

Sure. One coupon collector problem asks: given M different coupons, each time you collect one coupon, randomly, with replacement, what is the expected time to collect all M different coupons. The other coupon collector problem asks: also M different coupons, each time you collect one coupon, randomly, with replacement; you collect N times, what is the expected number of different coupons you would get? For both problems, we can use the trick of decomposing the expectation into summations. The latter one corresponds this elevator button problem (view M buttons as coupons and N people as collecting N times).