shlomi-fish-homepage / t2 / MathVentures / disco_circle.html.wml

#include '../template.wml'

<latemp_subject "A Solidarian Disco Circle" />

<p>
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 centre, 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,
and so on.
</p>

<p>
I eventually came to wonder about this question regarding disco circles:
</p>

<table border="1">
<tr><td>
<ol>
<li>When can a group of dancers form a disco circle, such that every
girl dances with every boy once and only once?
</li>
<li>
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?
</li>
</ol>
</td></tr>
</table>

<p>
The solution can be found some space below:
</p>

<longblank />

<h2>Solution:</h2>

<p>
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”,
“G2”.
</p>

<p>
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 centre. 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>

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

<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 satisfies the request. In mathematical terminology a
drawing with lines and circles is commonly called a <b>“Graph”</b>, and
the field of mathematics that deals with graphs is called <b>Graph
Theory</b>.
</p>

<p>
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 fulfilled:<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>

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

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

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

<ol>
<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
participate in the circle.</li>
<li>There is exactly one boy and exactly one girl.</li>
</ol>
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.