Sum and Product Puzzle
||This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: Full of code samples with no cited discussion of the problem. (November 2015) (Learn how and when to remove this template message)|
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, and the name Impossible Puzzle was coined by Martin Gardner. The puzzle is solvable, though not easily. There exist many similar versions of puzzles.
X and Y are two different whole numbers greater than 1. Their sum is no greater than 100, and Y is greater than X. 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.
The following conversation occurs:
- S says "P does not know X and Y."
- P says "Now I know X and Y."
- S says "Now I also know X and Y."
What are X and Y?
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 × 26
and S knows that P does not know the solution since all the possible sums to 17 within the constraints produce similarly ambiguous products. However, each can work out the solution by eliminating other possibilities following the other's statements and that is enough for the reader to find the solution given the constraints.
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, that’s us, 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), both factors must be prime numbers. But if you know Goldbach’s conjecture, though, your work is cut in half since you know immediately 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 immediately possible to factorise uniquely by the property of prime numbers.
Step 1. S (Sue), P (Pete), and O (Otto) make tables of all products that can be formed from 2-splits of the sums in the range, i.e. from 5 to 100 (X > 1 and Y > X requires us to start at 5). For example, 11 can be 2-split into 2+9, 3+8, 4+7, and 5+6. The respective products are 18, 24, 28, and 30 and the players put a tick mark beside each of these products in their tables (Table 1). When they are done, some numbers have no tick marks, some have one, and some have more than one.
Step 2. Sue now looks at her sum and all its 2-splits. She sees that all 2-splits have products that are not unique, i.e. there is at least one other multiplication of two numbers that yield the same result. She sees this from the table in Step 1 where all her products have more than one tick mark. She realises that because of this fact, Pete will be unable to uniquely determine the factors X and Y by looking at the product (that would have required at least one of the candidate products to have only one tick mark). Thus she exclaims “P cannot know X and Y”. When Pete and Otto hear this, they get the information that none of the products associated with Sue’s sum are unique. By going through the possible sums, one by one, Sue, Pete, and Otto can now each one by themselves make a list of all eligible sums (Table 2). The table contains those sums whose all 2-splits have products that are non-unique, i.e. have more than one tick mark in Table 1. In no time at all, Sue, Pete, and Otto have created the table of candidate sums (Sue of course already knows her sum but needs to trace Pete’s thinking).
Step 3. Considering the new information in Table 2, Pete once again looks at his product. To his surprise, the sums of all of the possible 2-splits of his product except one have disappeared from Table 2 compared to all numbers between 5 and 100 that were considered as sums from the outset. The only one that remains must be the sum of the two hidden numbers X and Y whose product X·Y he knows. From the sum and the product, it is easy to know the individual numbers and thus he tells Sue that “Now I know X and Y”. Pete is now done and exits the game.
Step 4. Sue and Otto recalculates Table 1, this time only counting products of 2-splits from sums that are in Table 2 instead of from all numbers in the range 5 to 100 as in the original Table 1. This updated table is called Table 1B. Sue looks at all the products of the 2-splits of her sum and finds only one of them in Table 1B. This must then be the product Pete has, and she can infer the two numbers from their sum and product as easily as Pete did. Thus, she tells Otto (Pete is already gone) that “Now I also know X and Y”. Sue is now also done and exits the game, only Otto remains.
Step 5. From the information in Step 4, Otto scans all sums in Table 2 in search for one who among its all 2-splits, only one has a single tick mark in Table 1B. The desired one can only have one tick mark, else Sue would not have been able to know X and Y with certainty. Finally, Otto arrives at the desired sum which also happens to be the only one with these properties, making the original problem solvable with a unique solution. Otto’s task is now done as well.
The problem can be generalized. The limit X+Y <= 100 is chosen rather deliberately. If the limit of X+Y is altered, the number of solutions 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. Further, 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. This non-prime property is not a trend, however, since the fifth solution again has a prime.
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, i.e. 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.
The above analysis rests on mathematicians' arguments and conclusions where the statements by S and P are taken at face value. But a discourse analysis reveals other facts. Since both S and P are able mathematicians, they start to examine their sum and product respectively. Assume that they are given the problem at the same time and can communicate freely with each other. P will look to see if the product is unique, i.e. could be factorized into two factors in only one way. S will look to see if this property holds for all 2-splits of the sum. One of these 2-splits is the product that P has, but S does not know which. But it is clear that S, having to factorize all 2-splits, must do considerably much more work than P has to. Hence, if P would succeed in factorizing uniquely into only two factors, P would have announced that prior to S being able to complete its larger task. Since the dialogue does not contain a statement by P "I know the answer", one can safely assume that the product X·Y is not possible to factorize uniquely into only two factors. The silence (non-statement) by P is a message in this discourse. S will of course take advantage of this message and cancel out all 2-splits that are possible to factorize uniquely into only two factors. With those 2-splits cancelled out, S's statement that "P does not know X and Y" is now much less of a powerful discriminator. This discourse analysis leads to eight possible solutions to the original problem, of which one is the original solution and the smallest being X=4, Y=5.
- The Impossible Problem by Torsten Sillke
- Two Mathematicians Problem on mathforum
- Model Checking Sum and Product
- Survey: The Freudenthal problem and its ramifications