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

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113``` ```#include '../template.wml'

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.

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?

The solution can be found some space below:

Solution:

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

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.

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 satisfies the request. In mathematical terminology a drawing with lines and circles is commonly called a “Graph”, and the field of mathematics 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 fulfilled:
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).

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.

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 of girls who wish to participate in the circle.
4. There is exactly one boy and exactly one girl.
```