This is a solution to this week’s Riddler Classic.

A town of 1,000 households has a strange law intended to prevent wealth-hoarding. On January 1 of every year, each household robs one other household, selected at random, moving all of that house’s money into their own house. The order in which the robberies take place is also random and is determined by a lottery. (Note that if House A robs House B first, and then C robs A, the houses of A and B would each be empty and C would have acquired the resources of both A and B.)

Two questions about this fateful day:

1. What is the probability that a house is not robbed over the course of the day?

2. Suppose that every house has the same amount of cash to begin with — say $100. Which position in the lottery has the most expected cash at the end of the day, and what is that amount?

For the first question, the probability that house \(m\) draws house \(n\) is \(\frac{1}{999}\). Write this as \(P_{m,n} = \frac{1}{999}\). The probability house \(n\) is not robbed by any house is then \[\prod_{m \in \{1, \dots 1000 \} \backslash \{ n \}} (1 - P_{m,n}) = \prod_{m \in \{1, \dots 1000 \} \backslash \{ n \}} \frac{998}{999} = \left( \frac{998}{999} \right)^{999} = 0.3678.\]

Onto the second part. Consider the house in position \(n\). One of three things can happen.

  1. The house never gets robbed.
  2. The house gets robbed after their turn.
  3. The house gets robbed before their turn and not after.

Let these events have probabilites \(P_1, P_2, P_3\) and expected values \(E_1, E_2, E_3\) respectively.

We’ve seen that \(P_1 = 0.368\). Since the mean of all houses that house \(n\) can steal from is \(\$100\), \(E_1 = \$200\).

It’s not hard to see that \(P_2 = 1 - (998/999)^{1000-n}\). In this event the house ends with no money so \(E_2 = 0\).

And similarly \(P_3 = (1 - (998/999))^{n-1}(998/999)^{1000-n}\). Here the expected value of all other houses is \(\frac{100000}{999}\), so $E_3 = 100.1001001. $

Putting all this together, \(E_n = P_1 E_1 + P_2 E_2 + P_3 E_3 = 0.368 \times 200 + 0 + (1 - (998/999))^{n-1}(998/999)^{1000-n} \times 100.1001001.\) This increases strictly as \(n\) increases, so the final house in the lottery has the most expected cash and the amount is \(\$136.83282\).

I also ran a simulation and graphed it with \(E_n\) as the red line.