Factoring For Non-RSA-Gurus

[koal]

Hi there! Here is one of my favorite puzzles

Mrs. NUMBER had the following idea: she thought of two positive integers, let’s say A and B (with A <> B and both between 2 and 30). Mr. SUM is told A+B, Mr. PROD gets the result of A*B.

‘Now, who of you can tell me the Numbers A and B?’, she asked. Both Mr. SUM and Mr. PROD tried to find the numbers, but both failed.

After a few Minutes (both guys are very quick with numbers) Mr. SUM said: ‘I immediately knew, that you won’t find them!’. :idea: ‘Hmmm -’, Mr. PROD said, ‘if you can claim that, I know the numbers!’. ;) ‘Then so do I, if you know them’, Mr. SUM said.

Now what are the only numbers, for which this conversation is conclusive?

8) Koal

BTW: there is no upper limit! "30" is just a number to prevent you from writing a program. All you need is a pencil, a sheet of paper and an idea!

[hyh1048576]

The answer is 4 and 13
Sum is 17 and Product is 52 :D

[koal]

Correct! And very fast! Would you like to tell us the way you solved it? (with a few hours delay for other's around the globe)

[hyh1048576]

The way I solved it???It's also messy :) I just have seen it before :?

[flava]

The problem goes like tis:
PROD: I don't know
SUM : I knew you don't know. I don't know either
PROD: Then I know
SUM : Me too

The only answer for 2 to N, where N<219 is the pair 3,14. For bigger N there are multiple solutions. I wrote a program that solves it. For 2-30 it can be done by hand It goes like this:

M.PROD does not know the numbers by seing the product =>

1. A and B are not both primes
2. A and B are not of the form "A is prime and the B = A^2" or "B is prime and the A = B^2"
(because any of the cases above would lead to a direct solution found by M.PROD)

M.SUM knew for sure by looking at the sum S that the two number agree with 1. and 2. so :
3. you make the list of sums S that can no be written as the sum of two primes or the sum of a prime and it's square.
4. For each sum in this list, you make the list of the possible A and B so A+B =S

M. PROD says that he knows. It means that for his product there is a unique factorisation into two numbers A and B (not necesarily prime) so A*B=P and A+B in the list above.

5. For each A and B from above you calculate the product P' = A*B
6. For each P' you try all the possible factorisations af two numbers (not necesarily primes) and verify that only one of them gives S' =A+B in the list. You note for each sum in your famous list how many products P' give a solution for that sum, let's call that O(S').

M.SUM says he knows too, so the sum he knows is a solution for only one product. So:
7.You look at O(S) for each S in your list, the solutions have O(S)=1.

Q.E.D.

I know I can't explain good, but I hope you got the ideea.

[koal]

Thanks for that explanation. It’s correct and I didn’t know about other solutions. So let’s ask for the smallest.

(0) PROD: I don't know
(1) SUM : I knew you don't know. I don't know either
(2) PROD: Then I know
(3) SUM : Me too

Sentence (0) is a redundancy, because PROD is quiet!

Due to Goldbach’s conjecture (“EVERY EVEN INTEGER n > 2 IS THE SUM OF 2 PRIMES”), which is proven for our purposes (I think up to 10^14), Mr. SUM has got an odd number, because otherwise he could not say sentence (1). In other words: if the sum WERE even, the product MIGHT be definitely factorable into two primes, and therefor Mr. SUM couldn’t claim sentence (1).

The only numbers with an upper limit of 30 (or an upper limit for the sum of 59), which lead to indefinite products are 11 and 17!

Sum = 11:
----------------
2+9 (Prod 18)
3+8 (Prod 24)
4+7 (Prod 28)
5+6 (Prod 30)

Sum = 17:
------------------
2+15 (Prod 30)
3+14 (Prod 42)
4+13 (Prod 52)
5+12 (Prod 60)
6+11 (Prod 66)
7+10 (Prod 70)
8+9 (Prod 72)

Let’s test some others. As we can omit all even numbers, let’s look at 23. One might believe, that 23 is another number that would lead to indefinite products. Yes – that’s true, if the upper limit would be higher. Explanation: the sum 4+19=23 leads to the product 4*19=76. Now 76 is definitely factorable within our ranges: 76 = 4*19 or 2*38, but 38 is outside our range (2-30). And therefore sentence (1) would be incorrect for a sum of 23. Even sentence (0) would be false, because if Mr. PROD is told “76”, he knows definitely that 76 = 4*19 within a range between 2 and 30 for both factors.

A last check with – let’s say 51 (every odd number between 5 and 59 passes that check - except 11 and 17)

21+30, prod=630
22+29, prod=638
23+28, prod=644
24+27, prod=648
25+26, prod=650

take any product and check it’s factorizations, eg. 648:

648 = 2*324 or 3*216 or 4*162 or 6*108 or 8*81 or 9*72 or 12*54 or 18*36 or 24*27

as you see, only one of them is within our range (2-30), and further checks show, that a sum of 51 leads to definitely factorable products within our range.

These facts both Mr. SUM and Mr. PROD are aware. Now, why can Mr. PROD say sentence (2)? Because he must have a number which is now is defintely factorable. But only since sentence (1) was said by Mr. SUM!

Let’s watch out for the only possible product:

Sum = 11:
----------------
2+9 (Prod 18 = 2*9, 3*6)
3+8 (Prod 24 = 2*12, 3*8, 4*6)
4+7 (Prod 28 = 2*14, 4*7)
5+6 (Prod 30 = 2*15, 3*10, 5*6)

Mr. PROD might have got 24 or 28, and because of sentence (1) he would definitely know the factors, because sentence (1) says (via Goldbach’s Conjecture) he can omit all numbers, which add to an even sum. So he COULD say sentence (2) for BOTH 24 (3*8) and 28 (4*7). But that’s exactly why Mr. SUM can’t claim sentence (3), because there are two possibilities to form “11” (3+8 and 4+7). Thus “11” can’t be the sum. It MUST be 17. Let’s see why:

Sum = 17:
------------------
2+15 (Prod 30 = 2*15, 3*10, 5*6) 3x odd
3+14 (Prod 42 = 2*21, 3*14, 6*7) 3x odd
4+13 (Prod 52 = 2*26, 4*13) 1x even, 1x odd
5+12 (Prod 60 = 2*30, 3*20, 4*15, 5*12, 6*10) 2x even, 3x odd
6+11 (Prod 66 = 2*33, 3*22, 6*11) 1x out of range, 2x odd
7+10 (Prod 70 = 2*35, 5*14, 7*10) 1x out of range, 2x odd
8+9 (Prod 72 = 2*36, 3*24, 4*18, 6*12, 8*9) 3x even, 2x odd

Imagine, Mr. PROD has been told “72” to be the product of A and B. Then he can’t know the factors, even after discarding those which form an even sum, i.e. the pairs [2,36] , [4,18] and [6,12] , because two pairs forming an odd sum still remain [3,24] and [8,9] and the values of A and B are unpredictable.

And here’s the error!!!

3 and 24 lead to a sum of 27. And 27 is NOT in our list of possible sums (11 and 17). Thus Mr. PROD would definitely know the factors 8 and 9. With an upper bound of 30 this puzzle does NOT work! It works with a range of 2-100. Then the list of possible sums grows to 11 17 23 27 29 35 37 41 47 53 and all the products above (for sum=17) are indefinite – except one: 52 ! Because 2*26 can be discarded, Mr. PROD knows the factors 4 and 13 and claims it. As Mr. SUM has the same list in his brain, he now knows the numbers => sentence (3).

Sorry for the limit of 30! )

Koal