Chapter 3

THE IMPOSSIBLE PROBLEM

If you think it’s simple, then you have misunderstood the problem.

Bjarne Strustrup

Double Dutch

The Dutch mathematician, mathematical historian and educator Hans Freudenthal was an original and inspirational thinker. Radio telescopes are pretty complicated mechanisms. Freudenthal therefore (and reasonably) argued that electronic communication with extraterrestrial life would require of them the capacity to count and to recognize that 2 + 2 = 4 and from this conviction he created a mathematically based interstellar language called Lingua Cosmica (the language of the cosmos, which was published in his book LINCOS: Design of a Language for Cosmic Intercourse in 1960). It seems that he also created a remarkable logical puzzle, which we will consider in this chapter. It was published in 1969 as problem number 223 in the Dutch Nieuw Archief voor Wiskunde (New Archive for Mathematics), and in its original form looked like:

The reader may appreciate the following translation:

Other and Later Versions

The puzzle in its English form above reappeared as problem 977 in the Problem section of the March 1976 issue of Mathematics Magazine (volume 49(2)), submitted by David J. Sprows. An editor’s footnote describes it as

A succinct variation of some past problems in the American Mathematical Monthly, especially E776, E1126 and E1156,

an observation which dates the problem’s variations at 1948, 1955 and 1956 respectively, and assuredly they are significant variations, which as we will see is a highly noteworthy matter. It is almost inevitable that Martin Gardner was responsible for bringing the problem to the greater mathematical puzzling public and certainly to the attention of this author. In the Mathematical Games section of the December 1979 issue of Scientific American, which he subtitled, ‘A pride of problems, including one that is virtually impossible’, Gardner listed several short, unrelated problems to challenge his readers, the first of which is his version of Freudenthal’s puzzle, told to him by the late Canadian puzzle and magic genius Mel Stover. The statement was preceded by the opening paragraph:

It is hoped that the following unrelated problems will be new and challenging to most readers. Number 1 is so difficult, with a solution that would take up an inordinate amount of space next month that it is answered at the end of the column. Readers who relish a tough challenge are urged to work on the problem before they read the solution. If there is a simpler solution to the problem than the one given, I should like to know about it. The other problems will be answered at the end of next month’s column.

He termed number 1 ‘The impossible problem’.

Gardner’s original version is as follows:

Two numbers (not necessarily different) are chosen from the range of positive integers greater than 1 and not greater than 20. Only the sum of the two numbers is given to mathematician S. Only the product of the two is given to mathematician P.

On the telephone S says to P, ‘I see no way you can determine my sum.’

An hour later P calls him back to say, ‘I know your sum.’

Later S calls P again to report, ‘Now I know your product.’

What are the two numbers?

He continued by remarking:

To simplify the problem, I have given it here with an upper bound of 20 for each of the two numbers. This means that the sum cannot be greater than 40 or the product greater than 400. If you succeed in finding the unique solution, you will see how easily the problem can be extended by raising the upper bound. Surprisingly, if the bound is raised to 100, the answer remains the same.

We can see that Gardner’s version is a variant of the original, most particularly and significantly because of the number and order of the statements. Over the years the problem has spawned any number of other variants each of which continues to maintain an air of mystery and surprise; it simply does not seem possible to solve any of its forms with the information given, but the solutions do exist, and involve the use of one of the great conjectures of mathematics, the Goldbach Conjecture, which is described in the appendix (page 224) (see Torsten Sillke’s page www.mathematik.uni-bielefeld.de/∼sillke/).

The exact wording of any variant is critical. Lee Sallows considered Gardner’s version in great detail in his article ‘The impossible problem’ (1995, The Mathematical Intelligencer 17(1):27–33) and we will look at a particular formulation which has, for reasons of the names’ first letters, been framed in terms of the two perfect logicians Polly and Sam. Notice the upper bound.

Polly and Sam are visited by a friend. The friend, having thought of two integers between 2 and 800 inclusive, whispers their product to Polly and their sum to Sam. The following dialogue results:

1. Polly: I don’t know the two numbers.

2. Sam: I know that and neither do I.

3. Polly: I know the two numbers.

4. Sam: So do I.

What are the two numbers?

We will draw inferences from the information contained within Polly’s and Sam’s statements, but it should be made clear that, in all likelihood, other inferences than those which we make can be made, which could lead to the elimination process behaving in a different manner to the one described below. This is not so much a puzzle to solve, but one to investigate.

First, although the emphasis it provides is useful, the ‘and neither do I’ part of Sam’s response is redundant. The only way Sam could know the numbers at this stage is if they are the pair (2, 3) and this possibility has already been eliminated by Polly.

Keeping track of the consequences of the deductive processes is greatly assisted by the use of a computer and the problem has long been used as an opportunity for Artificial Intelligence programming, with many programs having been written in languages such as Lisp and Prologue. We will give a general schema in a pseudo-code, which can be translated into a specific language.

An Analysis

If we call the two integers x and y, we can make the following deductions:

After statement 1.

x and y cannot both be prime. If they were, the given product could be factored in only one way and Polly would know the numbers, which would contradict her first statement.

x × y cannot be the cube of a prime p otherwise Polly would know that the numbers are p and p².

After statement 2.

x + y must be odd. This is where we need the Goldbach Conjecture. If x + y is even, using the conjecture, it is possible for it to be written as the sum of two primes. If this were the case, it would again mean that both x and y would be prime, in which case Sam could not be certain that Polly could not deduce the values of x and y.

x + y is not 2 more than a prime. If it were, then x could be 2 and y could be prime, in which case the product would be 2 y and again Sam could not be certain that Polly could not deduce the values of x and y.

x + y < 403. If not, x + y 403 and this means that x (say) could be the prime 401 with y ∈{2, 4, 6, . . . , 800} even, since x + y is odd. This means that the product known to Polly would be 401 y with the smallest factor of y being 2. It must then be that x = 401, otherwise x 2 × 401 = 802 and that is out of the allowed range. Therefore, if Sam were in possession of the sum x + y 403, again he could not be certain that Polly could not deduce the values of x and y.

Using this information a list of allowed number pairs can be formed; call it L.

After statement 3.

Since Polly tells Sam that she can now deduce the two numbers, it must be that her product appears uniquely in the products of the members of L. Polly can look at L, form the products and identify the unique pair that generates her given product.

After statement 4.

Since Sam tells Polly that he can now deduce the two numbers, it must be that his sum is uniquely formed from L. He can do for the sum what Polly did for the product.

With our analysis in place we can develop our pseudo-code and detail the results of a computer program based on it. Before we do this we can reduce the size of the list from its original 799² = 638 401 entries by assuming that x y, since addition and multiplication are commutative operations.

Pseudo-Code

Array A := {(x, y): {x, 2, 800}, {y, x, 800}}

A := {(2, 2), (2, 3), (2, 4), . . ., (799, 799), (799, 800), (800, 800)} LENGTH[A] = 319, 600.

After statement 1.

A → SELECT [A] : {(x, y) : (NOT[PRIME[x]&PRIME[y]])

&(x × y ≠ prime³)}

A:= {(2, 6), (2, 8), (2, 9), (2, 10), (2, 12), . . . ,

(798, 800), (799, 800), (800, 800)}

LENGTH [A] = 309, 861.

After statement 2.

A → SELECT [A] : {(x, y) : (x + y ODD)&(x + y < 403)

&(x + y = prime + 2)}

A:= {(2, 9), (2, 15), (2, 21), (2, 25), . . . ,

(198, 199), (198, 203), (199, 202)}, (200, 201)

LENGTH[A] = 12, 996.

This is list L.

After statement 3.

A → SELECT [A]: {(x, y) : x × y is unique}

A: = {(2, 9), (2, 25), (2, 27), (2, 49), . . . ,

(198, 199), (198, 203), (199, 202), (200, 201)}

LENGTH[A] = 4,471

Polly searches L for her known product, which must be unique.

After statement 4.

A → SELECT[A] : {(x, y) : x + y is unique}

A: = {(4, 13)}

LENGTH[A] = 1.

Sam searches L for his sum.

The unique solution is the pair (4, 13).

With a mathematical programming language available, there are functions which will greatly help with this sifting; otherwise some judicious programming is needed!

Further Thoughts

There is significance in there being just one member in the final list in the pseudo-code. It not only means that the provider of the numbers has no choice in them if the dialogue is to be correct, but also that an observer who has listened to Polly and Sam’s conversation could also identify the two numbers. To understand the problem completely, it is important to distinguish between what Polly and Sam know and what an observer knows from listening to them. The first two statements make no use of the specific numbers that Polly and Sam have been given and the listening observer could make the same deductions and arrive at the list L. L has many number pairs and Polly uses her knowledge of her number to pick the only pair in it that will do. Sam then does the same with ‘product’ replaced by ‘sum’. In fact, now neither has need of the precise number that was given them as each could both add and multiply the number pairs and arrive at the unique (4, 13). Since this is true the observer could have solved the problem himself and told Polly and Sam what the two numbers are.

We have given the upper bound as 800; now let us vary it. There is an important event when the upper bound is 123. The pair (4, 61) makes a first appearance in L, since it just passes through the sieve made by the first two statements. Having made its appearance, (4, 61) continues to be eliminated, with 4 + 61 = 65 not unique—until the upper bound is 867—when the pairs that sum to 65 and which cause (4, 61) to be eliminated are themselves eliminated, leaving that pair to pass through, and for the first time. The final list scrutinized by Polly and Sam is then {(4, 13), (4, 61)}. Now Polly and Sam have to use their knowledge of the exact value to arrive at the answer. For the first time, the provider of the numbers could have chosen a second number pair and the observer is not able to solve the problem.

Notice that (4, 61) cannot be eliminated by Polly since the only possible other pair multiplying to 244 is (2, 122) which has both entries even.

This is no more than a special case of the form (2ⁿ, p), where p is prime, with (4, 13) the first example of it. The product of the two numbers is 2ⁿp, which cannot be duplicated in L since to do so would mean moving a 2 across to the prime, and again this makes both numbers even. These numbers can only be eliminated from L by Sam. If other number pairs in L sum to 2ⁿ + p, the pair will be eliminated, otherwise Sam will have to use his knowledge of the exact value of the sum to make his second statement. In this sense pairs of numbers of this type are the most difficult to eliminate from L and as we increase the upper bound we see more and more of them appear, but to do this we need to generalize the third conclusion we made from statement 2. The earlier argument resulting in the bound of 443 is a special case of the following: if x and y each have an upper bound of n, then x + y < where is the smallest prime greater than or equal to N.

The justification is really the same as before. If x + y one of x or y (say x) might be and y must be an even integer 2 or greater. Polly would then be in possession of the product y. She would therefore know the two numbers, since the only possible ambiguity would be in moving a factor from y to and the smallest factor that y can have is 2 and that would make x = 2 × > n.

If we run the program for the upper bound of 2000, the final list is

{{4, 13}, {4, 61}, {16, 73}, {32, 131}},

and if we go as far as an upper bound of 5000, it becomes

{{4, 13}, {4, 61}, {4, 229}, {16, 73}, {16, 111},

{32, 131}, {32, 311}, {64, 73}, {64, 309}, {67, 82}}.

And this brings us to the end of our own investigation into the problem!

Three Variants

Finally, we offer the reader three standard but lesser-known variants—but without answers.

Variant 1. Three people V, C and X are joined by another person M, who holds hidden the sixteen cards: A, Q, 4 (♥); J, 8,7, 4, 3, 2 (♠); K, Q, 6, 5, 4 (♣); A, 5 ().

M selects a card at random and tells V the card’s value and C its colour. After this, in X’s hearing, he asks them the question, ‘Do you know which card I have?’ The following conversation ensues:

V : I don’t know what the card is.

C : I knew that you didn’t know.

V : I know the card now.

C : I know it too.

X thinks for a moment, and concludes correctly what M’s card is. How is this possible?

Variant 2. Each of A, B and C is wearing a hat on which a positive number is printed. Each can see the numbers on the others’ hats but not their own number. All are told that one of the numbers is the sum of the other two. The following statements are made in the hearing of all:

A : I cannot deduce what my number is.

B : I cannot deduce what my number is.

C : I cannot deduce what my number is.

A : I can deduce that my number is 50.

What are the numbers on the other two hats?

Variant 3. A person M joins two others, A and B. M whispers to A the sum of two natural numbers and to B the sum of the squares of the same two natural numbers. Each knows the nature but not the detail of the information being conveyed. The following conversation takes place:

B : I do not know the numbers.

A : I do not know the numbers.

B : I do not know the numbers.

A : I do not know the numbers.

B : I do not know the numbers.

A : I do not know the numbers.

B : I know the numbers.

What are the two natural numbers?