This puzzle was coined the “Impossible Puzzle” by Martin Gardner, a famous math and science writer that liked to create and write about math games and puzzles. The puzzle is named as such because it appears to provide insufficient information to solve, but it is in fact solvable! Read on for the puzzle and the (very difficult) solution.
There are two distinct whole numbers greater than 1, we can call them x and y (where y > x). We know the sum of x and y is no more than 100.
Sam and Prada are perfect logicians. Sam (“sum”) is told x + y and Prada (“product”) is told x * y, and both of them know all the information provided so far.
Sam and Prada have this conversation in which they truthfully deduce the numbers:
- Sam: I know Prada does not know x and y.
- Prada: Well now I know x and y.
- Sam: Ah, now I also know x and y.
Can you figure out x and y using this information?
Solution
x = 4, y = 13
To solve this, start with the list of possible sums (1-100) and eliminate them.
Deductions from statement 1
If Prada had a product with only one possible factorization (e.g., 15 = 3 * 5), Prada would know the numbers right away. So if Sam knows that Prada cannot know the numbers with just the product, then the sum is such that no combination of addends is the sole factorization of the product.
This means x and y cannot both be prime numbers, and the sum Sam was provided has no combination of addends that are both prime. For example, we can eliminate 9 because it can be formed by 2 + 7 which are prime, so Sam would be unable to conclude that Prada cannot deduce the numbers.
This leaves us with: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95, 97
The sum also cannot be greater than 55, because then there would be a combination of addends involving 53 that results in a unique factorization of the product. For example, we can eliminate 57, because while the combination 4 + 53 gives a product that can be factorized 4 * 53 or 2 * 106, 4 * 53 is actually unique because 2 * 106 is not valid (sum would be greater than 100).
This leaves us with: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53
Deductions from statement 2
If Prada can figure out the numbers from the first statement, then the product must be unique among the remaining possible sums. For example, if the product were 30, Prada would be unable to figure out the numbers because the sum could be 11 = 5 + 6 or 17 = 2 + 15. So for each of the remaining sums, we write out the possible products:
- From 11: 18, 24, 28, 30
- From 17: 30, 42, 52, 60, 66, 70, 72
- From 23: 42, 60, 76, 90, 102, 112, 120, 126, 130, 132
- and so on
Then we eliminate the products that are common between these sums. When this is done, we observe that 17 has only one remaining product (52) and the others all have more than one. Therefore the sum is 17 and the product is 52, so the numbers are 4 and 13!
From Sam and Prada’s perspective
Sam and Prada actually have an easier time figuring out the numbers than we did!
Sam was provided x + y = 17, and can list out the possible products that Prada could have been provided:
- 30 = 2 * 15
- 42 = 3 * 14
- 52 = 4 * 13
- 60 = 5 * 12
- 66 = 6 * 11
- 70 = 7 * 10
- 72 = 8 * 9
Because none of these products has a unique factorization (i.e., none of these are the product of two prime numbers), Sam knows Prada cannot know the solution yet – hence the first statement.
Prada was provided x * y = 52, and can list out the possible sums that Sam could have been provided: 28 = 2 + 26 or 17 = 4 + 13.
After the first statement, Prada can eliminate one of these possibilities. If Sam was provided 28, one of the possible products would have been 115 = 5 * 23, which is a unique factorization, meaning Sam would be unable to confidently make the first statement. So Prada knows Sam must have been provided 17, and now knows x and y.
After the second statement, Sam now knows Prada was provided a product with which all the possible sums could be ruled out except for one. For example, if Prada was provided 30, Prada would think Sam has either 17 = 2 + 15 or 11 = 5 + 6, but would be unable to narrow these to 17, because 11 is also ambiguous (none of the products 2 * 9, 3 * 8, 4 * 7, 5 * 6 consist of two primes). The same is true for the other products from Sam’s list above, except for 52. So Sam now knows the product must be 52, and now knows x and y too.
Yeѕ! Finally someone wrіtes aboᥙt impossibⅼe.
Hmm іt looks like your blog ate my first comment (it was super long) so Ι
guess I’ll just sum it up what I wrote and say, I’m thoroսghly enjoying your bⅼog.
I aѕ well am an aspiring blog blogger but I’m still new to everything.
Do you have any tips and hints for first-time bⅼog ԝriters?
I’d genuinely apprеciate it.