Party Guests and Perfect SquaresDate: 07/02/2001 at 21:11:44 From: kristy evans Subject: Problem of the week The problem states that a guest invites 17 people to her house, and gives each a number between 2 and 18. The host has number 1 for herself. While dancing, Sally notices that all of the couples' sums add up to perfect squares. The question asks me to find who is dancing with whom, and to state my reasoning. I have tried making an organized list, and a guess-check table, but neither has worked well. Can you please help me figure out how to do this problem? Thanks! Date: 07/03/2001 at 13:32:00 From: Doctor Ian Subject: Re: Problem of the week Hi Kristy, If I understand the problem correctly, you want to pair the numbers 1-18 up so that each pair adds up to a perfect square. The smallest possible sum would be 1 + 2 = 3, and the largest possible sum would be 17 + 18 = 35. What perfect squares are between 3 and 35? There aren't many: 4, 9, 16, and 25 are the only ones. We can make a table with the squares, and the possible couples that might add up to them: 4 -> (1,3) 9 -> (1,8), (2,7), (3,6), (4,5) 16 -> (1,15), ..., (7,9) 25 -> (7,18), ..., (12,13) Now, one thing to notice is that 3 can't be dancing with 1 and with 6 at the same time. And there is only one possible couple that can add up to 4, so we can ignore the possibility that 3 and 6 are a couple. For similar reasons, we can ignore the possibility that 1 and 8 are a couple: 4 -> (1,3) 9 -> (1,8), (2,7), (3,6), (4,5) xxxxx xxxxx 16 -> (1,15), ..., (7,9) 25 -> (7,18), ..., (12,13) Now, if you fill in the rest of the pairs, you can see that 18 has only one possible partner: 7. This tells us that 7 can't be dancing with 2: 4 -> (1,3) 9 -> (1,8), (2,7), (3,6), (4,5) xxxxx xxxxx xxxxx 16 -> (1,15), ..., (7,9) 25 -> (7,18), ..., (12,13) Also, 17 has only one possible partner: 8. Which means that 8 can't be dancing with anyone else. If you keep going like this, identifying pairs that _must_ be together, and then eliminating all the other pairs that become impossible as a result, you should end up with each number appearing in exactly one pair. Does this help? - Doctor Ian, The Math Forum http://mathforum.org/dr.math/ Date: 07/04/2001 at 04:16:29 From: kristy evans Subject: Problem of the week I did come up with a table; however, I have the number 10 twice, and I am missing 11. I cannot figure the answer out to this problem. Please help me! The following is what my table looks like: #1 #2 sum 1 3 4 2 14 16 16 9 25 10 15 25 12 13 25 7 18 25 8 17 25 4 5 9 6 10 16 Date: 07/05/2001 at 16:02:27 From: Doctor Ian Subject: Re: Problem of the week Hi Kristy, Sometimes the right representation makes all the difference. (If you don't believe that, try doing long division using Roman numerals.) Here are all the ways to add the numbers up to get the perfect squares 4, 9, 16, and 25, assuming that we always put the smaller member of the pair first: + 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 - 4 9 16 2 - 9 16 3 - 9 16 4 - 9 16 5 - 16 6 - 16 7 - 16 25 8 - 25 9 - 25 10 - 25 11 - 25 12 - 25 13 - 14 - 15 - 16 - 17 - 18 - So, what does this table tell us? Well, suppose we want to know all the ways that number 3 might pair up. We look across row number 3, to find 3 + 6 = 9 3 + 13 = 16 Then we look down column number 3 to find 1 + 3 = 4 So 3 _might_ be paired with 6, 13, or 1. Now, if you look at this table for a while, you might notice that when you do this for _some_ numbers, you find that there is only one possible way them up. For example, in row 18, we find nothing; and in column 18 we find only 7 + 18 = 25 So we know that 7 and 18 have to be one pair. This means that we can mark that pair (I'll use [] for that), and remove all the other entries for either 7 or 18. + 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 - 4 9 16 2 - 16 3 - 9 16 4 - 9 16 5 - 16 6 - 16 7 - [] 8 - 25 9 - 25 10 - 25 11 - 25 12 - 25 13 - 14 - 15 - 16 - 17 - 18 - Do you see how I changed the table? I put [] at the intersection of row 7 and column 18, to indicate that 7 + 18 = 25 is one of our pairs; then I deleted any other possibilities in row 7, column 7, row 18, and column 18, to indicate that those numbers can't be used again. By the same reasoning, we can see that 8 and 17 have to be one pair, and we can remove other entries for them: + 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 - 4 16 2 - 16 3 - 9 16 4 - 9 16 5 - 16 6 - 16 7 - [] 8 - [] 9 - 25 10 - 25 11 - 25 12 - 25 13 - 14 - 15 - 16 - 17 - 18 - Similarly for 9 and 16: + 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 - 4 16 2 - 16 3 - 9 16 4 - 9 16 5 - 16 6 - 16 7 - [] 8 - [] 9 - [] 10 - 25 11 - 25 12 - 25 13 - 14 - 15 - 16 - 17 - 18 - Do you see what I'm doing? At each step, I try to find a number N such that there is at most one possible match in row N and column N. Can you see that the next one like that will be 2? Row 2 contains only 2 + 14 = 16, and column 2 contains nothing. So I know that 2 + 14 has to be one of the pairs... and I remove everything else from row 2, column 2, row 14, and column 14: + 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 - 4 16 2 - [] 3 - 9 16 4 - 9 16 5 - 16 6 - 16 7 - [] 8 - [] 9 - [] 10 - 25 11 - 12 - 25 13 - 14 - 15 - 16 - 17 - 18 - My next lucky winner will be 11. Since 11 + 5 = 16 is the only possible pairing for 11, + 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 - 4 16 2 - [] 3 - 9 16 4 - 16 5 - [] 6 - 16 7 - [] 8 - [] 9 - [] 10 - 25 11 - 12 - 25 13 - 14 - 15 - 16 - 17 - 18 - The next winner will be 4: + 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 - 4 16 2 - [] 3 - 9 16 4 - [] 5 - [] 6 - 16 7 - [] 8 - [] 9 - [] 10 - 25 11 - 12 - 13 - 14 - 15 - 16 - 17 - 18 - At this point, we have the following pairs: (2,14) (4,12) (5,11) (7,18) (8,17) (9,16) So the numbers we haven't paired up yet are: 1, 3, 6, 10, 13, 15 Note that now you have the same kind of problem, only much smaller. That is, can you pair _these_ numbers so that all the pairs add up to perfect squares? Problems like this are tough! So don't feel bad about feeling lost. The important thing is to have some kind of systematic way to (1) keep track of what you've already tried, and (2) help you decide what to try next. I hope this helps. - Doctor Ian, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/