Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Logic

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search