wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Variation to the sum - product riddle
        
(Message started by: Altamira_64 on Jun 12^th, 2012, 4:38am)

Title: Variation to the sum - product riddle
Post by Altamira_64 on Jun 12^th, 2012, 4:38am

In our case the numbers are integers from 3 to 100.
One of the two friends (A) knows the sum and the second knows the product.
Their dialog is as follows:
A: I know u can't find the numbers. Unfortunately, neither can I.
B: But now I can!
A: So do I!

Title: Re: Variation to the sum - product riddle
Post by Grimbal on Jun 15^th, 2012, 3:59pm

Can the numbers be equal?

Title: Re: Variation to the sum - product riddle
Post by Altamira_64 on Jun 17^th, 2012, 1:53am

Yes

Title: Re: Variation to the sum - product riddle
Post by Grimbal on Jun 17^th, 2012, 3:12pm

I find 2 solutions:
[hide](5,8) and (13,16)[/hide]
But I am not 100% confident with my program.

Title: Re: Variation to the sum - product riddle
Post by 0.999... on Jun 18^th, 2012, 8:25pm

I believe (13,16) is the only solution. (Verified arduously by hand :P )

That (5,8 ) is not a solution follows from the following reasoning:
Suppose A makes the first statement seeing the sum 13. The statement is indeed correct.

If B sees 40, then clearly we get a true second statement.

I claim that if B sees 30, the second statement is still true!
30 = 5*6 = 3*10
If the pair was (5,6), then A's first statement would be false with 11 = 4+7 ruled out since 4*7 uniquely factors into integers greater than 3. Thus, B determines that (3,10) is the only possible pair.

On the third statement, therefore, A cannot determine whether it is (3,10) or (5,8 ).

Title: Re: Variation to the sum - product riddle
Post by Altamira_64 on Jun 19^th, 2012, 3:29pm

Can anyone briefly explain the reasoning??
How did you get to this result?

Title: Re: Variation to the sum - product riddle
Post by 0.999... on Jun 19^th, 2012, 9:26pm

Let S be the set of all sums we would rule out due to A's first statement.
S contains 7 and 199 because A would know their summands.
S contains all even numbers 6-200 because they can be written as a sum of two primes and so A would not be sure that B cannot know their factors.
S contains all sums p+4 where p is odd and prime, because p*4 is the only way to factor that product into integers greater than or equal to 3.

Now, for any remaining sum r:
If r = a+b = x+y where all other factorizations (a',b') of a*b and (x',y') of x*y sum to elements of S, then B's statement will be true, but A cannot deduce the pair, falsifying A's second statement.

What we have left are the sums such that there is exactly one pair (a,b) with all other factorizations of a*b summing to elements of S.

For instance,
13 = 3+10 = 5+8;
30 = 3*10 = 6*5 (= 15*2) where 6+5 = 11 = 7+4 an element of S.
40 = 5*8 = 10*4 (= 20*2) where 10+4 is even and so in S.
So 13 can be ruled out.

On the other hand,
29 = 3+26 = 4+25 = 5+24 = 6+23 = 7+22 = 8+21 = 9+20 = 10+19 = 11+18 = 12+17 = 13+16 = 14+15
78 = 3*26 = 13*6; 29 and 19 are both not in S.
100 = 4*25 = 20*5
120 = 5*24 = 3*40
138 = 6*23 = 3*46
154 = 7*22 = 11*14
168 = 8*21 = 7*24
180 = 9*20 = 45*4
190 = 10*19 = 5*38
198 = 11*18 = 9*22
204 = 12*17 = 51*4
(*)208 = 13*16 = even*even
210 = 14*15 = 7*30

Title: Re: Variation to the sum - product riddle
Post by Altamira_64 on Jun 20^th, 2012, 2:42am

Great, many thanks to all of you!

Title: Re: Variation to the sum - product riddle
Post by Grimbal on Jun 20^th, 2012, 2:03pm

on 06/18/12 at 20:25:18, 0.999... wrote:

I believe (13,16) is the only solution. (Verified arduously by hand :P )

Yo are correct, indeed. And my program was wrong.
I corrected the program and made it run a 100 times as a punishment. :P

Title: Re: Variation to the sum - product riddle
Post by 0.999... on Jun 22^nd, 2012, 9:08am

on 06/20/12 at 14:03:16, Grimbal wrote:

Yo are correct, indeed. And my program was wrong.
I corrected the program and made it run a 100 times as a punishment. :P

Oh no, you must write that program in 100 different (programming) languages. ;)

Title: Re: Variation to the sum - product riddle
Post by Altamira_64 on Jun 24^th, 2012, 12:39pm

on 06/19/12 at 21:26:41, 0.999... wrote:

78 = 3*26 = 13*6; 29 and 19 are both not in S.

What do you mean by this? 29 is the sum of the two numbers 13 + 16; how can they not be in S?

Title: Re: Variation to the sum - product riddle
Post by Altamira_64 on Jun 25^th, 2012, 4:24am

Sorry, my mistake, I just realized that S contains the ones we rule out, not the ones we keep!