wu :: forums - Print Page


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

        riddles >> medium >> Sum and Sum of Squares
        
(Message started by: ThudanBlunder on Jun 19^th, 2008, 5:56pm)

Title: Sum and Sum of Squares
Post by ThudanBlunder on Jun 19^th, 2008, 5:56pm

Z joins two others, A and B. Z whispers to A the sum of two natural numbers and to B the sum of the squares of the same two natural numbers. Each knows the nature but not the detail of the information being conveyed. The following conversation takes place:

B: I do not know the numbers.

A: I do not know the numbers.

B: I do not know the numbers.

A: I do not know the numbers.

B: I do not know the numbers.

A: I do not know the numbers.

B: I know the numbers.

What are the two natural numbers?

Title: Re: Sum and Sum of Squares
Post by Barukh on Jun 20^th, 2008, 11:42am

Not sure, but maybe [hide]1, 18[/hide]?

:-/ :-/

Title: Re: Sum and Sum of Squares
Post by ThudanBlunder on Jun 20^th, 2008, 12:28pm

on 06/20/08 at 11:42:55, Barukh wrote:

Not sure, but maybe [hide]1, 18[/hide]?

:-/ :-/

Thud: I do not know the numbers.

But [hide]8 and 9 are given as the answer[/hide].

Title: Re: Sum and Sum of Squares
Post by Sir Col on Jun 20^th, 2008, 4:13pm

I don't see how this can be resolved. Working with the proposed answers...

Initially A has lots of possible pairs that could add to 17. However, B would know that 145 (sum of squares) must come from 1,12 or 8,9 with sums 13 and 17 respectively.

When B says he don't know, A realises that the sum of squares is not unique so he knows that his sum, 17, comes from 8,9; 4,13; or 3,14, with square sums of 145, 185, and 205 respectively.

When B hears that A doesn't know he is hardly surprised because he knew that 13 had three non-unique square sums as did 17, so he is none the wiser and admits it.

When A hears that B still doesn't know he is hardly surprised either because whichever square sum he's looking at 145, 185, or 205, he can deduce nothing further.

It seems that they are both in a stalemate situation.

Title: Re: Sum and Sum of Squares
Post by tohuvabohu on Jun 21^st, 2008, 6:33am

I wrote a quick computer program to check out all the sums and sums of squares up to 200.
On B's first round he could have answered if the sum of the squares was any of 8821 different numbers. (but many of the higher ones may not actually be unique if I had checked higher)
RUling out those, A could have answered if the sum was 9, 15, 16, 20, (and 8 higher numbers that may not be unique)
Ruling those out B could have answered if the sum of the squares was 65, 125, 130, 250
Ruling those out A could have answered if the sum was 11, 14 (and maybe 330)
RUling those out B could have answered if the sum of the squares was 85, 170
Ruling those out A could have answered if the sum was 13
RUling that out B could only answer if the sum of the squares was 145.
No further answers are possible.

Title: Re: Sum and Sum of Squares
Post by ThudanBlunder on Jun 21^st, 2008, 10:00am

Filling out the numbers of your working so far, Sir Col:

1)
B: I do not know the numbers.
B would know that 145 (sum of squares) must come from (1,12) or (8,9) with sums 13 and 17, respectively.

2)
A: I do not know the numbers.
When B says he doesn't know, A realises that the sum of squares is not unique so he knows that his sum, 17, comes from (8,9) or (4,13) or (3,14), with square sums of 145, 185, and 205 respectively.
145 = 8² + 9² = 1² + 12²
185 = 4² + 13² = 8² + 11²
205 = 3² + 14² = 6² + 13²

3)
B: I do not know the numbers.
But B knows A's sum is 13 or 17 - (1,12) or (8,9)
13 can come from (6,7) or (2,11) or (1,12) with square sums of 85, 125, and 145, respectively.
85 = 6² + 7² = 2² + 9²
125 = 2² + 11² = 5² + 10²
145 = 1² + 12² = 8² + 9²
B also knows that A knows which set the sum of squares is in, {145,185,205} or {85,125,145}. But B does not know which.

I think it might have something to do with the fact that in the first set 8 + 11 = 6 + 13 = 19
But trying to work out who knew what, when they knew it, not to mention who knew they knew, does my head in, haha.

Title: Re: Sum and Sum of Squares
Post by tohuvabohu on Jun 21^st, 2008, 12:11pm

Taking your step three, If A's sum was 13, he would have been able to answer on his third turn. Why?
1,12=13=6,7 or 2,11
but
6,7=85=9,2=11=4,7=65=1,8 = 9 is unique
or
2,11=125=5,10=15 is unique

So A would have known 9 on his first turn
B would have known 65 on his second
A would have known 11 on his second
B would have known 85 on his third
or
A would have known 15 on his first
B would have known 125 on his second
By his third turn A would know either one

Title: Re: Sum and Sum of Squares
Post by wonderful on Jun 21^st, 2008, 6:56pm

An interseting question is how one can come up with 8 and 9.

This reminds me of a smilar puzzle with the sum and the product (instead of sum squares) of tow natural numbers. By a sequence of reasoning, one can find out which are the two numbers.

How about here?

Have A Great Day!

Title: Re: Sum and Sum of Squares
Post by Barukh on Jun 28^th, 2008, 9:42am

Tohuvabohu, I can't understand your logic.

Could you please elaborate?

Title: Re: Sum and Sum of Squares
Post by tohuvabohu on Jun 28^th, 2008, 12:35pm

My forward or backward logic?
Forward, I wrote a program that looked at all a and b from 1 to 200, summing the squares, and then eliminating all combinations of a and b that gave a unique total, as that would have allowed B to know the answer on his first turn.
On A’s first turn, he would have known the answer if his sum was 9, 15, 16, or 20, because with 9, for example, all a,b were eliminated except 1,8. (2,7 gave a squared sum of 53, which B would have known on round one; likewise 3,6 and 4,5).
Eliminating these 4 combinations resulted in 4 more combinations being unique for B’s second turn... And so on.
Notice that on A’s third turn, he could have answered if the sum was thirteen. Eliminating that combo is what allowed B to answer 8,9 with a square sum of 145 on his fourth turn.

On my backward logic, I just figured out the eliminations that led to 13 dropping out on A’s third turn. It goes like this
If A’s sum was thirteen, then a,b would either be 1,12 or 6,7, or 2,11 as TandB figured in his step 3. The other combinations would all have resulted in first round solutions.
If it was 6,7, with a squared sum of 85, then the only other pair that square sums to 85 is 9,2.
9,2 sums to 11 which has only one other non-unique pair; that is 4,7.
4,7 square sums to 65, which can only be alternatively formed from 1,8.
1,8 sums to 9. All of 9's other combos are unique, as I pointed out above.
That’s what I short-handed to “6,7=85=9,2=11=4,7=65=1,8 = 9 is unique.”
85 can be square summed only by 6,7 or 9,2.
11 can only be summed (with a pair that do not create a unique square sum) by 9,2 or 4,7.
65 can be square summed only by 4,7 or 1,8.

If the numbers were 2,7, or 3,6, or 4,5 B would have answered round one.
If the numbers were 1,8, then A would have answered on his first turn, since 2,7, and 3,6, and 4,5 would have been already answered.

If the squared sum had been 65, then B could have answered on his second turn since A did not say 1,8, and the only other pair that makes 65 is 4,7.
If the sum had been 11, then, because B did not answer on round one, A’s only remaining suspects were 4,7 or 9,2. And since B did not say 4,7 on his second turn, it must be 9,2.

Since A did not answer 9,2 on his second turn, B knows the sum is not 11 (all other sums to 11 would have been answered previously). So if the squared sum was 85, he would have ruled out 9,2 and been left with only 6,7 possible. And that would have been his answer. He did not say 6,7.

The same process was used to determine that the combo of 2,11 would have been answered even more quickly than 6,7. Namely, 2,11=125 as a squared sum whose only other solution is 5,10. But 5,10 sums to 15, all of whose other pairs would have given unique squared sums to be answered by B in the first round.

“A would have known 15 on his first” must be 5,10 since B did not answer first.
“B would have known 125 on his second” that it must be 2,11 since it wasn’t 5,10.
“By his third turn A would know either one” - If he was looking at 13, either 2,11 or 6,7 would have already been answered so he would have known it was 1,12.
No answer of 1,12 proceeding from A’s lips on round 3 tells B the sum is not 13.

Title: Re: Sum and Sum of Squares
Post by Eigenray on Jun 28^th, 2008, 10:28pm

B: I do not know the numbers.
A: I do not know the numbers.
B: I do not know the numbers.
A: I do not know the numbers.
B: I do not know the numbers.
A: I do not know the numbers.
B: I know the numbers.
50: 8, 10
~~65: 9, 11~~
~~85: 11, 13~~
~~125: 13, 15~~
130: 14, 16
145: 13, 17
170: 14, 18
185: 17, 19
200: 16, 20
205: 17, 19
221: 19, 21
250: 20, 22
260: 18, 22
...

It suffices to show therefore that any sum > 15 appears in at least two places.

If n = |a+bi|² = a²+b², then
5n = |(2+i)(a+bi)|² = (2a-b)² + (a+2b)²
= |(1+2i)(a+bi)|² = (a-2b)² + (2a+b)².

So the sums 3a+b and 3a-b both appear in row 5n. But then 3(a-1)+(b+3) and 3(a-1)-(b+3) both appear in row 5((a-1)²+(b+3)²). So 3a+b=3(a-1)+(b+3) appears in both rows.

But a,b were arbitrary, as long as:
2a-b, a+2b, a-2b, 2a+b are positive integers,
2(a-1)-(b+3), (a-1)+2(b+3), (a-1)-2(b+3), 2(a-1)+(b+3) are positive integers,
b http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0; b+3 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0.
(a-1)²+(b+3)² http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif a²+b², i.e., a-3b http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 5.

If S > 15, we can write S = 3a+b with a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 5 and 1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif b http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 3. Then:
2a-b, a+2b, 2a+b > 0
a-2b > 0 unless (a,b) = (5,3), (6,3).
2a-b-5, a+2b+5, 2a+b+1 > 0
a-2b-7 > 0 unless: b=1, a<10; b=2, a<12; b=3, a<14.
a - 3b http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 5 unless (a,b) = (8,1), (11,2), (14,3).

So we have finitely many cases to check.

Title: Re: Sum and Sum of Squares
Post by Barukh on Jun 30^th, 2008, 10:41pm

tohuvabohu, thanks for the explanations.

It makes a perfect sense now. And, as you mentioned earlier, the conversation given in the problem statement, is the longest possible?