You have to guess the identity of a specific person, randomly chosen from all people currently alive on Earth. You are allowed to ask one question about the randomly chosen individual, with a “yes” or “no” answer, and receive the answer before guessing. For the answer of any such question, you will be given a list of all persons satisfying that answer. For example, you could ask: Does the person primarily reside inside California? If the answer is “yes,” you will be given a list of all persons primarily residing in California; if “no,” a list of all persons not living in California.
- Give an example of a question that maximally improves your expected probability of correctly guessing the individual.
- Give an example of a question that minimally improves your expected probability of correctly guessing the individual.
- How would you characterize questions with improvement greater than the minimum and less than the maximum?
Several readers sent in noteworthy solutions, which can be found attached to this column posted on the AR website under bit.ly/AR_Puzzlement. Unfortunately, as of this printing, neither Steve Mildenhall nor I have yet allocated sufficient time and attention to evaluate whether any of these solutions constitute a definitive answer to the puzzle as posed. We are not otherwise aware of a definitive solution, and the puzzle may effectively be an “open problem.”
However, there is a definitive answer to a closely related problem. It is known as the Mian-Chowla sequence. Details and references can be found at The On-line Encyclopedia of Integer Sequences (https://oeis.org/A005282). This sequence is recursively defined very simply as follows: a(1) = 1; for n > 1, a(n) = smallest number > a(n – 1) such that the pairwise sums of elements are all distinct. There does not appear to be a simpler formula or computationally much simpler algorithm than a recursive search program, where given a(1),…, a(n) successively larger candidates for a(n + 1), beginning with a(n) + 1, are analyzed to determine if the new pairwise sums they produce with a(1), …, a(n) are all different from any of the pairwise sums already produced among only a(1), …, a(n).
A known asymptotic interval bound is n2/2 + 0(n) < a(n) < n3/6 + 0(n2). A conjectured asymptotic growth estimate is a(n) ~ n3/(log(n))2.
Note that any partition of a(n) into infinite disjoint sequences A(n) and B(n), will automatically satisfy the identifiable condition posed by Mildenhall, although not necessarily satisfying his loosely defined “slowest growing” criterion. However, two sequences A(n) and B(n), finite or infinite, that are jointly identifiable, do not necessarily form a union that satisfies the unique pairwise sum property of the Mian-Chowla sequence. Therefore, in a loose conceptual sense, the Mian-Chowla is a “special case” of Mildenhall’s puzzle.
Solutions were submitted by John Berglund, Ken Klinger, Eamonn Long and Tomasz Serbinowski.
Solutions [ZIP]
