The Sam and Polly Puzzle is a beautiful riddle in which two logicians Sam and Polly must simulate the other’s thought processes several layers deep, deriving information from seemingly unhelpful statements. While many variations have been proposed, I first heard of the puzzle from the excellent list at the XKCD wiki, where it takes the following form:
Sam and Polly are perfectly logical mathematicians. A student walks in and says: “I’m thinking of two numbers
3 <= x <= y <= 97. I’ll tell their sum to Sam, and their product to Polly.” She does so, then leaves, and the following conversation takes place:
Sam (to Polly): You can’t know what
Polly (to Sam): That was true, but now I know.
Sam (to Polly): Now I know too.
If you haven’t solved this riddle or one of its variations before, I absolutely recommend giving it a try before reading on. It took me about three hours to solve, with a whiteboard and the Python programming language.
This post consists of:
- Section 1: A clean Python solution
- Section 2: An investigation of the (somewhat weak) dependence on the bounds 3 and 97
- Section 3: A discussion of unbounded variations of the riddle.
The most common variant on the puzzle (and the original version published by Freudenthal in 1969, available here) uses the following bounds instead:
2 <= x < y and
x + y <= 100, leading to a different solution. I’m sticking with the above formulation just because that’s the version that I saw and started thinking about before looking around to see what was known. The solution in the following section can be easily modified to solve Freudenthal’s version.