# Impossible Puzzle

Another weekly FiveThirtyEight riddler, and this one's a mind-bender.

Three very skilled logicians are sitting around a table — Barack, Pete and Susan. Barack says: “I’m thinking of two natural numbers between 1 and 9, inclusive. I’ve written the product of these two numbers on this paper that I’m giving to you, Pete. I’ve written the sum of the two numbers on this paper that I’m giving to you, Susan. Now Pete, looking at your paper, do you know which numbers I’m thinking of?”

Pete looks at his paper and says: “No, I don’t.”

Barack turns to Susan and asks: “Susan, do you know which numbers I’m thinking of?” Susan looks at her paper and says: “No.”

Barack turns back to Pete and asks: “How about now? Do you know?”

“No, I still don’t,” Pete says.

Barack 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 said no the fifth time, would Susan have said yes or no at her fifth turn?

It appears that they both shouldn't have enough information to deduce what the two numbers are. How is it possible that only after five turns, they could exchange enough information to pinpoint the number pair?

When Pete first says 'I don't know', that means with the product he's been given isn't unique in the space of all possible product pairs from [1,9]. So Pete can eliminate all pairs that have unique products.

Sarah, following the same logic also doesn't see a unique sum, and can eliminate all pairs that have unique sums.

Iterate this for 5 turns and we get the following logic:

from collections import Counter

lower_bound = 1
upper_bound = 9

remaining_pairs = set((a, b) for a in range(lower_bound,upper_bound + 1) for b in range(a, upper_bound + 1))

for i in range(0,4):
print "Pete - 'I don't know'"

_prod_counts = Counter(a*b for a,b in remaining_pairs)
remaining_pairs = set((a,b) for a,b in remaining_pairs if _prod_counts[a*b]>1)

print "Sarah - 'I don't know'"

_sum_counts = Counter(a+b for a,b in remaining_pairs)
remaining_pairs = set((a,b) for a,b in remaining_pairs if _sum_counts[a+b]>1)

_prod_counts = Counter(a*b for a,b in remaining_pairs)
print "Pete - 'I know its: {}'".format(set((a,b) for a,b in remaining_pairs if _prod_counts[a*b] == 1))


Running this we get:

Pete - 'I don't know' Sarah - 'I don't know'
Pete - 'I don't know'
Sarah - 'I don't know'
Pete - 'I don't know'
Sarah - 'I don't know'
Pete - 'I don't know'
Sarah - 'I don't know'
Pete - 'I know its: set([(2, 8)])'

And in the case where Pete doesn't know in round 5, Sarah also won't know what the pair will be.