A third party picks two integers, X and Y, each from the interval 2 to 99, and tells Mr. Sam the sum of the two integers, and Mr. Paul the product of the two. Sam and Paul do not know the values given to the other. Paul tells Sam, “I do not know the two integers.” Sam tells Paul, “I know you didn’t. Neither do I.” Paul replies, “Oh, now I know the integers.” Sam replies back, “Now I know too.”
Given that both of them are telling the truth, what are the two integers.
This puzzle has been in print for quite some decades now, and is also usually published with the title of “The Impossible Puzzle“. It isn’t impossible to solve at all though. Not this version at least. The puzzle has appeared with numerous variations in different places, usually changing the interval from which the integers are chosen by the third party, or putting a constraint on the maximum possible sum of the chosen integers. This version is very much solvable though, even if it doesn’t look like in first guess. Before proceeding to read the solution, I suggest you give it a shot and try to solve it yourself. All it needs is some concepts from the number theory. (Hint: Prime numbers)
Approach to solution
One of the wrong ways to approach this puzzle would be to start thinking from either Paul’s or Sam’s perspective and trying to see how he could have solved the puzzle. Why this won’t be the right approach is because we do not have the same information as either of them. Paul knows the product, and Sam knows the Sum. But we as the puzzle solvers, know neither of these two values. Our best bet is to take the hints passed by both of them to each other, and analyse to see if we could come up with a solution.
To start with, we can say that the sum could be any in the interval [4, 198]. 4 being the smallest, and 198 being the largest sum possible out of two integers chosen from the interval [2, 99]. Lets call this set of possible sums as our possible sums set.
Paul: I do not know the two integers.
Analysis: This is only possible if the product has more than just a single pair of factors, and that means it isn’t a product of two primes. A product that can be factorized into two prime numbers, has only that single pair as its factors. E.g. 35=5*7. Both 5 and 7 are primes, and there is no other pair of factors for 35 (ignoring 1 and 35 itself).
Sam: I know you didn’t. Neither do I.
Analysis: The fact that Sam knew that Paul doesn’t know the two integers means he knew that his sum can’t be written as a sum of two primes. Otherwise he wouldn’t have been so sure. E.g. if the sum had been 12, the pair of summands for it in interval [2, 99] are, (2, 10), (3, 9), (4, 8), (5, 7), (6, 6). One of these pairs, (5, 7) consists of two primes. Sam couldn’t be sure that Paul hasn’t been give a product of these two, and thus wouldn’t have passed this comment.
This further leads to the fact that the sum isn’t an even number. Because every even number can be written as a sum of two primes (GoldBach’s conjecture). So the sum is odd, which means one of the two integers is an odd, and the other is an even.
This eliminates all even numbers from our possible sums set. It also eliminates all odd numbers that can be written as sum of 2 and another prime.
Paul: Oh, now I know the integers.
Analysis: Since this information was of help to Paul. It means, his product has only one such pair of factors consisting of an odd and an even, that can’t be added to give a sum that can be written as a sum of two primes.
Sam: Now I know too.
Analysis: Since Sam figures the two numbers out as well, it means his sum has only one such pair of summands, that when multiplied, gives a product that has only one such pair of factors consisting of an odd and an even, that can’t be added to give a sum that can be written as a sum of two primes.
That is too much of “that”s. Let me clear up with an example. 41 as a sum has (4, 37) as its pair of summands, and 4*37=148, which has (2, 74) and (4, 37) as two pairs of factors. Now Mr. Paul, if given 148 as the product, could have identified (4, 37) to be the pair of unknown integers. But, Mr. Sam wouldn’t have been able to, after that. Because 41 as a sum gives more than one possible summands that can multiply to give such products. One is (4, 37), the other one is (7, 34), which gives 238 as the product, having (7, 34) and (14, 17) as possible factors. Pair of (14, 17) couldn’t have been Mr. Paul’s choice because it gives a sum, 14+17=31 that can be written as a sum of (2, 29), both primes. Thus Mr. Sam couldn’t be sure which of the two (4, 37) and (7, 34) was it for his sum of 41, that Mr. Paul deduced as the unknown numbers.
This leaves us with only one pair of integers as the possible solution: (4, 13).
Of course I didn’t do all of the above calculations by hand, it’s too much for that. I wrote a short C++ program to help me out with the calculations, that I am attaching here for download.