My family has recently started taking tennis lessons. In one of the lessons there were 6 students and we got to play on 3 courts. The instructor wanted each of us to play with each other so we had 3 singles matches going simultaneously on 3 courts and we switched players after 2 games. He had us switch the players on one side of the court to the other courts. In other words, the first pairing was:
1 -- 2 Court 1
3 -- 4 Court 2
5 -- 6 Court 3
and the second pairing was:
1 -- 6 Court 1
3 -- 2 Court 2
5 -- 4 Court 3
and the third pairing was:
1 -- 4 Court 1
3 -- 6 Court 2
5 -- 2 Court 3
Since there are a total of $\left(\begin{array}{c}n\\2\end{array}\right)$ = n(n-1)/2 pairs and we can play n/2 games at a time on n/2 courts (let us consider the case of even n for the moment), we should be able to have different pairings at most n-1 times. In the above case of 6 students (n=6), we should be able to have 5 such rotations. But having the first 3 rotations as above, it is easy to see that it is not possible to have a 4th set of pairings without some of the pairs being repeated since players 1, 3, 5 have each played 2,4,6 respectively and thus needed to play each other which cannot be done simultaneously. So we asked ourselves the question, is it possible to have n-1 rotations where each person with play another person exactly once?
My son looked at the configurations and came up with the following algorithm to pair players. Fix one player and rotate the other players around a loop. In other words, keeping player 1 fixed, and rotating the remaining players clockwise, the pairings are:
Court 1 1 -- 2 1 -- 3 1 -- 5 1 -- 6 1 -- 4
Court 2 3 -- 4 5 -- 2 6 -- 3 4 -- 5 2 -- 6
Court 3 5 -- 6 6 -- 4 4 -- 2 2 -- 3 3 -- 5
It is easy to see that this is equivalent to the well-known polygon method of assigning round robin tournaments. Since my son is a fan of Minecraft, he also created a machine in Minecraft that illustrated this process using pistons to move colored blocks around. He made one piston to pull out one of the blocks and then rotate the remaining blocks around a loop. Finally the block that was pull out is reinserted into the group. Pictorially, it looks like this:
Starting configuration:
1 2
3 4
5 6
One block is pulled out (where x represent an empty slot):
1 x 2
3 4
5 6
The remaining 5 blocks (with the empty slot) are rotated clockwise:
1 3 x
5 2
6 4
Block 1 is inserted back (and pushing block 3 across to the right) resulting in the first rotation:
1 3
5 2
6 4
Sunday, September 30, 2012
Subscribe to:
Posts (Atom)