5
$\begingroup$

I am trying to solve a scheduling problem for a boys camp.

I have 12 teams(A through L), 6 sports for them to play, and 6 periods for them to play in(P1 through P6).

                 P1-P2-P3-P4-P5-P6
Soccer          |AB|KJ|IF|GB|EJ|CF|
Football        |CD|AL|KH|ID|GL|EH|
Kick-ball       |EF|CB|AJ|KF|IB|GJ|
Volley Ball     |GH|ED|CL|AH|KD|IL|
Hockey          |IJ|GF|EB|CJ|AF|KB|
Water Polo      |KL|IH|GD|EL|CH|AD|

Here is how schedules are ranked:

1: Teams can only play one game per period.

2: Two points are awarded for every different sport a team plays

3: One point is subtracted every time a team match-up is repeated(e.g., Team C plays team F twice)

Given this system, a perfect schedule(one where every team played every sport and never competed against the same team twice) would have a score of 144.

$\endgroup$
2
+200
$\begingroup$
                 P1-P2-P3-P4-P5-P6
Soccer          |AG|BH|CI|DL|EK|FJ|
Football        |BC|JG|DE|HI|FA|LK|
Kick-ball       |KJ|CD|GH|EF|IL|AB|
Volley Ball     |EL|FK|AJ|BG|CH|DI|
Hockey          |FI|AL|BK|CJ|DG|EH|
Water Polo      |DH|EI|FL|AK|BJ|CG|

@Vince Kroon is incorrect. Here, I have reformatted your schedule using the information from this answer mentioned by @Kevin Costello.

@Vince Kroon was correct in saying that this problem is unsolvable for $n = 2$, but it is, however, solvable for any n where $n>2$.

$\endgroup$
0
$\begingroup$

Achieving a perfect score(All teams playing all sports with no repetitions in the match-ups) isn't possible using the parameters you have.

Tl;dr You are filling in a grid of size $(n/2)^2.$, but each team only has $n-1$ possible competitors since teams can't play themselves. You could solve this problem by taking out one of the periods, adding an extra sport, creating an additional team, or divideing the campers up into an even number of teams.

To show why, let's imagine that there are only 4 teams(A through D), 2 periods, and 2 sports. Start to fill in that graph.

  1   2
1|AB|  |
2|CD|  |

As you can see, I have filled in the first column. Unfortunately, there are only two spots left in row 2, so A and B must both go there if all teams are to play all sports.Similarly, C and D must go in row 1.

On a 3 by 3 grid however, this problem is solvable.

|AB|CE|DF|
|CD|AF|BE|
|EF|BD|AC|

Since this solved grid is 1/4 of the grid you are trying to solve, let's try using it to make your grid work.

|AB|CE|DF|
|CD|AF|BE|
|EF|BD|AC|

|GH|IK|JL|
|IJ|GL|HK|
|KL|HJ|GI|

I have shown above a second solved board made by shifting all of the letters in the first grid down 6 letters(e.g. A=G, B=H...). This is half the schedule.

But now if you try you try to fill in the second half of the schedule, you return to the problem faced in the 2 by 2 example. A through F cannot be used in rows 1 to 3, and G through L cannot be used in rows 4 to 6. That being said, we must rearrange team A through F to compete in rows 4 through 6, and rearrange team G through L to compete in rows 1 through 3.

|AB|CE|DF| |GK|LH|IJ|
|CD|AF|BE| |IH|GJ|LK|
|EF|BD|AC| |KJ|IL|GH|

|GH|IK|JL| |AE|FB|CD|
|IJ|GL|HK| |CB|AD|FE|
|KL|HJ|GI| |ED|CF|AB|
                   ^
                  Repeated match-ups

Here I have filled in the grid with the minimum number of repetions(6), and I have chosen to repeat the first columns match-ups in the last row so that the maximum amount of times goes in-between repetitions. As You can see, cutting out the last period would solve the problem entirely, as would removing any of the sports. Alternately, you could divide the kids up into an odd number of teams.

$\endgroup$
  • 1
    $\begingroup$ The size of the grid is $(n/2)^2=n^2/4,$ not $n^2.$ $\endgroup$ – Randy E Apr 24 '15 at 17:48
  • $\begingroup$ @RandyE You're correct. If edited my answer accordingly. $\endgroup$ – Vince Kroon Apr 24 '15 at 18:11
  • $\begingroup$ Isn't the number of competitors for a given team still $(n-1)$? $\endgroup$ – Randy E Apr 24 '15 at 18:14
  • $\begingroup$ You have to distribute $\binom{12}{2}=66$ different pairs in a grid of $6\times 6$, such that in every column and every row all numbers appear. Sounds like a variant of Sudoku. You should look at a Sudoku solving program and adapt it to this case. I think it is better to think it as a grid $12\times 6$ and put the conditions accordingly. $\endgroup$ – san Apr 25 '15 at 3:02
  • 1
    $\begingroup$ Have you really shown that a perfect schedule is impossible, or just that your particular method doesn't work? $\endgroup$ – Kevin P. Costello Apr 25 '15 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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