The various versions of the puzzle differ, sometimes slightly, and sometimes drastically. It is preferable to discuss each problem in a separate section.
By the way, in most of the puzzles, we begin with a pair of unknown numbers X and Y whose sum S is given to one person, and the product P to another. The person having P (whom we will also call P!) tries to figure out the sum S, while S tries to figure out P.
Note that for S to figure out P, or for P to figure out S, is equivalent to figuring out the values of X and Y. This is because we have the simultaneous equations:
X + Y = S
X * Y = P
and, if we are guaranteed that X and Y are positive (and hence S and P),
then there is exactly one solution. Knowing the values of S and P, we
can substitute X=P/Y to obtain the quadratic
Y2 - S * Y + P = 0
and the two roots of this equation are the (indistinguishable)
values (X,Y).
So don't be worried or confused. When P cries out "I know S", this is the same as saying "I know X and Y!".
Designate the unknown pair of numbers by (X0,Y0); let S0 = X0 + Y0 and P0 = X0 * Y0.
(i) Let V1 be the set of natural numbers P which can be factored in at least two ways, P=X*Y with 1<X<Y, and X+Y<=100. From statement (1) it follows that P0 must be in V1.
(ii) Let V2 be the set of natural numbers S with the property that for every splitting S=X+Y with 1<X<Y, the product X*Y is an element of V1.
It is immediately obvious that it must be the case that 5<=S<=100 to guarantee that S is in V2. One can soon see that that the following numbers S do not belong to V2:
V2 = { 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53 }.And from statement 2 we have that S0 must be one of the values in V2.
(iii) Now suppose that S is in V2, and consider then all possible splittings S=Xi+Yi with 1<Xi<Yi. For the given S, denote by K(S) the set of all the corresponding products Xi*Yi. For example,
K(11) = { 18, 24, 28, 30 },
K(17) = { 30, 42, 52, 60, 66, 70, 72 },
K(23) = { 42, 60, 76, 90, 102, 112, 120, 126, 130, 132 },
etc
From statement (3) it follows that P0 must belong to exactly one of the sets K(S). Now, for each S in V2, form L(S), the subset of elements that belong uniquely to K(S), that is
L(S) = K(S) / Union K(T) where T is in V2 and T is not S.
By eliminating elements common to other sets, each reduced set L(S) is straightforward to compute:
L(11) = { 18, 24, 28 },Note that L(17) has exactly one element. All the other sets L(S) for S in V2 have at least two elements.
L(17) = { 52 },
L(23) = { 76, 112, 130 },
etc.
From statement (3) it follows that P0 is an element of one of the sets L(S).
(iv) From statement (4) it follows that the set L(S0) must have just one element, that is,
S0 = 17, P0 = 52, X0 = 4, Y0 = 13.Hence, the unknown pair of values is, in fact (4,13).
Based on the solution submitted (in Dutch) by J Boersma.
Because Mr P's first statement is that he doesn't know x and y even though he knows their product, it must be the case that x and y are not both prime numbers.
Ms S asserts that she already knew that Mr P did not know the values. So, before Mr P spoke, Ms S must have known, based on the value of the sum of x and y, that they could not both be primes. This means that, from the list of possible sums between 3 and 100, we can eliminate every sum which can be formed by adding two primes.
Following this elimination, we are left with the following set of 24 possible values for the sum: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95, 97.
Since every sum is odd, we now know that x must be odd and y even, or vice versa.
Of the possible values for the sum, 16 of them can be written in at least two different ways as 2m+q, where m is at least 2, and q is an odd prime. (Will this argument fail if we relax the requirement to allow m=1?) As an example, notice that 11 = 4 + 7 = 8 + 3. If one of these quantities is the sum, then Mr P can now determine the values of x and y, because the product will be 2m*q, which can only be broken one way into an odd and an even factor. But if one of these quantities is the sum, Ms S can never know which of the representations 2m+q corresponds to the values of x and y. Since Ms S does determine the values, these 16 entries in the sum list must be eliminated.
Following this elimination, we are left with the following set of 8 possible values for the sum: 17, 29, 41, 53, 65, 89, 97.
In fact, we can also eliminate any value in the list of possible sums that can be written in two different ways as the sum of 2 and the product of any number of odd primes. (This is again because x and y must be one odd and one even). And yet we have:
29 = 2 + 27 = 16 + 13
41 = 4 + 37 = 16 + 25
53 = 16 + 37 = 32 + 21
59 = 16 + 43 = 32 + 27
65 = 4 + 61 = 32 + 33
89 = 16 + 73 = 64 + 25
and therefore, the only possible value for the sum is 17!
Now we need to consider every possible partition of 17:
S E O P E O
17 = 2 + 15 2 * 15 = 30 = 6 * 5
17 = 3 + 14 14 * 3 = 42 = 2 * 21
17 = 4 + 13 4 * 13 = 52
17 = 5 + 12 12 * 5 = 60 = 2 * 30
17 = 6 + 11 6 * 11 = 66 = 2 * 33
17 = 7 + 10 10 * 7 = 70 = 2 * 35
17 = 8 + 9 8 * 9 = 72 = 2 * 36
and note that, for most partitions of 17, we can come up with
at least two distinct factorizations into an odd and even factor,
which have the same product. Therefore, given that the sum is 17,
the product cannot be any of those ambiguous products. It must
be the only product which can only be divided one way into an
even factor and an odd factor, namely 4 + 13.
Therefore, x = 4 and y = 13.
The solution reported here is a rewording of the solution given in Mathematics Magazine, where it is attributed to "The Problem Solving Group" of Bern, Switzerland.
After S said "I see no way you can determine my sum,", P quickly realized that the sum cannot be a sum of two primes. To understand why, suppose the sum is 14. S would reason as follows: "Perhaps the two numbers are the primes 3 and 11. Since their product, 33, has only one pair of factors 3 and 11 (the factors 1 and 33 can be ignored because each number must be greater than 1), P would know at once that my sum is 3 plus 11, or 14." Therefore when S says P cannot know his sum, that tells P the sum cannot be the sum of two primes.
There is a famous conjecture in number theory called Goldbach's conjecture, which states that every even number is the sum of two primes. This has not been proved in general, but it has been established for all even numbers up to 100 million, so that one can safely eliminate all even sums within the given range of 4 through 40. We can do more. Since 2 is a prime, one can also eliminate all odd sums that are a prime plus 2. After making all these eliminations, one is left with seven possible sums:
{ 11, 17, 23, 27, 29, 35, 37 }.These are the only odd numbers within the range that are sums of a composite number plus 2.
Could the sum be 11? No. If P's product were 24, he would immediately conclude the numbers were 3 and 8, since only those factors of 24 have a sum, namely 11, that is among the seven numbers that are possible. On the other hand, if P's product were 28, he would also know the sum was 11, because only the factors 4 and 7 add up to a number on the list. S would then not be able to make his final statement that he knows P's product, because he would have no way of deciding between the products 24 and 28. As a result, 11 is eliminated as a possible sum.
Could the sume be 23? No. S, unable to decide between 4+19 and 16+7, both of which add up to 23, would not know whether the product was 76 or 112. In the same way 27 is eliminated by 4+23=8+19=16+11=27; 29 is eliminated by 16+13=4+25=29; 35 is eliminated by 4+31=16+19=35, and 37 is eliminated by 8+29=32+5=37. There is only one possible sum left: 17. (In most of the above calculations, Gardner has violated his initial condition that both x and y must be no more than 20. The puzzle needs a higher limit on the values in order to be able to generate these ambiguous sets of factors.)
Seven possible pairs of numbers add up to 17, as follows:
Only one pair of numbers remains, 4+13. The product 52 has only one other pair of factors, 2x26, and they add up to 28, which is not a possible sum. (Actually, since we already have shown that the sum cannot be even, we know that one number must be odd and one even. Therefore, we can already rule out 2 and 26! Also, 26 is impossible because of Gardner's limit of 20!) Therefore, only if the numbers were 4 and 13 would P know for certain that S's sum is 17. From the fact that P knew this sum, S could then deduce that P's product is 4*13=52. Any other pair of numbers has ambiguities that do not allow both S and P to know the numbers. Since ambiguity increases as numbers get larger, it is reasonable to conjecture that there may be no other solution even when the upper bound is removed.
For readers who may want to prove that this result also holds when the bound is raised to 100, I shall add that the higher possible sums are
{ 41, 47, 51, 53 }.If the bound is raised still higher, computer programs seem necessary to rule out other solutions. I would be interested in hearing from anyone who knows the origin of this remarkable problem, or whether anyone has shown that the answer is unique when there is no upper limit to the two numbers.
Martin Gardner soon realized that he had made a mistake in simplifying the statement of the problem by lowering the bound to 20, and in his March, 1980 column he added the following note:
As hundreds of readers have pointed out, the "impossible problem" given in this department for December turned out to be literally impossible. Because I gave an upper bound of 20 for the two selected numbers the solution became totally inapplicable. I have since learned that the problem, with the correct upper bound of 100, was first submitted by David J Sprows to Mathematics Magazine, where it appeared in March, 1976 (Volume 49, Number 2, Page 96). An accurate solution appeared there in November, 1977 (Volume 50, Number 5, page 268). Richard Hess and Thomas Truscott were the first of many who sent me proofs that 62 is the lowest upper bound that allows a solution. I shall comment more fully on this problem in a future column.
(Note that the paper by Born, Hurkens and Woeginger cited below states that the lowest upper bound is actually 65, not 62!)
If Goldbach's conjecture is assumed to be true, then the numbers must be 5 and 6.
I haven't thought about why this must be so yet.
This puzzle is a fairly faithful restatement of the Freudenthal version, and the argument follows the same lines and need not be repeated here. (No explication is given in Smith's article.)
As we've noted, Martin Gardner's statement of the problem, using the lower bound of 20, is actually impossible - that is, if we make the typical assumptions common to this type of puzzle. The reason that Lee Sallows was able, nonetheless, to solve the problem had to do with the fact that he didn't actually know it was impossible. If Martin Gardner said there was a solution, then there must be one. And since thinking of the problem in the typical way yielded no solution that he could see, perhaps it was worthwhile questioning the usual assumptions.
Thus, let us consider the situation after P and S have been given their product and sum. An hour elapses, and then S calls P to say "I see no way you can determine my sum." Since we have not been told otherwise, we are free to assume that P would have called S first, well before an hour had elapsed, if he had been able to work out the sum quickly. So, as an hour elapses with no call from P, it may be reasonable to say that S actually knows two things, namely, his own sum, and the fact that P's product must not be one that makes it easy to determine S.
Considering the various possibilies, Sallows tried the pair S=8 and P=12, and discovered that, under his interpretation of the initial hour's silence, he could explain everything that happened.
And having discovered one solution that worked, Sallows then determined that under the stated limitations for the ranges of the two numbers, this was the only such solution. He did this by considering the 37 possible values of S, the corresponding pairs (X,Y), the corresponding products P and factorizations, and finding no other case that would allow for S and P to have the indicated conversation.
Let's go over the overt facts of the puzzle, and see how the covert facts of the solution explain what happens. As we begin, S has been given the sum 8, and P has been given the product 12.
S realizes that the possible partitions are 2+6, 3+5, and 4+4. S therefore knows that P must have the product 12, 15, or 16. Since 15 is uniquely factorable, the hour-long silence of the telephone suggests that P cannot have this value, or he would have called to announce the solution. Therefore, S believes that the underlying values can only be (2,6) or (4,4). At this moment, S cannot make any further progress to determine the value P, and if S has reasoned correctly, then he believes that P cannot have enough information to determine the value S.
Note that this interpretation of the puzzle includes factors not typically considered, namely the implications to S of P's initial silence. We could interpret this extra information as being an initial phone call from P, stating "I don't have enough information to determine your sum". Adding this statement explicitly would make it easier to compare the puzzle, as interpreted by Lee Sallows, with other variants.
On the telephone S says to P: "I see no way you can determine my sum."
Compare the puzzle at this point to the version by David Sprows. Can you see why they are not equivalent? Even if we add P's implicit initial statement that there is not enough information, we still have a difference in what S says. In the Sprows version, we have essentially:
Before you spoke, I already knew you could not know the answer.and in Sallows's version:
Now that you have spoken (implicitly or not), I can state that you cannot know the answer.The values S=8 and P=12 that work in Sallows's solution would not work in Sprow's interpretation. The puzzles are not equivalent.
P has the product 12, with legal factorizations are 2*6 and 3*4. P now considers the implications of S's remark.
An hour later, P calls back to say: "I know your sum."
The remainder of the story is easy to follow. S had the sum 8, and knew that P had either 12 or 16. S realizes that if P is equal to 16, there is not enough information to determine whether the solution is (2,8) or (4,4). But P just announced that the sum is known. Therefore, P must be 12, and that means the solution is (2,6). And so now it is time for S to make the final call.
Later S calls P again to report: "Now I know your product."
Fridman points out that he has fallen into the common trap of trying to make the puzzle easier, by imposing a low limit on the sum, which has the unintended effect of actually making the puzzle impossible. He points out that the puzzle can be solve if the puzzle is changed to require, say, that A+B<=64. We will work on the puzzle using this revised limit.
(It does not actually make a difference here, but notice that Green announces that he knows the sum, rather than saying he knows the values of the two numbers. Similarly, Blue claims to know the product, without claiming to know the two numbers. Of course, to know both the sum and product of two numbers (integer or not) is to know the numbers themselves.)
From the facts given, we can place limits on A and B:
2 <= A < B <= 62If we let S denote the sum, then we now know
5 <= S = A + B <= 64We can use P to denote the product, and a little bit of figuring will show that
6 <= P = A * B <= 63*64
Consider the implications of Green's statement that "I cannot figure out the sum". He knows the product. If there was only one way to decompose the product into two distinct factors, he would know A and B, and, obviously, their sum. In particular, if A and B were both primes, their product would be enough to determine their values. Therefore, Green's statement tells us A and B cannot both be prime numbers.
Now consider the implications of Blue's statement that "I already knew you (Green) couldn't (figure out the sum).". Before Green's statement, Blue already knew the sum S, and therefore, he knew that the product P must be one of the values 2*(S-2), 3*(S-3), ..This could be a lot of pairs of numbers. Suppose one pair of these numbers was both prime. If this pair was the actual values of A and B, then simply knowing P guarantees you can figure out A and B. But, before Green spoke, Blue already knew that this was impossible. How could he know this? Only if there is no way for the given value S to be formed by summing A and B that are both prime. In other words, the sum S must have the property that it cannot be formed as the sum of two primes that are possible values of A and B.
Now we already know that S is between 5 and 39, but this new information eliminates values as follows:
| S | Prime Sum? | Telltale Product |
|---|---|---|
| 5 | =2+3 | 6 |
| 6 | ||
| 7 | =2+5 | 10 |
| 8 | =3+5 | 15 |
| 9 | =2+7 | 14 |
| 10 | =3+7 | 21 |
| 11 | ||
| 12 | =5+7 | 35 |
| 13 | =2+11 | 22 |
| 14 | =3+11 | 33 |
| 15 | =2+13 | 26 |
| 16 | =3+13 | 39 |
| 17 | ||
| 18 | =5+13 | 65 |
| 19 | =2+17 | 34 |
| 20 | =3+17 | 51 |
| 21 | =2+19 | 38 |
| 22 | =3+19 | 57 |
| 23 | ||
| 24 | =5+19 | 95 |
| 25 | =2+23 | 46 |
| 26 | =3+23 | 69 |
| 27 | ||
| 28 | =5+23 | 115 |
| 29 | ||
| 30 | =11+19 | 209 |
| 31 | =2+29 | 58 |
| 32 | =3+29 | 87 |
| 33 | =2+31 | 62 |
| 34 | =3+31 | 93 |
| 35 | ||
| 36 | =5+31 | 155 |
| 37 | ||
| 38 | =7+31 | 217 |
| 39 | =2+37 | 74 |
Now it's not actually necessary that A and B be prime. We can also eliminate S=6, because this could be achieved by A=2, B=4, in which case the product is P=8, from which it is immediately possible to deduce that the factors are 2 and 4. Therefore, 8 is not a possible sum.
So, based on Blue's statement, Green can figure out that the only possible values for the sum are { 11, 17, 23, 27, 29, 35, 37 }.
Now notice that once Green figures out the only possible sums, he now actually knows the sum. In other words, knowing the product, and knowing the limited set of sums, he can determine the sum. This tells us that the product P must have the property that it cannot be factored in two different ways that add up to two different possible sums.
After Green announces that he has worked out the sum, Blue announces that he knows the product. This can only happen if the sum (which Blue knows) has the property that there is only one partition whose product would allow Green to work out the factors and hence the sum.
Moreover, if, in the list of possible sums, there is only one sum that has this property, then we, too, can figure out what the sum was, what its partition was, and what the product was.
Now it takes some tedious tabulation to show that there is only one S for which there is only one A+B for which the corresponding product P has only one valid factorization; However, it's not too hard to show, for particular (low) values of S from the list of possible sums, whether the stated conditions hold.
We'll just look at the first two cases, 11 and 17.
The sum can not be 11. If Mr Blue knows that the sum is 11, then there are at least two ways that P could have a product, derived from 11, that allows him to figure out the sum. In particular, P could be P=3*8=24, or P=4*7=28. If Mr Green has a product of 24 or 28, he knows that the factorization must be into an odd and an even value, so he knows the factors, and hence, of course the sum. But there is no way that Mr Blue would be able to tell whether 11 had been partitioned as 3+8 or 4+7, so he would never be able to get Mr Green's product. So 11 is out.
The sum could be 17. To see why, note that, of all the partitions of 17, there is only one that results in a product that is "unique", that is, that cannot be formed by another legal sum. This is because
S1 A1 B1 P A2 B2 S2
17 --> 2 15 --> 30 <-- 5 6 <-- 11
17 --> 3 14 --> 42 <-- 2 21 <-- 23
17 --> 4 13 --> 52 no other legal sum can form 52!
17 --> 5 12 --> 60 <-- 3 20 <-- 23
17 --> 6 11 --> 66 <-- 2 33 <-- 35
17 --> 7 10 --> 70 <-- 2 35 <-- 37
17 --> 8 9 --> 72 <-- 3 24 <-- 27
In other words, 17 has the property that there is only one partition
which creates a product P from which S can be determined. So if the sum
is 17, and Mr Green was able to backtrack from his product to its factors
to the sum of 17, he must have been working from a product of 52. And
therefore Mr Blue knows that the partition was 4+13, and he knows the
product too.
As I suggested before, if you now look at the other 5 possible sums, the same situation occurs as for the case of 11; that is, it is easy to find at least two partitions of the sum which result in products with the property that Mr Green could backtrack to the sum. That means that if Mr Blue knows the sum, and knows that Mr Green was able to backtrack from his product to its factors to the sum, Mr Blue still can't figure out which partition of the sum represents the factors.
Therefore, the sum is 17, the numbers are 4 and 13.
This is all very involved and elaborate. But that's partly because we are reasoning abstractly. Let's go through the motions once again, knowing now what the values are that Green and Blue are working with.
Born, Hurkens and Woeginger go into great detail about the mathematical and algorithmic theory behind the problem and its variants, and demonstrate that the pair (4,13) is always a solution of the original problem as long as the upper limit M is 65 or greater.
This suggests that the report that Martin Gardner's correspondents showed that the upper limit must be 62 or greater (see above) was misquoted or miscalculated.
Note also that there were two further parts to the Born, Hurkens and Woeginger paper, published in subsequent issues of the EATCS bulletin!
Thanks to Alexander Strehl for pointing out this reference, and for noting the discrepancies between the upper bounds of 62 versus 65.