Author |
Topic: Sum and Sum of Squares (Read 796 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Sum and Sum of Squares
« on: Jun 19th, 2008, 5:56pm » |
 Quote  Modify
|
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?
|
| « Last Edit: Jun 20th, 2008, 4:50pm by ThudnBlunder » |
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum and Sum of Squares
« Reply #1 on: Jun 20th, 2008, 11:42am » |
Quote Modify
|
Not sure, but maybe 1, 18?
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Sum and Sum of Squares
« Reply #2 on: Jun 20th, 2008, 12:28pm » |
Quote Modify
|
on Jun 20th, 2008, 11:42am, Barukh wrote:Not sure, but maybe 1, 18?
|
|
Thud: I do not know the numbers.
But 8 and 9 are given as the answer.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Sum and Sum of Squares
« Reply #3 on: Jun 20th, 2008, 4:13pm » |
Quote Modify
|
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.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
tohuvabohu
Junior Member
Gender:
Posts: 102
|
|
Re: Sum and Sum of Squares
« Reply #4 on: Jun 21st, 2008, 6:33am » |
Quote Modify
|
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.
|
| « Last Edit: Jun 21st, 2008, 8:24am by tohuvabohu » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Sum and Sum of Squares
« Reply #5 on: Jun 21st, 2008, 10:00am » |
Quote Modify
|
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 = 82 + 92 = 12 + 122
185 = 42 + 132 = 82 + 112
205 = 32 + 142 = 62 + 132
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 = 62 + 72 = 22 + 92
125 = 22 + 112 = 52 + 102
145 = 12 + 122 = 82 + 92
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.
|
| « Last Edit: Jun 21st, 2008, 3:01pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
tohuvabohu
Junior Member
Gender:
Posts: 102
|
|
Re: Sum and Sum of Squares
« Reply #6 on: Jun 21st, 2008, 12:11pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Sum and Sum of Squares
« Reply #7 on: Jun 21st, 2008, 6:56pm » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum and Sum of Squares
« Reply #8 on: Jun 28th, 2008, 9:42am » |
Quote Modify
|
Tohuvabohu, I can't understand your logic.
Could you please elaborate?
|
|
IP Logged |
|
|
|
tohuvabohu
Junior Member
Gender:
Posts: 102
|
|
Re: Sum and Sum of Squares
« Reply #9 on: Jun 28th, 2008, 12:35pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum and Sum of Squares
« Reply #10 on: Jun 28th, 2008, 10:28pm » |
Quote Modify
|
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|2 = a2+b2, then
5n = |(2+i)(a+bi)|2 = (2a-b)2 + (a+2b)2
= |(1+2i)(a+bi)|2 = (a-2b)2 + (2a+b)2.
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)2+(b+3)2). 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  0; b+3 0.
(a-1)2+(b+3)2 a2+b2, i.e., a-3b 5.
If S > 15, we can write S = 3a+b with a  5 and 1  b 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 5 unless (a,b) = (8,1), (11,2), (14,3).
So we have finitely many cases to check.
|
| « Last Edit: Jun 28th, 2008, 11:08pm by Eigenray » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum and Sum of Squares
« Reply #11 on: Jun 30th, 2008, 10:41pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print