Integer Logic Puzzle

Date: 04/22/2001 at 20:26:26
From: Andrew Walters
Subject: Very difficult logic puzzle driving me crazy

Two integers, m and n, each between 2 and 100 inclusive, have been 
chosen. The product, mn, is given to mathematician X. The sum, m + n, 
is given to mathematician Y. Their conversation is as follows:

X: I don't have the foggiest idea what your sum is, Y.

Y: That's no news to me, X. I already knew that you didn't 
   know.

X: Aha, NOW I know what your sum must be, Y!

Y: And likewise X, I have surmised your product!

Find the integers m and n.

Date: 04/23/2001 at 16:24:54
From: Doctor Jaffee
Subject: Re: Very difficult logic puzzle driving me crazy

Hi Andrew,

I can see why this problem is giving you difficulty. I don't have the 
answer either, but I can give you something to think about.

Suppose X looks at his slip of paper and sees the product 14. There 
are only 2 numbers that you can multiply together and get 14; 2 and 7.  
Therefore, X would know that the sum on Y's paper is 9. We can 
conclude, then, that 14 is not the number that X is looking at.

Suppose X sees the product 12. Now he doesn't know if m and n are 3 
and 4 or if they are 2 and 6. If they were 2 and 6, then Y's paper 
would say 8, but if Y's paper said 8, then Y would know that X's paper 
must say 12 or 15. But if X's paper said 15, X would know that Y had 
8. So, when X says he doesn't know what the sum is, Y can answer that 
he knew that, so X now knows that Y's sum could be 8 and accordingly Y 
knows that 12 might be the product.

If m and n were 3 and 4, Y would see a 7, which means that X must have 
10 or 12. But if X had a 10 he would know that Y had a 7, so X must 
have 12. So X knows that Y could have a 7.

So, if X has a 12, the best he can conclude from Y's response is that 
Y might have a 7 or an 8.

I'm pretty certain that this is the type of reasoning that you have to 
use to solve the problem. Find a number which, after going through the 
preceding argument, leads to only one possible conclusion and the 
problem will be solved.

Good luck and let me know if you find it or if you want to discuss the 
problem with me some more.

- Doctor Jaffee, The Math Forum
  http://mathforum.org/dr.math/   

Date: 04/23/2001 at 20:17:46
From: A Walters
Subject: Re: very difficult logic puzzle driving me crazy

I tried 3 and 8 for the two numbers.

P (like product) has 3x8 = 24
S (like sum) has 3+8 = 11

1. P can't know, that is sure.

2. S knew that P could not know, that is also correct.

3. Here is what P thinks : 24=3*8=4*6, so I know that S can only have  
   10 or 11. If S has 10, S would have thought for 2]: "Maybe the 
   numbers are 3 and 7 and then P, having 21, would have guessed the 
   two numbers. So I could not know if P would find or not the two 
   numbers." Since S said in 2] that he KNEW that P would not have 
   found, it implies that S is 11 and the two numbers are 3 and 8. So 
   P says:"Now I know the two numbers."

4. Here is now what S thinks:
   "The numbers are in the following list: {(2,9);(3,8);(4,7);(5,6)}
   So the P can only have: { 18 24 28 30 . If P has 18=2x9=3x6, he 
   would have thought:
   'S has either 11 or 9. But S has not 9, because if so, S would have 
   thought that I could have 2x7=14, in which case I would have found 
   the two numbers at once. And S said he knew I would not have found 
   the two numbers at once. So S has 11 and the numbers are 2 and 9.'"

So (], S can't find the two numbers: If they are 2 and 9, P would have 
found the numbers at 3].

----------- 3 --- 8, -------------------------------------

So S can't make any conclusion.
Since he does make a conclusion ("Now I also know the numbers") it 
means that the two numbers are not 3 and 8.

This is as close as I got. Is there a mathematical way of presenting 
the question? Please, I need more help! Can you prove that there 
definatly IS an answer?

Andrew Walters

Date: 04/24/2001 at 15:34:29
From: Doctor Jaffee
Subject: Re: Very difficult logic puzzle driving me crazy

Hi Andrew,

I haven't figured out an elegant way to prove that there is a unique 
answer, and I don't know of any formula to solve this problem. 
However, I can suggest a slightly different perspective which was 
suggested by a colleague of mine which may shed some light on the 
problem. I noticed that you changed X's name to P and Y's name to S, 
which I think was a good idea. I will follow that convention.

I previously suggested that we examine the problem from the point of 
view of P, the individual with the product. Let's take a look at the 
problem from S's perspective. Specifically, under what conditions 
would he know that P couldn't possibly guess the sum?

The smallest sum that S could have is 5. Then P would have 6 and know 
that S had 5. So, eliminate that possibility.

If S had 6, then P had 8.
If S had 7, then P had 10 or 12. Still, S wouldn't know in advance 
that P couldn't guess the sum because if P had 10 he would know that 
S had 7.

Similarly, my colleague and I eliminated every integer from 5 through 
17 as possible sums except for 11 and 17. Then we took a closer look 
at what would happen if S had 11. He would be thinking the pairs of 
numbers must be 2,9 or 3,8 or 4,7, or 5,6 with respective products 
18, 24, 28, 30. In each case P would not know what the sum could be 
and would say "I don't have the foggiest idea what your sum is, S."

S would respond with "That's no news to me, P. I already knew that you 
didn't know."

Now, Suppose that P had "30" on his paper. That would get P to think, 
"maybe S has 2+15 = 17 or 3+10 = 13, or 5+6 = 11. He wouldn't know if 
S had 11 or 17 so he couldn't respond "Aha, NOW I know what your sum 
must be, S!"

Consequently, all possible sums from 5 through 16 are now eliminated.

So, my best suggestion for you is to start with S having 18 and see 
what happens. Then plow through each sucessive number until you have 
established that there is only one possibility.

Let's see.  If S has 18, then he would think "maybe the two numbers 
are 7 and 11, in which case P would have 77 and P would know what S 
had. So, we can eliminate 18 as a sum.

Try it from there and if you find the solution, write back. I'm really 
curious to know. If you get stuck again, or if my explanation needs 
clarification, write back and we'll discuss it some more. 

- Doctor Jaffee, The Math Forum
  http://mathforum.org/dr.math/   

Date: 05/15/2001 at 09:58:37
From: A Walters
Subject: Re: Very difficult logic puzzle driving me crazy

I think I have a solution. Can you check it and show that it's unique?

Thanks.

One clue at a time.

"I haven't the foggiest idea what the sum is": X is looking at a 
number that can be factored in more than one way. In other words, m 
and n are not both prime, or there would be a unique factorization of 
mn into m times n. (And we aren't dealing with a huge number like 9801 
that can be factored more than one way, but only one way with both 
factors 100 or under.)

"I already knew that you didn't know": this is a much bigger clue. 
Y is looking at a number *that cannot be written as the sum of two 
primes*, or there would exist some possibility that X had been looking 
at a product of those two primes. Y is therefore not looking at an 
even number (Goldbach's conjecture has been verified quite a long way 
past 200!), nor is he looking at anything that is 2 more than a prime. 
The list of possible candidates for Y's number begins 11, 17, 23, 27, 
29, 35, 37, 41, 47....

"Aha! Now I know!": X is looking at a number that has several possible
sums - but _only one_ of those possible sums is on that list of 
possible candidates for Y.

For example, X might be looking at 18, and trying to decide whether Y 
is looking at 9 or 11. After Y says in effect "I am looking at one of 
11, 17, 23...", X will say, "Then it can't be 9, it must be 11!" Or X 
might be looking at 24, trying to decide whether Y had 10, 11, or 14, 
and likewise he'd be convinced that Y held 11.

If X held 30, he'd be trying to decide whether Y had 11, 13, or 17 - 
and he still wouldn't be able to tell between 11 and 17 - so X doesn't 
have 30.

"And I know your number, too": Well, Y's number must not be 11; we 
just saw that X could have either 18 or 24 if Y held 11. Still, we've 
run out of clues to help us; so nothing left to do now except check 
the cases. Smallest to largest, of course, since there are fewer 
possible ways to express the small numbers it'll be easier for us to 
avoid a "bad" case!

Checking the Y = 17 possibilites, we consider X=30, 42, 53, 60, 66, 
70, or 72. If X = 42, X would not be able to tell if Y had 17 or 23; 
if X = 52, X will know Y has 17 and not 28; if X = 60, 23 is possible; 
if X = 66, 35 is possible; if X = 70, 37 is possible; if X = 72, 27 is 
possible.

From this, we see that X = 52, Y = 17 satisfies all the constraints of 
the problem:

  X can't tell if Y has 17 or 28 at the beginning;

  Y knows that whichever of 30,42,52,60,66,70,72 X started with, 
  X can't tell what Y's number is;

  X eliminates 28 as a result of Y's first remark;

  Y eliminates 30,42,60,66,70,72 as a result of X's second remark.

So m = 4, n = 13 yields a satisfactory solution.

This only shows, by the way, that this is A solution. It doesn't pin 
down whether this is the ONLY solution, and it doesn't really narrow 
it down enough to make an exhaustive search of all the under-100 cases 
without computer aid reasonable. So, "prove or disprove: m = 4, n = 13 
is the only possible solution" remains an open question.

Date: 05/16/2001 at 16:50:36
From: Doctor Jaffee
Subject: Re: Very difficult logic puzzle driving me crazy

Hi Andrew,

It appears to me that you have a pretty good solution. It works. As 
far as the uniqueness of the solution, however, I have still not come 
up with a good proof. I suspect that a clever programmer could put the 
computer to use and exhaust all of the other possibilities to prove 
that 13 and 4 are the values of m and n, or perhaps come up with 
another solution. At any rate, I am still intrigued by the problem and 
will continue to work on it, but I expect it will take a while. I'll 
get back to you when I have more information.

I hope that the fact that I don't have a definitive answer for you 
right now is not too disappointing, but I can assure you that I will 
give it my best effort.  

I think you've come a long way on your understanding of the problem 
and eventually we will determine if your solution is unique.

- Doctor Jaffee, The Math Forum
  http://mathforum.org/dr.math/   

Date: 06/04/2001 at 14:45:08
From: Doctor Jaffee
Subject: Re: Very difficult logic puzzle driving me crazy

Hi Andrew,

I have good news for you. The solution: 4,13 is a unique solution (at 
least as long as we are restricting ourselves to integers from 2 to 
200 inclusive).

I have been consulting with Chris Andrews, Professor of Mathematics at 
Oberlin College, who took an interest in your puzzle. He wrote a 
computer program that went through every possibility and verified that 
your solution was unique.

He also expanded the problem to integers from 2 to 1,000 and found 
that 4,61 was also a solution. He suspects that if we continued to 
expand the domain there may be more, but he hasn't proved that.

At any rate, I've enjoyed working on this problem, as has Professor 
Andrews, and I am glad that the problem is no longer driving you 
crazy.

Best Wishes,

- Doctor Jaffee, The Math Forum
  http://mathforum.org/dr.math/