Integer Logic PuzzleDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/