-<TITLE>Math-Ventures: A Solidarian Disco Circle</TITLE>

-<BODY BGCOLOR="#FFFFFF">

-<CENTER><H2>A Solidarian Disco Circle</H2></CENTER>

-Are you familiar with disco circles? I participated in quite a lot of them

-when in the parties I attended. The concept is that a group of boys and

-girls are standing in a circle with pop music playing in the background. A

-boy and girl couple is standing in the middle of the circle dancing, and

-after a while the boy walks-dances out of the center, while the girl invites

-a different boy to dance with her. After a while longer, the girl leaves,

-allowing the new boy to invite a new female partner. Again, the boy leaves,

-I eventually came to wonder about this question regarding disco circles:<P>

-<B>1.</B> When can a group of dancers form a disco circle, such that every

-girl dances with every boy once and only once?

-<B>2.</B> 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?

-The solution can be found some space below:

-<BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR>

-<BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR>

-<BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR>

-<BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR>

-The secret to solving this problem lies in representing it in a proper

-model. Let's take a piece of paper (or an empty pad in a drawing program)

-and draw one circle for every boy and one for every girl. We can mark the

-boys' circles with "B1", "B2", "B3" and so on and the girls' with "G1",

-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.<P>

-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).<P>

-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 <B>"Graph"</B>, and

-the field of mathemtics that deals with graphs is called <B>Graph

-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:<BR>

-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.<P>

-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 <B>and</B> 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).<P>

-Yet another option is the trivial case in which there is one boy and one

-girl. The reason that it is not included in the other sub-cases, is because

-that way the two nodes are all the existing nodes in the graph.<p>

-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:<P>

-1. There are 2 boys present.<BR>

-2. There are 2 girls present.<BR>

-3. There is an even number of boys and an even number of girls who wish to

-pariticipate in the circle.<BR>

-4. There is exactly one boy and exactly one girl.<br>

-<A HREF="./"><H3>Back to the Math-Ventures Web page</H3></A><P>

-<A HREF="../"><H3>Back to Shlomi Fish' Homepage</H3></A>