The Sum and Product Puzzle, also known as the Impossible Puzzle because it seems to lack sufficient information for a solution, is a logic puzzle. It was first published in 1969 by Hans Freudenthal,[1] [2] and the name Impossible Puzzle was coined by Martin Gardner.[3] The puzzle is solvable, though not easily. There exist many similar puzzles.
X and Y are two whole numbers greater than 1, and Y > X. Their sum is not greater than 100. S and P are two mathematicians (and consequently perfect logicians); S knows the sum X + Y and P knows the product X × Y. Both S and P know all the information in this paragraph.
In the following conversation, both participants are always telling the truth:
What are X and Y?
The problem is rather easily solved once the concepts and perspectives are made clear. There are three parties involved, S, P, and O. S knows the sum X+Y, P knows the product X·Y, and the observer O knows nothing more than the original problem statement. All three parties keep the same information but interpret it differently. Then it becomes a game of information.
Let us call the split of a number A into two terms A=B+C a 2-split. There is no need for any advanced knowledge like Goldbach's conjecture or the fact that for the product B·C of such a 2-split to be unique (i.e. there are no other two numbers that also when multiplied yield the same result). But with Goldbach's conjecture, along with the fact that P would immediately know X and Y if their product were a semiprime, it can be deduced that the sum x+y cannot be even, since every even number can be written as the sum of two prime numbers. The product of those two numbers would then be a semiprime.
The following steps give the solution:
The solution has X and Y as 4 and 13, with P initially knowing the product is 52 and S knowing the sum is 17.
Initially P does not know the solution, since
52 = 4 × 13 = 2 × 26and S knows that P does not know the solution since all the possible sums to 17 within the constraints produce similarly ambiguous products. However once P knows that S believes there are multiple possible solutions given the product, P can rule out 2 x 26, as in that case the sum is 28. If S had been told 28, she couldn't state with certainty that P didn't know the values, as a possible pair would be 5 and 23, and if P had been told the total of 5 x 23, then those two numbers are the only possible solution.So P now knows the numbers are 4 and 13 and tells S that he knows the numbers. From this, S now knows that of the possible pairs based on the sum (viz. 2+15, 3+14, 4+13, 5+12, 6+11, 7+10, 8+9) only one has a product that would allow P to deduce the answer, that being 4 + 13.The reader can then deduce the only possible solution based on the fact that S was able to determine it. Note that for instance, if S had been told 97 (48 + 49) and P was told 2352 (48 * 49), P would be able to deduce the only possible solution, but S would not, as 44 & 53 would still be a logically possible alternative.
The problem can be generalized. The bound X + Y ≤ 100 is chosen rather deliberately. If the limit of X + Y is altered, the number of solutions may change. For X + Y < 62, there is no solution. This might seem counter-intuitive at first since the solution X = 4, Y = 13 fits within the boundary. But by the exclusion of products with factors that sum to numbers between these boundaries, there are no longer multiple ways of factoring all non-solutions, leading to the information yielding no solution at all to the problem. For example, if X = 2, Y = 62, X + Y = 64, X·Y=124 is not considered, then there remains only one product of 124, viz. 4·31, yielding a sum of 35. Then 35 is eliminated when S declares that P cannot know the factors of the product, which it would not have been if the sum of 64 was allowed.
On the other hand, when the limit is X + Y ≤ 1685 or higher, there appears a second solution X = 4, Y = 61. Thus, from then on, the problem is not solvable in the sense that there is no longer a unique solution. Similarly, if X + Y ≤ 1970 or higher a third solution appears (X = 16, Y = 73). All of these three solutions contain one prime number. The first solution with no prime number is the fourth which appears at X + Y ≤ 2522 or higher with values X = 16 = 2·2·2·2 and Y = 111 = 3·37.
If the condition Y > X > 1 is changed to Y > X > 2, there is a unique solution for thresholds X + Y ≤ t for 124 < t < 5045, after which there are multiple solutions. At 124 and below, there are no solutions. It is not surprising that the threshold for a solution has gone up. Intuitively, the problem space got "sparser" when the prime number 2 is no longer available as the factor X, creating fewer possible products X·Y from a given sum A. When there are many solutions, that is, for higher t, some solutions coincide with those for the original problem with Y > X > 1, for example X = 16, Y = 163.
If the condition X + Y ≤ t for some threshold t is exchanged for X·Y ≤ u instead, the problem changes appearance. It becomes easier to solve with less calculations required. A reasonable value for u could be u = t·t/4 for the corresponding t based on the largest product of two factors whose sum are t being (t/2)·(t/2). Now the problem has a unique solution in the ranges 47 < t < 60, 71 < t < 80, 107 < t < 128, and 131 < t < 144 and no solution below that threshold. The results for the alternative formulation do not coincide with those of the original formulation, neither in number of solutions, nor in content.