Math Newsletter number 20; Wednesday, December 8, 2010.
If you send any part of this newsletter to a friend, please
also include this paragraph. To subscribe or unsubscribe,
send a personal email request to kermit@polaris.net
Archive is at

http://en.wikipedia.org/wiki/Impossible_Puzzle

The Impossible Puzzle, also named Sum and Product Puzzle is a
puzzle called "impossible" because it seems to lack
sufficient information for a solution. It was first published
in 1969, and the name Impossible Puzzle was coined by
Martin Gardner.

The puzzle is solvable, though not easily. There exist many
similar versions of puzzles.

Puzzle

Given are X and Y, two integers, greater than 1, are not
equal, and their sum is less than 100. S and P are two
mathematicians;
S is given the sum X+Y, and P is given the product X*Y of
these numbers.

* P says "I cannot find these numbers."
* S says "I was sure that you could not find them."
* P says "Then, I found these numbers."
* S says "If you could find them, then I also found them."

What are these numbers?

Since both x and y are > 1; x*y is not a prime.

* P says "I cannot find these numbers."

This implies that x*y is not the product of two primes,
for otherwise, P would know what x and y were.

x*y must be the product of at least 3 primes.

For example,

2*2*2,
2*2*3,
2*3*3,
3*3*3,
2*2*5,
2*3*5,
...

* S says "I was sure that you could not find them."

This implies that none the ways of adding two integers,
each > 1, to get (x+y), is the addition of two primes.

Otherwise, S would not know, in advance, that P could not
determine what x and y were.

X > 1 and y > 1.

Minimum value of x is 2.
Given x is 2, and y is not same as x,
minimum value of y is 3.

Minimum value of (x+y) is 5.

(2+3) = 5.

(x+y) cannot be 5 because
then the product might be 6,
and if the product were 6,
P would know immediately what x and y were.

Try (x+y) = 6
2+4 = 6
1+5 = 6 is not permitted because x > 1 and y > 1.
3+3 = 6 is not permitted because x is different than y.

(x+y) cannot be 6 because,
if it were , the x and y would be 2 and 4,
and x*y would be 8.

If P has x*y = 8, then P would know immediately,
that x and y were 2 and 4.

Try x+y = 7.
(2+5)=7.
(x+y) cannot be 7.

Try x+y = 8.
(3+5)=8.
(x+y) cannot be 8.

Try x+y = 9.
(2+7) = 9.
(x+y) cannot be 9.

Try x+y=10.
(3+7)=10.
(x+y) cannot be 10.

Try x+y=11.

11=2+9=3+8=4+7=5+6

Maybe.

Record 11 as a possible sum (x+y).

5+7 = 12 eliminates 12 as sum (x+y).
2+11 = 13 eliminates 13 as sum (x+y).
3+11 = 14 eliminates 14 as sum (x+y).
2+13 = 15 eliminates 15 as sum (x+y).
5+11 = 16 eliminates 16 as sum (x+y).

17=8+9=7+10=6+11=5+12=4+13=3+14=2+15

Record 17 as a possible sum (x+y).

5+13 = 18 eliminates 18 as sum (x+y).
2+17 = 19 eliminates 19 as sum (x+y).
3+17 = 20 eliminates 20 as sum (x+y).
2+19 = 21 eliminates 21 as sum (x+y).
3+19 = 22 eliminates 22 as sum (x+y).

23=2+21=3+20=4+19=5+18=6+17=7+16=8+15=9+14=10+13=11+12

Record 23 as a possible sum (x+y).

5+19 = 24 eliminates 24 as sum(x+y).
2+23 = 25 eliminates 25 as sum(x+y).
3+23 = 26 eliminates 26 as sum(x+y).

27=2+25=3+24=4+23=5+22=6+21=7+20=8+19=9+18=10+17=11+16
=12+15=13+14

Record 27 as a possible sum (x+y).

5+23 eliminates 28 as a possible sum (x+y).

29=2+27=3+26=4+25=5+24=6+23=7+22=8+21=9+20=10+19=11+18
=12+17=13+16=14+15

Record 29 as a possible sum (x+y).

7+23=30 eliminates 30 as a possible sum (x+y).
2+29=31 eliminates 31 as a possible sum (x+y).
3+29=32 eliminates 32 as a possible sum (x+y).
2+31=33 eliminates 33 as a possible sum (x+y).
3+31=34 eliminates 34 as a possible sum (x=y).

35=2+33=3+30=4+29=5+28=6+27=7+26=8+25=9+24=10+23=11+22
=12+21=13+20=14+19=15+18=16+17.

Record 35 as a possible sum (x+y).

5+31=36 eliminates 36 as a possible sum (x+y).

37=2+35=3+34=4+33=5+32=6+31=7+30=8+29=9+28=10+27=11+26
=12+25=13+24=14+23=15+22=16+21=17+20=18+19.

Record 37 as a possible sum (x+y).

7+31=38 eliminates 38 as a possible sum (x+y).
2+37=39 eliminates 39 as a possible sum (x+y).
3+37=40 eliminates 40 as a possible sum (x+y).

41=2+39=3+38=4+37=5+36=6+35=7+34=8+33=9+32=10+31
=11+30=12+29=13+28=14+27=15+26=16+25=17+24=18+23
=19+22=20+21

Record 41 as a possible sum (x+y).

5+37=42 eliminates 42 as a possible sum (x+y).
2+41=43 eliminates 43 as a possible sum (x+y).
3+41=44 eliminates 44 as a possible sum (x+y).
2+43=45 eliminates 45 as a possible sum (x+y).
3+43=46 eliminates 46 as a possible sum (x+y).

47=2+45=3+44=4+43=5+42=6+41=7+40=8+39=9+38=10+37
=11+36=12+35=13+34=14+33=15+32=16+31=17+30=18+29
=19+28=20+27=21+26=22+25=23+24

Record 47 as a possible sum (x+y).

7+41=48 eliminates 48 as a possible sum (x+y).
2+47=49 eliminates 49 as a possible sum (x+y).
3+47=50 eliminates 50 as a possible sum (x+y).

Becoming tedious.

All even positive integers > 6 will be eliminated as a
possible sum, by being the sum of two primes.

All odd positive integers that are 2 more than an odd prime,
will be eliminated by being 2 + a prime.

The odd primes < 100 are

3,5,7,11,13,17,19,23,29,31,37,41,43,47,
53,59,61,67,71,73,79,83,89,97

This implies that the only candidates for sum (x+y) are

11,17,23,27,29,35,37,41,47,
51,53,57,59,65,67,71,77,79,83,87,89,93,95,97

* P says "I cannot find these numbers."
* S says "I was sure that you could not find them."
* P says "Then, I found these numbers."
* S says "If you could find them, then I also found them."

When P hears S say
"I was sure that you could not find them."

Then he knows that the sum (x+y) is one of

11,17,23,27,29,35,37,41,47,
51,53,57,59,65,67,71,77,79,83,87,89,93,95,97

* P says "Then, I found these numbers."

P factors his product in all possible ways and discovers that
exactly one of the possible sums is a candidate sum.

What are the possible products?

If sum = 11?
11 = 2+9=3+8=4+7=5+6

Initial candidate products for sum=11 are
2*9=18=3*6 ==> {2+9=11, 3+6=9} ==> {x,y} = {2,9}
3*8=24 ==> {3+8=11 } ==> {x,y} = {3,8}
4*7=28 ==> {4+7=11} ==> {x,y} = {4,7}

* P says "Then, I found these numbers."
* S says "If you could find them, then I also found them."

Since S figured out the {x,y} from the fact that P figured
out what they were, it must be that exactly one of the ways
of summing x+y leads to a product that allows P to figure out
{x,y}.

Since all three sums, 2+9, 3+8, 4+7, if they represented the
true value of {x,y}, would enable P to calculate {x,y},
it must be that 11 is not the sum (x+y).

Try (x+y)=17.

17=2+15=3+14=4+13=5+12=6+11=7+10=8+9

If (x,y)=(2,15) the xy = 30 = 5*6 = 3*10 = 2*15

P would calculate 5+6 = 11, 3+10 = 13, 2+15=17.

The candidate sums are:

11,17,23,27,29,35,37,41,47,
51,53,57,59,65,67,71,77,79,83,87,89,93,95,97

Both 11 and 17 are candidate sums. xy is not 30.

If (x,y)=(14,3),P would calculate,
3*14=42=2*21=3*14=6*7

3+14=17 is a candidate sum.
2+21=23 is a candidate sum.
xy is not 42.

If (x,y) = (4,13), P would calculate,

4*13=52=2*26=4*13
4+13=17 is a candidate sum.
2+26=28 is not a candidate sum.
P would conclude that (x,y) = (4,13).

Before S can be sure, S must also check out

5+12 = 17.

If (x,y)=(12,5) then xy = 60.
P would calculate 60 = 4 * 15 as the only factoring of 60
which gives x even and y odd.
4+15 = 19 is not a candidate sum.
xy is not 60.

If (x,y) = (11,6) then xy = 66 = 2*33 = 6*11.

Both 2+33 and 6+11 are candidate sums.
xy is not 66.

* P says "I cannot find these numbers."
* S says "I was sure that you could not find them."
* P says "Then, I found these numbers."
* S says "If you could find them, then I also found them."

With x=4, y = 13,
the sum is 17 and the product is 52.

* P says "I cannot find these numbers."

52 = 4*13=2*26. P does not know whether {x,y} = { 4,13} or
{2,26}.

* S says "I was sure that you could not find them."

(x+y)=17.
17=8+9=7+10=6+11=5+12=4+13=3+14=2+15.

None of the products,
8*9, 7*10, 6*11, 5*12, 4*13, 3*14, 2*15 are the product of
two primes.

* P says "Then, I found these numbers."

P knows the product is 52.

52=4*13=2*26.
4+13 is a candidate sum.
2+26 is not a candidate sum.

* S says "If you could find them, then I also found them."

S examines each of the products,

8*9=72, 7*10=70, 6*11=66, 5*12=60, 4*13=52, 3*14=42, 2*15=30,

and confirms that only 4*13=52 would enable P to figure out
for sure what {x,y} were.

{x,y} = {4,13} is one possible solution to this puzzle.

I suppose that one could prove that it is the only solution.

I won't do that here.

Kermit

References

1. Hans Freudenthal, Nieuw Archief Voor Wiskunde,
Series 3, Volume 17, 1969, page 152
2. Scientific American Volume 241, December 1979