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.

Puzzle

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:

  • 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?

Explanation

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:

  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.
  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 exists a different factorization that is a 2-split of some other possible sum. 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 all of whose 2-splits have products that are non-unique, i.e. have more than one tick mark in Table 1. 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).
  3. Considering the new information in Table 2, Pete once again looks at his product. 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.
  4. Sue and Otto recalculate 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 that only one of them appears exactly once 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.
  5. From the information in Step 4, Otto scans all sums in Table 2 in search for one of which only a single 2-split has a single tick mark in Table 1B. The desired one can only have one tick mark, or 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.

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 × 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 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.

Other solutions

The problem can be generalized.[2] 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.

See also

References

  1. ↑ Hans Freudenthal, Nieuw Archief Voor Wiskunde, Series 3, Volume 17, 1969, page 152
  2. 1 2 Born, A.; Hurkens, C. A. J.; Woeginger, G. J. (2006). "The Freudenthal problem and its ramifications (Part I)" (PDF). Bulletin of the European Association for Theoretical Computer Science, EATCS. 90: 175–191.
  3. ↑ Gardner, Martin (December 1979), "Mathematical Games: A Pride of Problems, Including One That Is Virtually Impossible", Scientific American, 241: 22–30, doi:10.1038/scientificamerican0979-22.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.