|
Here is a cool puzzle for you to work on. The Problem Arrange the integers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, and 16 in order so that, when you go through the list, the sum of any two sitting next to each other is a square number. So, for example, 7 and 2 might be side-by-side since 7 + 2 = 9 = 32; and 5 might go next to 4, since 5 + 4 = 9 = 32, or it might go next to 11, since 5 + 11 = 16 = 42. A. How I worked on the problem. I call it Method A. 1. We know the biggest sum possible for two different positive integers between one and sixteen is 15 + 16 = 31. And what we want are integers between one and 31 that are squares. So we list them. 1 = 12, but it is excluded because it is not the sum of two positive integers. We have 4, 9, 16, and 25 as square numbers. So now we want to list pairs of numbers between 1 and 16 that add to one of the squares. 2. Let’s write each of the squares in as many ways as we can as the sum of two numbers between 1 and 16. 4 = 1 + 3 1 way 9 = 8 + 1 = 7 + 2 = 6 + 3 = 5 + 4 4 ways 16 = 15 + 1 = 14 + 2 = 13 + 3 = 12 + 4 = 11 + 5 = 10 + 6 = 9 + 7 7 ways 25 = 16 + 9 = 15 + 10 = 14 +11 = 13 +12 4 ways 16 ways 3. The list of 16 numbers we are trying to form will have 15 pairs. We see that each pair above (except for one of them!) must appear in our list. And from that list, we see that 8 is in only one pair, namely, 8 + 1. So the list either begins with 8 1, or ends with 1 8. We also see that 16 appears in only one pair, 16 + 9. So the list either begins with 16 9 or ends with 9 16. (We have underlined these two pairs in (2) above.) So far we have 8 1 9 16 Next, looking at the remaining possibilities, we see that 1 pairs only with 15 or 3. Let’s try 15. 8 1 15 9 16 ***** (at * below we try 8 1 3……9 16) What can 15 pair with, other than 1, which is already paired? From the list above we see that it is 10. 8 1 15 10 9 16 10 can pair only with 6. 8 1 15 10 6 And 6 pairs only with 3. 8 1 15 10 6 3 Next, 3 pairs with 13, and on the other end, 9 pairs with 7: 8 1 15 10 6 3 13 7 9 16 Next, 13 goes with 12, and 7 goes with 2: 8 1 15 10 6 3 13 12 2 7 9 16 Next, 12 goes with 4, and 2 goes with 14 8 1 15 10 6 3 13 12 4 14 2 7 9 16 And finally, 4 goes with 5 and 14 goes with 11 (and 5 and 11 go together!) 8 1 15 10 6 3 13 12 4 5 11 14 2 7 9 16 ← list of numbers 1-16 we want! 9 16 25 16 9 16 25 16 9 16 25 6 9 16 25 ← row of squares And we observe, 9 occurs 4 times; 16 occurs 7 times; 25 occurs 4 times, as in our chart above. *Trying some numbers that won’t work: Above we found that 8 1 15 works, and that 8 1 3 might be possible. Now let’s try 8 1 3: 8 1 3 9 16 Looking at our list above, 3 can pair with 6 or 13. Let’s try 6 first: 8 1 3 6 Six can pair with 10, 10 with 15, and 15 with 1. So we have 8 1 3 6 10 15 1 oops—we already used 1! So this doesn’t work. So let’s try 13: 8 1 3 13 Thirteen can pair with 3 (nope; it is already used!) or 12. So let’s try 12. 8 1 3 13 12 now we have only one choice for each position: 8 1 3 13 12 4 5 11 14 2 7 9 16 But this ordering only uses 13 of the 16 numbers. Where are 6, 10, and 15? No good! So we have to continue at ***** above in order to get a correct solution. B. Another way to solve the problem (Method B). What single numbers from 1 through 16 can be added to each of the numbers one through sixteen to make a square? Here is the table. In the first row are the numbers one through sixteen, and in each column are the numbers that can be added to the top number to make a square.
(so, for example, 1 + 15 = 16 = 42; 1 + 8 = 9 = 32; 1 + 3 = 4 = 22.) As before, we see that 8 pairs only with 1, and 16 pairs only with 9. So we are at the same starting place as we were in Method A. 8 1 9 16 One pairs only with 15 or 3, so we are exactly where we were in Method A. Following it through, we have the same solution: 8 1 15 10 6 3 13 12 4 5 11 14 2 7 9 16 |