Jump to content
BrainDen.com - Brain Teasers
  • 0
Sign in to follow this  
Guest

Question

Guest

I recently posted a puzzle given to me by a friend that he got from his Dad many years ago. Once a couple of solutions were found, the thought was there may be many solutions. I discussed this with my friend and he felt that the reason another solution was found was because the solver had put an upper bound ond the range of possible numbers. This had the unintended consequence of creating the extra solution. So, in order to truly "solve" the puzzle, one must find an answer and then prove that it is indeed unique. He has done this. His proof is a thing of beauty. Something I could have never come up with, but it's pretty easy to understand. I repost the puzzle below and I will put his solution and proof in the spoiler. You might want to consider revisiting the problem and thinking about a proof before looking at his.

Two positive integers are chosen. Their sum is revealed to perfect logician A. The sum of their squares is revealed to perfect logician B. This is all common knowledge. The following conversation ensues:

Logician A: I don’t know what the two numbers are.

Logician B: I don’t know what the two numbers are.

Logician A: I don’t know what the two numbers are.

Logician B: I don’t know what the two numbers are.

Logician A: I don’t know what the two numbers are.

Logician B: I don’t know what the two numbers are.

Logician A: I don’t know what the two numbers are.

Logician B: Now I know what the two numbers are!

What are the two numbers? And prove that the two numbers are a unique solution.

As a third party observer listening to the conversation, A’s first “I don’t know” rules out only (1,1) and (1,2) as possible answers. If the sum of the squares is unique, (can only be produced by two specific integers), then B will know the answer, so B’s first “I don’t know” rules out all unique sums of two squares. All non unique sums of two squares are shown in the chart below, listed in rows by the sum of the two possible integers up to a sum of 24. Note that knowing the sum and sum of the squares uniquely determines the two integers. We don’t include the integer pairs in the chart just the sum and sum of squares.

sum | possible sums of

of | squares after B’s

ints| first “I don’t know”.

1: none

2: none

3: none

4: none

5: none

6: none

7: none

8: 50*

9: 65*

10: 50*

11: 85, 65**

12: none

13: 145, 125**, 85

14: 170, 130

15: 125*

16: 200, 130

17: 205, 185, 145

18: 290, 260, 170

19: 325, 265, 221, 205, 185

20: 250, 200

21: 305, 221

22: 370, 340, 260, 250

23: 485, 377, 325, 305, 265

24: 530, 450, 290

Our proof will work as follows: We play the role of a third party observer listening to the conversation. As each logician in turn says “I don’t know the answer”, we keep track of all possible remaining integer pairs that could lead to that conversation. For any sum, if there is a unique sum of squares remaining in the integer sum’s row of our chart, then A will know the answer if he were given that sum. Thus when A says “I don’t know”, we can eliminate the entry from any row with a single remaining entry. For any sum of squares that appears only once in our chart, then B will know the answer if he were given that sum of squares. Thus when B says “I don’t know”, we can eliminate any sum of squares that appears only once in our remaining chart. Let’s continue.

If there is a single entry in a row then A will now be able to determine the two numbers. Thus A’s second “I don’t know” eliminates the numbers unique in a row, 50, 65, 50, and 125, shown with an * in the chart. This makes the remaining 65 and remaining 125 unique. Thus B will know if he were given one of those two numbers. B’s second “I don’t know” eliminates these from consideration (shown with ** in the chart). Below is a redacted chart of the remaining possible sums of squares.

sum | possible sum of

of | after B’s second

ints| “I don’t know”

11: 85*

12: none

13: 145***, 85**

14: 170, 130

15: none

16: 200, 130

17: 205, 185, 145****

18: 290, 260, 170

A’s third “I don’t know” eliminates the 85 alone in row 11, and now the remaining 85 is a unique sum of squares left in the chart and B’s third “I don’t know” eliminates it as a possibility. A’s fourth and the final “I don’t know” eliminates the 145 which is now alone in row 13. This leaves 145 in row 17 as the sole unique sum of squares remaining in the chart so when B finally says “I know what the two numbers are” the two numbers must add up to 17 and the sum of their squares must be 145. Thus the two numbers are 8 and 9.

This proof essentially assumes that no other numbers whose sum is above 15 is eliminated. To complete the proof and show that 8 and 9 is the unique answer, it is sufficient to show that for all sum’s greater than 24 (the chart shown is complete up to 24) there are at least two possible non unique sums of squares for each possible sum of integers above 24, therefore there are at least two entries on each row of our chart above 24, and thus no other eliminations of non unique sum of squares can occur.

Consider the equation:

(5x+2y)^2 + (5x+y)^2 = (7x+2y)^2 + (x+y)^2 = (50xx + 30xy + 5yy)

This equation holds for all x and y. For example if x=1, and y=1 : 7^2 +6^2 = 9^2 + 2^2 = 85. Each x and y will give us two integer pairs which have the same sum of their squares. In particular for (x=1,y>=5), (x=2,y>=1), (x=3,y>=-2)

Sum of

Pair1 pair2 squares sum1 sum2

x=1, y=5 : (15,10) (17,6) 325 25 23

y=6 : (17,11) (19,7) 410 28 26

y=7 : (19,12) (21,8) 505 31 29

y=8 : (21,13) (23,9) 610 34 32

y=9 : (23,14) (25,10) 725 37 35

y=10 : (25,15) (27,11) 850 40 38

... ... ... ... ... ...

x=2, y=1 : (12,11) (16,3) 265 23 19

y=2 : (14,12) (18,4) 340 26 22

y=3 : (16,13) (20,5) 425 29 25

y=4 : (18,14) (22,6) 520 32 28

y=5 : (20,15) (24,7) 625 35 31

y=6 : (22,16) (26,8) 740 38 34

... ... ... ... ... ...

x=3, y=-2 : (11,13) (17,1) 290 24 18

y=-1 : (13,14) (19,2) 365 27 21

y=0 : (15,15) (21,3) 450 30 24

y=1 : (17,16) (23,4) 545 33 27

y=2 : (19,17) (25,5) 650 36 30

Y=3 : (21,18) (27,6) 765 39 33

... ... ... ... ... ...

As y increases by one, the sum of each integer pair increases by 3.

Looking at the sums of the initial pairs for x=1, x=2, x=3, two are 0 mod 3, (11,13) and (17,1), two are 1 mod 3 (15,10) and (16,3) and two are 2 mod 3, (17,6) and (12,11). The largest of the initial sums is 25, and no integer pair is duplicated in the region of concern, so there are at least two non unique sums of squares for each possible sum of integers 23 and above. In particular, for x=1, y>=5 and x=2,y>=1 in our formula both covers sums of 23, 26, 29, 32, 35…, x=3, y>=-2, x=3, y>=0 both cover 24, 27, 30, 33, 36…, and x=1, y>=5, x=2, y>=3 doubly covers 25, 28, 31, 34, 37…. Thus no other eliminations can occur in the chart and 8,9 is the unique answer.

Share this post


Link to post
Share on other sites

0 answers to this question

Recommended Posts

There have been no answers to this question yet

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...