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