tough logic problem

[wins_pot]

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.

can you prove uniquenss? (i can't. don't even know if it's possible)

[NiceCatch]

Excellent question. Quick question: can m=n?

I'll give my reasoning so far: clearly m and n are not prime numbers, otherwise X would easily be able to tell exactly what they are. Likewise, the sum of the two numbers indicates that they are not prime, which tells Y that X couldn't know what the numbers are. So...
What numbers between 4 and 200 (or 5 and 199, if m doesn't equal n) are clearly not the sums of prime numbers? Sounds like a number-cruncher to me... but then there are only 197 possibilities. Maybe I'll go through all of them. [img]/images/graemlins/grin.gif[/img]

[wins_pot]

m and n are not equal.
it's solvable without crunching numbers.
that said, this problem is tough - it takes smart people a very long time.

[NiceCatch]

Update: Ok, so every even number can be stated as the sum of two primes. Odd numbers can only be stated as the sum of two primes if they are equal to (2+j), where j is another prime number.

The one factor I have not taken into consideration is the fact that X's knowing what the numbers were allowed Y to know what the numbers were. Hmmm... Ok, I think I have at least the logic down. Since X figured out precisely what the two numbers were, knowing that both of them were not prime, Y could then figure out what the two numbers were if and ONLY IF there was not more than one way for the potential m and n combos to add up to a value that could not be a sum of primes. For example, say m*n=30. m could equal 5, n could equal 6 ---> m+n=11. Or, m could equal 2, n could equal 15 ---> m+n=17. Given this circumstance, there's no way X could figure out m & n are. So given that, there must be m*n such that m+n=k, where k is not equal to the sum of two primes, and k is unique (i.e. there is only one combination of m and n that will produce k).

[NiceCatch]

Ok, I'm going to step through a couple of examples. I've found one combination that works already, which I'll review below.

Say m+n=11 (11 is not a sum of primes)
(m,n)=(5,6),(4,7),(3,8), or (2,9)
Say (m,n)=(5,6) ---> m*n = 30, so (m,n) could equal (5,6), (15,2), (3,10) in X's eyes. However, 3+10=13=11+2 (two primes), so that gets thrown out the window. As does m+n=11, because in such a case, X could believe (m,n) is EITHER (5,6) OR (15,2). Since X KNOWS what the combo is, m*n can't possibly equal 30, therefore (m,n) can't be (5,6).

If you go through all the possibilities for m+n=11, you'll find that both (3,8) and (4,7) have products whose factors only add up to a "k" number (not a sum of two primes) in only one way. This means that Y would see TWO possible pairs that would fit. So m+n therefore cannot equal 11.

Let's try the next smallest "k" number (not a sum of two primes), 17. (m,n) = (2,15), (3,14), (4,13), (5,12), (6,11), (7,10), or (8,9).

Doing the same process, you find that six of the pairs named have products whose factors can add up to more than one "k" number. This obviously discounts them.

Interestingly, the pair (4,13) does not have a product whose factors can add up to more than one "k" number.

4*13=52
52=(4*13) or (2*26), 2+26=28=23+5 (two prime numbers), therefore (m,n) can be (4,13).

So that is one solution. This does not discount the possibility of other solutions. Basically there are two stipulations: m*n must be a number such that there must be a unique set of two of its factors that adds up to the summation of two non-primes. Additionally, m+n must equal some z where the following is true: given all pairs of numbers between 2 and 100 that add up to z, there must be a unique set of two numbers such that any two factors of the product of the two numbers can only add up to the summation of two non-prime numbers in a single way.

Sorry, I know there is some better way to word that. I hope the gist of it comes through, though.

[wins_pot]

damn. my last post didn't go through. in short - you're right, (4,13) is the solution. great work. it's a tough problem. i don't know how to prove uniqueness.

[thylacine]

I didn't look through the argument, but note that the sum also could not be of the form p^2+p for prime p, since p^3 factorises uniquely into factors bigger than one.

[Rasputin]

[ QUOTE ]
So that is one solution. This does not discount the possibility of other solutions. Basically there are two stipulations: m*n must be a number such that there must be a unique set of two of its factors that adds up to the summation of two non-primes. Additionally, m+n must equal some z where the following is true: given all pairs of numbers between 2 and 100 that add up to z, there must be a unique set of two numbers such that any two factors of the product of the two numbers can only add up to the summation of two non-prime numbers in a single way.

[/ QUOTE ]

I’d like to bump this to ask why.

Going back to the problem, we know the following facts:

1) There is a pair of distinct numbers from 2-100 inclusive.
2) One mathematician (P) was given the product of the two numbers.
3) Another mathematician (S) was given the sum of the two numbers.
4) P cannot determine what the sum of the numbers is
5) S knows that P cannot determine what the sum of the numbers is
6) When P finds out that S knows that P cannot determine what the sum of the numbers is, it provides him with enough information to determine what the sum of the numbers is
7) When S finds out that the above is true, it gives him enough information to determine what the product is.
8) From #4 we can deduce that there is more than one pair of numbers in the given range that would produce the product. Crunching the numbers gives me 2880 distinct products, 1793 of which only have one pair of factors in the required range leaving 1087 with more than one potential pair.
9) From #5 we can deduce that the sum is such that all of the pairs of integers in the range that would sum to this number would, when multiplied, result in a product which has more than one potential pair of factors in the given range. That is there must be at least two pairs of integers that sum to the sum and all of them must produce a product that is among the 1087 from #8. Crunching those numbers gives me ten possibilities for the sum, 11, 17, 23, 27, 29, 35, 37, 41, 47, and 53.

I completely understand that if both the numbers are prime, the guy given the product will be able to figure out what they are pretty easily. However, if one of the pair of integers is prime and one is not the guy given the product won’t be able to determine which pair it is.

For example, if the pair were to be 7, 10 the product is 70 and the sum is 17. The guy given the product doesn’t know if the pair is 7,10 or 2,35.

The guy given the sum doesn’t know if the pair is 2,15 or 3,14 or 5, 12 or 6,11 or 7,10.

2,15 multiplies to 30 which could also result from 3,10
3,14 multiplies to 42 which could also result from 2,21
5,12 multiplies to 60 which could also result from 2,30
6,11 multiplies to 66 which could also result from 2,33
7,10 multiplies to 70 which could also result from 2,35

If the pair were to be 5,6 the product is 30 and the sum is 11. The guy given the product doesn’t know if it’s 2,15 or 5,6.
The guy given the sum doesn’t know if the pair is 2,9 or 3, 8 or 4,7 or 5,6

2,9 multiplies to 18 which could also result from 3,6
3,8 multiplies to 24 which could also result from 2,12
4,7 multiples to 28 which could also result from 2,14
5,6 multiplies to 30 which could also result from 3,10

In both of these situations the man who knows the sum knows that the man who knows the product can’t pin down the pair because every possible combination of integers multiplies to a product that could also be the result of another pair of integers within the given range.

Now if you eliminate 2 from the range of integers I can see where it would work (though I haven’t crunched the numbers) but anytime the pair of integers is an even number and an odd number the man who knows the product won’t know if the pair is that pair or half the even number and twice the odd one.

[Gebre]

I don't think (4,13) is a unique solution, as I believe (4,19) also works.

For larger values of m + n, the fact that Y can then determine the product comes into play. For example, when X can determine that m + n = 27, Y would not be able to know if (m,n) was (2,25) or (4,23).

[NiceCatch]

K is the set of all numbers that are not the sum of two prime numbers. k is any number in this set.

I'll try to answer your argument:

~~~
The guy given the sum doesn’t know if the pair is 2,15 or 3,14 or 5, 12 or 6,11 or 7,10.

2,15 multiplies to 30 which could also result from 3,10
*** It can't be 2,15 because 30 could also result from 5,6, which adds up to 11, another k number. The product (30) CANNOT potentially be the product of two sets of numbers that add up to two k numbers. If it were, P couldn't EXACTLY figure out m and n, just from knowing they were both not prime.
3,14 multiplies to 42 which could also result from 2,21
*** Once again, 2+21=23 is a k number. Same reason as above.
5,12 multiplies to 60 which could also result from 2,30
*** 60 is also the product of 20 and 3. Once again, 20+3=23 is a k number. Same reason as above.
6,11 multiplies to 66 which could also result from 2,33
*** Once again, 2+33=35 is a k number. Same reason as above.
7,10 multiplies to 70 which could also result from 2,35
*** Once again, 2+35=37 is a k number. Same reason as above.

4,13 multiplies to 52, which is also the product of 2 and 26 (4,13 and 2,26 are the ONLY integer pairs in the range from 2 to 100 that multiply to 52). 2+26 DOES NOT equal a k number, so 4,13 alone from the (m+n=17) numbers works.

I think your analysis missed all possible combinations of numbers that multiply to some of the numbers listed below. Look over my explanation for the (m+n=11) numbers in a previous post... I think it was fairly clear.