Deadline: September 7, 2018

Here’s Anirban DasGupta’s latest puzzle, probability this time:

This problem is a comparatively simple one. You can get a reasonable idea of the answers to the questions that we pose by large simulations, but you cannot get the algebraic answers that we are asking for. Here is the setup.

In a town, there are N residents. A subset of n residents have x₁, x₂, …, x_n acquaintances (i.e. friends) respectively. The acquaintance sets are random subsets of {1, 2, …, N}, and let us assume these sets are formed independently. To keep this problem simple, here are three fairly straightforward problems:

a) find an expression for the probability that the n residents do not have a common acquaintance.

b) Give a numerical value for the probability that these n residents have at most one common acquaintance when N=10⁶, n = 15 and each x_i = 4×10⁵.

c) Give an analytic approximation to the probability that they have exactly one common acquaintance when n = N, and each x_i = N − log N , with the parameter N → ∞.

[Note that part (c) is asking what is the probability that there is exactly one person in town who is a friend of everybody?]

The solution to the previous puzzle is here. Find out who submitted a correct answer!