Math Professor Laurie Snell: Can You Explain This Problem?

RECENTLY AN ANN Landers reader asked why mathematicians worked years to solve the following puzzle:

"Ifyou are having a party and want to invite at least four people who know each other and five who don't, how many people should you invite?

"The answer," the Landers reader confided, "is 25."

We asked Laurie Snell to elucidate.

There is a major error in the statement of the problem. You want to be sure that th ere areatleast four people who know each other or (not and) five who do not.

A smaller example of this problem is a well-known puzzle problem. You are asked to show that in any group of six people there are either a group of 3 people who are totally ac- quainted with each other or a group of 3 people who are complete strangers to each other. For a group of 6 people there are 37,768 differreasons ent acquaintance patterns possible so, of course, you can just check them all until you find one which works. What makes this a nice puzzle problem is that a clever student can figure out an argument that only takes a few sentences to explain and avoids the boring enumeration process.

It turns out, however, that when dealing with larger numbers—even 4 and 5—the patterns of connection are much harder to analyze, even with assurances from the Ramsey Theorem that it can be done. It took cleverness and 11 years of computer time to come up with die solution that you must have a group of 25 to be absolutely sure you will be getting either four people with every pair aquainted with each other or 5 people who are complete strangers to each other. The significance of this problem beyond party invitations? It is easy to suggest that these results have applications to such important functions as telephone networks and to explain why there is a big dipper in the sky; but probably a more honest answer is that mathematicians love to look for patterns, and the Ramsey Theorem assures they will find them. In the last analysis, the problem provides a look at a very pretty branch of mathematics where, by chance, the results can be explained to those who are not mathematicians.

Landers

Snell