The Art and Craft of Problem Solving

30 CHAPTER^2 STRATEGIES FOR INVESTIGATING PROBLEMS

Hence we have restated our conjecture into an unrecognizably different, yet equivalent,

form:

Prove that an integer has an odd number of di visors if and only if it is

a perfect square.

There are many ways to think about this particular problem. See the discussion on

p. 68 and Problem 6.1. 21 for two completely different approaches.

Example 2.2.4 (LMO 19 88) There are 25 people sitting around a table, and each

person has two cards. One of the numbers 1 ,2,3, ... ,2 5 is written on each card, and

each number occurs on exactly two cards. At a signal, each person passes one of

her cards-the one with the smaller number-to her right-hand neighbor. Prove that,

sooner or later, one of the players will have two cards with the same numbers.

Partial Solution: At first, this problem seems impenetrable. How can you prove

something like this? Small doses of getting our hands dirty and making it easier go

a long way. Let's help our understanding by making the problem easier. There is

probably nothing special about the number 25 , although we are immediately alerted to

both squares and odd numbers. Let's try an example with two people. If each person

has the cards numbered 1 and 2, we see that the pattern is periodic: each person just

passes the number 1 to her neighbor, and each person always holds numbers 1 and 2.

So the conclusion is not true for two people. Does parity (evenness or oddness) matter,

then? Perhaps! Use the notation -+-to indicate a person holding cards numbered a

and b. Consider four people, initially holding

We see that at each turn, everyone will hold a 1 or 2 paired with a 3 or 4. So again,

the conclusion is not true, and for any even number of people, we can make sure that

it never is true. For example, if there are^10 = (^2) · 5 people, just start by giving each

person one card chosen from {I, 2, ... ,5} and one card chosen from {6, 7, ... , 10}.

Then, at every turn, each person holds a card numbered in the range 1- 5 paired with

one in the range 6- 10 , so no one ever holds two cards with the same numbers.

Now we turn our attention to the case where there is an odd number of people.

Here is an example involving 5 people.

I! I i I ; I � I � I

We arranged the table so that the top row cards are smaller than the bottom row,

so we know that these are the cards to be passed on the next turn. After that, we sort

them again so that the top level contains the smaller numbers: