538 Riddler: Can You Solve The Puzzle Of Your Misanthropic Neighbors?

This week's Riddler involves some not-so-nice neighbors:

The misanthropes are coming. Suppose there is a row of some number, N, of houses in a new, initially empty development. Misanthropes are moving into the development one at a time and selecting a house at random from those that have nobody in them and nobody living next door. They keep on coming until no acceptable houses remain. At most, one out of two houses will be occupied; at least one out of three houses will be. But what’s the expected fraction of occupied houses as the development gets larger, that is, as N goes to infinity?

I usually approach problems like this by trying a few small cases and seeing if a pattern appears.  For N = 1, exactly one person will move in.  The same is true for N = 2 - they'll randomly select one of the two houses, and then no one will move in next door.

It's only a bit more complicated for N = 3.  If the first person moves into the middle house (which will happen 1/3 of the time) then no one else will move in on the street.  However, if the first person moves into one of the end houses (which will happen 2/3 of the time), another misanthrope will move into the empty house on the other end of the street.  So the total number of expected residents for N = 3 is \frac{1}{3}*1 + \frac{2}{3}*2 = \frac{5}{3}.

(The problem actually asks us to solve for the expected fraction of houses that will be occupied, which would be the expected residents divided by the number of houses, so \frac{5}{9}.  But for the time being I'll continue talking about the number of expected residents.)

If we add a fourth house, then no matter where the first person moves, there will always be at least one house available for a second resident.  But once a second resident moves in, there will be no room left for a third, so the expected number of residents for N = 4 is 2.

We could keep reasoning case by case like this but obviously not for much longer.  Let's think about it more generally, then, for the case N = 5.

  • If the first person moves into one of the end houses (which would happen 2/5 of the time), they've occupied that house and made the one next to it unavailable as well.  So there is a row of three adjacent houses left for the next neighbor to pick from.
  • If the first person moves into the second or fourth house on the street (which would happen 2/5 of the time), they've occupied that house and also made the two houses on either side of it unavailable.  So there is now just a row of two adjacent houses left for the next neighbor to pick from.
  • Finally, if the first person moves into the middle house (which would happen 1/5 of the time), only the two end houses now remain available.

By choosing a house, the first person is effectively splitting the street into 1-2 distinct groups of houses available for the next misanthrope to choose from.

  • 2/5 of the time they leave a group of 3 in a row, which is just the case N = 3 (which we've already solved).
  • 2/5 of the time they leave a group of 2 in a row, which is just the case N = 2 (which we've already solved).
  • 1/5 of the time they leave TWO groups of 1 in a row, each of which is just the case N = 1 (which we've solved).

So for N = 5, we have 1 for the first neighbor, plus the expected number of residents that will occupy the remaining houses:

\displaystyle \frac{2}{5} * \frac{5}{3} + \frac{2}{5} * 1 + 2 * \frac{1}{5} * 1

which is equal to 2 \frac{7}{15}.  But more generally, there's a pattern emerging that becomes evident after examining subsequent cases.  For N = 6, after the first person chooses a house:

  • 2/6 of the time they've left a group of 4 in a row, which is just the case N = 4.
  • 2/6 of the time they've left a group of 3 in a row, which is just the case N = 3.
  • 2/6 of the time they've left a group of 1 in a row on one side, and 2 in a row on the other side, which are just N = 1 and N = 2 respectively.

The pattern we find is that for any N, the number of expected residents is simply:

\displaystyle E(N) = \frac{2}{N} \displaystyle\sum_{i=1}^{N-2} E(i) + 1

Now let's think about E(N+1).  If we solved E(N) then we've already done the summation, we just need to add another term.  So if we take the formula for E(N), strip away all but the summation, add in the additional term and put everything back we should have a working relationship between successive terms.  What we end up with is:

\displaystyle E(N+1) = [(E(N) - 1)(\frac{N}{2}) + E(N-1)] * \frac{2}{N+1} + 1

Which simplifies to the (relatively) nice looking recurrence relation:

\displaystyle E(N+1) = \frac{2E(N-1) + (N)E(N) + 1}{N+1}

Sadly, that's as far as I got before the deadline to submit solutions.  We have a simple formula that will generate the correct answer for any N recursively, but no closed-form solution.  I used the recurrence to calculate the expected proportion of occupied houses (dividing the expected residents by N) for N = 100,000,000 and got the result 0.432332361373...  So we know approximately what the answer is, but I assumed that there was a cleaner way to state it.

It turns out that there is, which I found in this blog post via Twitter.  It involves more math that I was prepared to do this weekend, but the end result is that:

\displaystyle \lim_{N \to \infty} \frac{E(N)}{N} = \frac{1}{2}\Big(1 - \frac{1}{e^2}\Big)

Note that this agrees with the observed result from our recurrence relation.

Leave a Reply