Party Guests and Perfect Squares

Date: 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/