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

+#include '../template.wml'

-~~<BODY BGCOLOR="#FFFFFF"~~>

+<subject "A Solidarian Disco Circle" />

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

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>

+I eventually came to wonder about this question regarding disco circles:

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

+<li>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

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

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

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

+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 <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~~>

+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>

+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 <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>

+for two girls and an uneven number of boys).

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>

+that way the two nodes are all the existing nodes in the graph.

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>

+together once can be formed on one of the following conditions:

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

+<li>There are 2 boys present.</li>

+<li>There are 2 girls present.</li>

+<li>There is an even number of boys and an even number of girls who wish to

+pariticipate in the circle.</li>

+<li>There is exactly one boy and exactly one girl.</li>

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

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

+<h3><a href="./">Back to the Math-Ventures web page</a></h3>