I eventually came to wonder about this question regarding disco circles:
1. When can a group of dancers form a disco circle, such that every
girl dances with every boy once and only once?
2. In case this feat cannot be achieved, what possible times can every pair dance, so that all boy-girl combinations will dance the same number of times together?
Now, let's suppose a girl invited a boy to dance with her in the middle of the disco circle. After a short while, the girl would leave and the boy would be able to invite a girl to join him in the center. If we keep tracing who is the person in the middle who can (now or in a short while) invite a member of the opposite sex to join him, we can see that we move from a boy to a girl, and then to another boy, another girl, and so on.
Imagine we put the pencil inside the circle of the kid that is in the middle , and when he is replaced by the one he invited, we move the pencil towards the circle of the new kid, thus drawing a line between the two circles. Assuming that a dancing routine in which every pair danced once can be achieved, we'll end up with a drawing in which every boy is connected to every girl (and vice-versa).
If we can traverse this drawing, so that every link is drawn once, and the pencil is not lifted off the paper, then we found a dancing order that satistfies the request. In mathematical terminology a drawing with lines and circles is commonly called a "Graph", and the field of mathemtics that deals with graphs is called Graph Theory.
A very famous theorem in Graph Theory, called Euler's Circle Law,
proves that a graph can be drawn in one draw if and only if the
following condition is fullfilled:
Every circle is connected by an even number of links or there are only two circles that are connected by an uneven number of links.
In our case, it's obvious that the number of links for every girl is equal to the number of boys and vice versa. Thus, to have an even number of links that emerge from every circle, we will need to have an even number of boys and an even number of girls. Plus, if there are two boys and an uneven number of girls, we'll still get a graph with only two circles having an uneven number of links. (and likewise for two girls and an uneven number of boys).
To sum up, a disco circled in which every pair of boy and girl dances together once can be formed on one of the following conditions:
1. There are 2 boys present.
2. There are 2 girls present.
3. There is an even number of boys and an even number who wish to pariticipate in the circle.
Back to Shlomi Fish' Homepage