Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a seemingly simple question. There are 12 teams competing in 6 different events. Each event is seeing two teams compete. Is there a way to arrange the schedule so that no two teams meet twice and no teams repeat an event.

Thanks.

Edit: Round 1: All 6 events happen at the same time. Round 2: All 6 events happen at the same time. And so on until Round 6.

share|improve this question
    
Sure-don't play any games. More seriously, do you want each team to play 6 games, in which case they will only meet 6 other teams? It should be easy-just start making a chart. –  Ross Millikan May 18 '12 at 18:08
    
I once spent some hours writing up code for solving this exact problem (but with more teams) for a summer camp. Suddenly a guy walked in the door, handed me a hand-made solution, said nothing and left. –  utdiscant May 18 '12 at 18:13
    
    
Yes, each team only meets 6 other teams. I tried to make some chart but the constraints become very difficult to fulfill. The reason for such difficulty has to do with the number 6. If there were 14 teams competing in 7 events it would be much easier: it suffices to set up the teams in two groups of 7 and rotate them any which way through the 7 (prime number) events. –  Minh May 18 '12 at 18:27
    
This is reminiscent of en.wikipedia.org/wiki/Kirkman's_schoolgirl_problem –  deoxygerbe May 18 '12 at 19:00
add comment

2 Answers

A solution to the specific problem is here:

Event 1     Event 2     Event 3     Event 4     Event 5     Event 6
1  - 2      11 - 1      1  - 3      6  - 1      10 - 1      1  - 9
3  - 4      2  - 3      4  - 2      2  - 11     2  - 9      10 - 2
5  - 6      4  - 5      5  - 7      7  - 4      3  - 11     4  - 8
7  - 8      6  - 7      8  - 6      3  - 10     4  - 6      7  - 3
9  - 10     8  - 9      10 - 11     9  - 5      8  - 5      11 - 5
11 - 12     12 - 10     9  - 12     12 - 8      7  - 12     12 - 6

which came from the following webpage: http://www.crowsdarts.com/roundrobin/sched12.html

share|improve this answer
    
I realize my query wasn't specific enough. I made an edit. The above solution doesn't quite work. –  Minh May 18 '12 at 18:47
    
@Minh: What doesn't work? Maybe you want to label each column "Round 1" instead of Event 1? –  Phira May 18 '12 at 19:27
    
@Phira: Say you label each column "Round x", then you have to label each row "Event y". Then you don't want any team repeating an event. –  Minh May 18 '12 at 19:31
add comment

This can be solved generally for events of two teams where the number of events is half the number of teams and the number of rounds is one less than the number of teams.

Represent a schedule as an edge-colored complete graph. Let the vertices correspond to teams, edges correspond to an event, and colors coorespond to a round.

The graph is laid out with one vertex in the center and the remainder equally spaced in a circle around the center vertex. Each "spoke" (edge from center vertex to an outer vertex) and edges perpendicular to it share a color. In other words, a spoke from the center to an outer vertex, $v$, shares a color with edges on the vertices $n$ to the right and $n$ to left of $v$, for $0<n<\frac{t}{2}$ where $t$ is the number of teams.

Therefore, for the specific case in the question, we have the following edge-colored complete graph.

Graph generation

Since this problem only asks for the first 6 rounds, we can use the first 6 rounds generated by the graph.

        Color   Event 1    2     3     4     5     6
Round 1 (Black)     (A-B) (C-L) (D-K) (E-J) (F-I) (G-H)
Round 2 (Red)       (A-C) (B-D) (E-L) (F-K) (G-J) (H-I)
Round 3 (Yellow)    (A-D) (B-F) (C-E) (G-L) (H-K) (I-J)
Round 4 (Blue)      (A-E) (B-H) (C-G) (D-F) (I-L) (J-K)
Round 5 (Green)     (A-F) (B-J) (C-I) (D-H) (E-G) (K-L)
Round 6 (Orange)    (A-G) (B-L) (C-K) (D-J) (E-I) (F-H)
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.