old riddle exact solution needed...

The Riddle regards two numbers between 2 and 99 (1<x, y<100)

Mr. X knows the product of the two numbers, Mr. Y knows the sum. The following Dialogue occurs:

Mr.X: I don't know the numbers Mr.Y: I know that you don't know the numbers, i don't know them either Mr.X:Now i know them Mr.Y: Me too

What are the two numbers?

You mean 1<x<100, 1<y<100.

No idea. This intrigues me.

I believe this puzzle is in the FAQ. I also believe that there's another step where in between where Mr. X tells Mr. Y 'I knew you did not know the numbers', which you need to get the solution.

The main insight you need to solve it is that Mr. X would know the solution if the two numbers were primes. Mr. Y knows from the sum that they cannot possibly both be prime. (this substantially cuts down on the possibilities).

The second insight is kinda hard to explain, it's that the 'I know you didn't know' gives the guy the info he needs to solve the puzzle.

I.e. say the numbers are 6 and 5, product guy gets '30' and the sum guy gets '11'. X has it narrowed fown to (10,3), (15,2), and (6,5) the sum guy knows the product guy couldn't solve it because there is no pair of primes that sums to 11. The fact that Y knows X didn't know tells X that the sum couldn't be 13 (because it's the sum of 11 and 2). But rhe sum could be 17 or 11, so that's not the a answer.

George

On Wed, 24 Jan 2001 10:02:29 +0100, 'Andreas Pfüller'

I saved this when it came up once before. This is NOT my reply below I just saved it and am pasteing it in. Pretty amazing to me.

SPOILER

The numbers are 4 and 13.

For the product 52: 52 = 2*26, 2+26 = 28 52 = 4*13, 4+13 = 17 There are 2 possible sums, so Mr. P does not know the numbers.

For the sum 17: 17 = 2+15, 2*15 = 30 17 = 3+14, 3*14 = 42 17 = 4+13, 4*13 = 52 17 = 5+12, 5*12 = 60 17 = 6+11, 6*11 = 66 17 = 7+10, 7*10 = 70 17 = 8+9, 8*9 = 72 Mr. Q does not know the numbers. Each of the products formed has at least 2 valid factorizations, so Mr. Q knows that Mr. P does not know the numbers.

If the sum were 28, the numbers could have been 5,23 or 11,17; in either case Mr. Q could not have stated 'I Know that you don't know the mumbers.' Therefore Mr. P knows now that the sum is 17 (and not 28), and thus the numbers are 4 and 13.

If the product were anything other than 52, Mr. P could not have stated 'Now I know them' at this point. For example, in case of 30, the possible sums are 11, 13 and 17. With both 11 and 17 Mr. Q could have stated 'I Know that you don't know the mumbers.' Therefore Mr. Q knows the product is 52, and hence the numbers are 4 and 13.

A computer search shows that this is the only possible solution.

Here's a more complete explanation:

First, we know from the range [2,100] that the Sum is between 4 and 200, and the Product is between 4 and 10,000 (inclusive).

<<Statement 1>> Mr. P.: I do not know the two numbers.

This tells us that the Product can be factored in at least two ways using numbers from the range 2 - 100.

Therefore, both numbers can't be prime. Furthermore, neither of the numbers can be a prime greater than 50 even if the other number isn't prime.

<<2>> Mr. S.: I knew that you didn't know the two numbers. This is a more interesting statement. This says that for the particular Sum that S has been told, he has calculated all possible pairs of numbers in the range that add to his Sum, multiplied each pair, and determined that in no case do any of his pairs produce a Product that can be uniquely factored.

It turns out that this eliminates all but 10 possible Sums. First, all even numbers are the sum of two primes. Second, anything bigger than 53 might be the Sum of 53 plus something, which would have a unique factorization. Third, anything that is a prime plus 2 can be eliminated. Finally, 51 is a special case. 51 is 17 + 34, and 17 * 34 can only be factored one way with numbers in the range.

At this point, 11 17 23 27 29 35 37 41 47 53 are the only possible Sums.

<<3>> Mr. P.: Now I know the two numbers.

<<4>> Mr. S.: Now I know the two numbers.

Let's look at <<3>> and <<4>> together. We go through each possible Sum, and all the pairs of numbers that can add up to that Sum, and then the Product each pair would produce, and then all the ways to factor that product. It's tedious, and I'll only do a few.

First, try Sum = 11. This could be 2+9, 3+8, 4+7 or 5+6.

Look at 2+9. Now, 2*9 = 18, which can be factored as 2*9 or 3*6. Now, 2+9 = 11, and 3+6 = 9. Since 11 is in the list from part <<2>> and 9 is not, P could make statement <<3>> if his Product were 18. So far, so good.

Now, look at 3+8. 3*8 = 24, which can be factored as 2*12, 3*8, or 4*6, which give Sums of 14, 11 and 10. Since only 11 is on the list from part <<2>>, P could make statement <<3>> if his Product were 24. But, S could not make statement <<4>> if his Sum is 11, because he can't tell 2+9 from 3+8.

The two numbers must be 4 and 13 (Sum = 17, Product = 52). You should be able to see that this works, and eliminate any other possibilities.