The Kissing Problem

A while back my family spent some time in Aix-en-Provence, and my daughter went to a french high school, the Lycee Georges Duby. She learned that school is a little different in France. For one thing, every day before every class, everyone had to kiss each other on each cheek.

We are not concerned with why they do this, it is is just the way it is in France. But we would like to know how many kisses it takes to finish the job.  For simplicity, we will ignore the fact that people can kiss each other from 2 times (normal, for Provence) up to as many as 4 or even 5 times (really, really good friends in Provence, but nothing special in Paris) and just define one kiss as occuring when 2 people kiss each other, any number of times.

One way to think about this problem is to imagine that everyone is arranged in a circle. Put a dot on the circle for each person. Draw a line from each person on the circle to every other person on the circle. Each line represents a kiss. Because of the way we define a kiss, there is only one line between any 2 people, not one line going each way.
    
We can display groups of people and kisses this way using a program called Mathematica, as shown below for groups of people from size 2 to 5.

Now, we would like to know how many kisses it takes until everyone in the class has kissed everyone else. Instead of drawing the picture and counting the lines, we will think about the problem and find a general solution, that is a solution that works for any number of people. First, we'll look at the figure for 5 people, as an example.

Pick one of the dots. Notice that this person must kiss 4 other people - one less than the total number of people, 5. And every other of these 5 must also kiss 4 others.  So, is the total number of kisses 5x4=20? No, because once one person has kissed a person, that person doesn't need to kiss them back, at least according to the way we've defined a kiss.  So, one kiss counts for two people, or one line between two dots represents one kiss between two people, and the total number of kisses needed for five people is (5x4)/2=10.

Suppose there are some other number of people, say n people? Following the logic from above, the rule is just (n(n-1))/2 kisses. We can show this in a list, like this, where the left hand column shows the number of people, and the right hand shows the number of kisses. We go up to 35 people because the law in France is that there can't be more than 35 kids in a class. In practice, this means there are exactly 35 kids. Unless there is a bus strike that day, but that is another complication of french life that we will also ignore here.

Or we can plot it, like this.

So, the number of kisses increases at an increasing rate. With 35 people, Anna's class must engage in a total of 595 kisses. This is a lot of kissing. Maybe that's why they don't want more than 35 kids in a class?

The figure below shows the kissing for just 25 people.

One thing we haven't dealt with is how to accomplish this kissing in the most efficient manner. Since schools in France only have 10 minutes between classes, efficiency in kissing is of the utmost importance to an orderly educational process. Suppose that it takes 5 seconds for a kiss. How quickly can a class of 35 people kiss each other? How should the kissing be organized?

Created by Mathematica  (December 15, 2003)