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://www.kermitrose.com/math/NewsLetter/LetterList.html

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,[1] and the name Impossible Puzzle was coined by

Martin Gardner.[2]

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