The professor tells Peter the product of two positive integers and Sam their sum. At first, nobody of them knows the number of the other. One of them says: You can't possibly guess my number. Then the other says: You are wrong, the number is 136. Which number did the professor tell them respectively? Give reasons for your claim.
Problem
Source: Mediterranian Mathematics Competition 2005, Problem 1
Tags: combinatorics proposed, combinatorics
07.02.2006 23:13
I think something is missing in the statement. The solutions of the problem are numbers which their sum can be deduced from their product, or their product from their sum.Obviously, the first way is impossible except for 2 and 3, the second imposes that the number can be written as a product in 1 way, so it must a prime number multiplied by 1, hence there can be a solution for the problem if 135 was prime: false. Otherwise it will be ok if we had 138 instead of 136, but that would make the problem trivial...Am i missing something?
08.02.2006 00:38
no one to check? (sorry for this post)
10.02.2006 21:05
It might indeed be a typo ...
13.02.2006 02:39
Hi, maskman, I think you have forgotten the statement, that the guessing person is not only using his number to deduce the number of the other, he also uses the knowledge, that the other knows that he can't deduce the other number by only his own number. I Hope that my solution is correct Obviously, if the product is 136, Sam cannot deduce the product by the knowledge, that Peter knows that he can't deduce the product with his sum, so the sum is 136. A possible solution would be e.g. if Peter had 135. When Sam said that Peter couldn't deduce the sum, he was right because the only possible case when Peter was able to was if the sum was 1+prime, which is wrong in this case (135 is not prime). But now Peter knows that Sam knows that Peter cannot deduce the sum by the mere knowledge of the product. Let Peter's number be $P$. If we consider the set of all $\{x+\frac{P}{x}\mid x|P\}$, then every number in this set except for one must be 1+prime. This is true for $P=135$, because in this case, Peter would know that Sam has one of the numbers 136, 48, 24, 32. Everyone of these numbers except for 136 is 1+prime. But if Sam had 48, 24 or 32 then Sam could not know that Peter cannot deduce the sum because Sam cannot tell for sure that Peter has no prime number. Hence Peter knows that Sam must have 136. Now we still have to prove that 135 is the only solution for $P$. But that's actually trivial because if there was another solution $P'$, then the set defined above would contain at least two numbers which do not have the form 1+prime (136 and $P'+1$) Hence Sam's number must be 136 and Peter's must be 135.
18.02.2006 23:06
WOW! it's one of the trickiest problems i have ever found and made me feel really stupid!! i would even say that the proposer deserves a special prize i also wonder if many students solved it during the competition....