Can You Solve The Impossible Puzzle?

Three skilled logicians, Barack, Pete and Susan, sit around a table. Barack says: “I’m thinking of two natural numbers between $1$ and $9$, inclusive. I’ve written their product on this paper for you, Pete, and their sum on this one for you, Susan.” He then asks Pete whether he knows the two numbers. Pete says no. He asks Susan; she says no. He asks Pete again; still no. He keeps going back and forth, and when he asks Pete for the fifth time, Pete says “Yes, now I know.” First, what are the two numbers? Second, if Pete had instead said no that fifth time, would Susan have said yes or no at her fifth turn?

The Riddler, FiveThirtyEight (Max Wahlund)(original post)

Solution

The one idea is that every “I don’t know” is itself a clue. A logician knows the pair the moment her own number, the product for Pete or the sum for Susan, belongs to just one pair still in play. So each “no” broadcasts that the true number is shared by at least two survivors, which lets everyone strike out every pair whose number is now unique. The pool of candidates only shrinks, and the puzzle is just watching it shrink.

Begin with the $45$ unordered pairs $(a,b)$ with $1 \le a \le b \le 9$. The questions alternate Pete, Susan, Pete, Susan, and so on, so apply the cuts in that order: after a Pete “no” delete the pairs whose product is now unique, after a Susan “no” delete the pairs whose sum is now unique. Eight “no”s, four from each, thin the $45$ pairs down to nine. Among those nine, exactly one has a product that no other survivor shares: $2 \times 8 = 16$. That is what lets Pete finally say yes, so the numbers are $$\boxed{2 \text{ and } 8}.$$

For the second question, replay the fifth Pete answer as a “no” instead. That deletes the unique-product survivors once more, leaving eight pairs. Now check Susan: every sum still present is shared by another of those eight pairs, so her slip never narrows to one. She would still be stuck, and the answer is $$\boxed{\text{no}}.$$

The computation

Encode the two cuts and run the alternating “no”s; the surviving pairs are read off directly. A “no” from a speaker removes exactly the pairs whose value (product for Pete, sum for Susan) is unique among current survivors, since such a pair would have let her answer yes.

from collections import Counter
pairs = [(a, b) for a in range(1, 10) for b in range(a, 10)]
prod, summ = lambda p: p[0] * p[1], lambda p: p[0] + p[1]

def after_no(S, val):                 # a "no" kills pairs whose value is now unique
    c = Counter(val(p) for p in S)
    return [p for p in S if c[val(p)] > 1]

S = pairs
for val in (prod, summ) * 4:          # Pete, Susan, Pete, Susan, ... eight "no"s
    S = after_no(S, val)

c = Counter(prod(p) for p in S)       # Pete's 5th turn: unique products now?
print("Q1:", [p for p in S if c[prod(p)] == 1])

S2 = after_no(S, prod)                # counterfactual: Pete's 5th is also "no"
c2 = Counter(summ(p) for p in S2)
print("Q2 Susan knows?", any(c2[summ(p)] == 1 for p in S2))
# Q1: [(2, 8)]
# Q2 Susan knows? False        <- she still cannot tell, so "no"