Welcome to The Riddler. Every week, I offer up a problem related to the things we hold dear around here — math, logic and probability. These problems, puzzles and riddles come from lots of top-notch puzzle folks around the world, including you, the readers. You’ll find this week’s puzzle below.
Mull it over on your commute, dissect it on your lunch break, and argue about it with your friends and lovers. When you’re ready, submit your answer using the form below. I’ll reveal the solution next week, and a correct submission (chosen at random) will earn a shoutout in this column. Important small print: To be eligible, I need to receive your correct answer before 11:59 p.m. EDT on Sunday — have a great weekend!
Before we get to the new puzzle, let’s return to last week’s. Congratulations to 👏 Kevin Carde and Andrew Lin 👏 of Cambridge, Massachusetts, who submitted an answer together and are our big winners. You can find a solution to the previous Riddler at the bottom of this post.
Now here’s this week’s Riddler, a party puzzle that comes to us from Dominic van der Zypen, a software engineer in Bern, Switzerland.
It’s Friday and that means it’s party time! A group of N people are in attendance at your shindig, some of whom are friends with each other. (Let’s assume friendship is symmetric — if person A is friends with person B, then B is friends with A.) Suppose that everyone has at least one friend at the party, and that a person is “proud” if her number of friends is strictly larger than the average number of friends that her own friends have. (A competitive lot, your guests.)
Importantly, more than one person can be proud. How large can the share of proud people at the party be?
Need a hint? You can try asking me nicely. Want to submit a new puzzle or problem? Email me.
[googleapps domain=”docs” dir=”forms/d/1gqLE2dYDNVwVowPCT5RLqd_VBx3To9xwIR91CcMm7gE/viewform” query=”embedded=true” width=”760″ height=”950″ /]
And here’s the solution to last week’s Riddler, concerning the population density of a misanthropic neighborhood, which came from Jim Ferry. I’ve adapted Jim’s solution below.
Since a misanthrope will only move into an empty, neighborless house, the most tightly packed neighborhood, asymptotically, will have someone in one out of every two houses, while the emptiest neighborhood will have someone in one out of three houses. This suggests the Richard Feynman ploy of immediately declaring the answer to be \(1/e\). But is this correct? No.
The correct answer is \((1 – e^{-2})/2\), or approximately 0.432. About 43.2 percent of the houses are expected to be occupied. Sorry, Feynman.
Why? Deep breath … It’s math time!
Let \(a_n\) be the expected number of misanthropes in a row of n houses. Clearly \(a_0=0\) and \(a_1=1\). For larger \(n\), we may obtain a recursion by observing that the first misanthrope picks house \(k\) (= 1 to \(n\)) with probability \(1/n\), yielding an expected value \(a_n\) of 1 (due to the first misanthrope) plus contributions due to the rows of houses 1 through \(k-2\) and \(k+2\) through \(n\). The recursion is therefore \(a_n = 1 + (2/n) \sum_{j=1}^{n-2}a_j\). Letting \(s_n = \sum_{j=1}^n a_j\), we can write the recursion as
$$a_n = 1 + (2/n) s_{n-2}$$ and
$$s_n = s_{n-1} + a_n$$
We don’t really want to solve the recursion — we just want to find the asymptotic limit of \(a_n / n\) as \(n \rightarrow \infty\). Therefore, we introduce generating functions \(A(x) = \sum_{n=0}^\infty a_n\cdot x^n\) and \(S(x) = \sum_{n=0}^\infty s_n\cdot x^n\). We can then multiply each side of the above recurrences by \(x^n\) and sum from \(n = 0\) to infinity to obtain
$$A(x) = 1/(1-x) + 2 F(x)$$ (where \(F’(x) = x S(x)\)) and
$$S(x) = x S(x) + A(x)$$
Therefore, \(A(x) = (1-x) S(x)\), and differentiating the first equation yields
$$(1 – x) S’(x) – S(x) = 1/(1 – x)^2 + 2 x S(x)$$
with the initial condition \(S(0) = 0\) (which enforces \(s_0 = 0\)). The solution to this equation is \(S(x) = (1 – e^{-2x}) / (1-x)^3\), so
$$A(x) = (1 – e^{-2x}) / (1-x)^2$$
Therefore the asymptotic growth rate of \(a_n\) is \(a_n \sim ((1 – e^{-2})/2) n\). That is, the limit of \(a_n / n\) as \(n \rightarrow \infty\) is, indeed, \((1 – e^{-2})/2\). In expectation, about 43.2 percent of the houses will be occupied — closer to the tightest possible neighborhood than the emptiest.
Daniel McNichol created this awesome Shiny app to simulate the solution, and Andrew Mascioli has another really nice explanation of the math.
There were also lots of great extensions this week. Philip Bulsink explored what happens when the misanthropes are a bit nicer. On the flip-side, Zach Wissner-Gross explored what happens when they get meaner:
Lots of folks suggested tweaking the dimensions of the neighborhood, often into a rectangular grid of houses. Tom Walker sent in a really cool extension putting you in the shoes of a homebuilder who wants to maximize profit and can build both houses and privacy walls to quell the misanthropes.
But the 🏆 Coolest Riddler Extension Award 🏆 goes to Nick Stanisha! (Congrats, Nick. You’re now in the Riddler Hall of Fame.) If the curmudgeonly neighbors were bees in a hexagonal beehive, like below, we’d have 76.8 percent less honey!
https://twitter.com/sticknanisha/status/723670601043456000
A looming honey shortage notwithstanding, have a sweet weekend and enjoy the party!