Can You Solve This Elevator Button Puzzle?

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?

The Riddler, FiveThirtyEight(original post)

Solution

Count the buttons one at a time. For floor $i$, let $F_i$ be $1$ if at least one person picks it and $0$ otherwise, so the number of lit buttons is $L = F_1 + \cdots + F_M$. A button stays dark only if all $N$ people avoid it, and each person avoids a given floor with probability $(M-1)/M$, independently, so $$\Pr(F_i = 1) = 1 - \left(\frac{M-1}{M}\right)^{N}.$$ The floors are not independent of one another, but expectation adds regardless, so by linearity $$\mathbb{E}[L] = \sum_{i=1}^{M} \Pr(F_i = 1) = \boxed{\,M\left(1 - \left(\tfrac{M-1}{M}\right)^{N}\right)}.$$ For example, $30$ people choosing among $20$ floors light on average $20\big(1-(19/20)^{30}\big) \approx 15.7$ buttons.

The computation

Press the buttons: send each of $N$ people to a uniformly random floor, count the distinct floors chosen, and average over many rides. With $N=30$ and $M=20$ the mean matches the formula.

import numpy as np
rng = np.random.default_rng(0)
n, m = 30, 20
runs = 200_000
total_lit = 0
for _ in range(runs):
    picks = rng.integers(0, m, n)        # each person's chosen floor
    total_lit += len(set(picks.tolist()))    # number of distinct floors
print(total_lit / runs)                  # ~15.71
print(m * (1 - ((m - 1) / m) ** n))      # 15.707..., the formula