1
$\begingroup$

There is a competition going on where 5 different games are occurring at 5 different stations. Also, there are only 5 time slots during the competition. Once the time runs out, every team rotates to another station. There are 10 teams and each of the teams has to play at a different station. The team can not stay at the station and must relocate and they can not return back to the station. Once a team arrives at a different station, they have to compete against a different team (so a team can not play the same team twice). Finally, there can only be 2 teams at a station.

To Clarify, here are the rules:

  • there are only 5 time slots (this determines when the teams change stations)
  • team must move after time runs out
  • team must play a different team when they arrive at a new station
  • there can only be 2 teams at a station at once (the two teams that are competing against eachother)

How does one schedule this with these restrictions? Please help.

Here is what I have done:

Guess and check, I've tried just filling out a 5x5 grid (5 stations vs 5 time slots) and I would always get stuck on the last line. The last line could not be filled out as there were repeat of teams at a station, or two teams that have already competed would compete again.

$\endgroup$
1
$\begingroup$

Divide the ten teams into two groups of five. Scheduling with the given restrictions is equivalent to finding a Graeco-Latin square of order 5; the two Latin squares correspond to the two groups of teams.

The following is an admissible schedule, numbering the teams from 0 to 9. Each column is one venue and each timeslot is one row.

01 27 43 69 85
23 49 65 81 07
45 61 87 03 29
67 83 09 25 41
89 05 21 47 63
$\endgroup$
  • $\begingroup$ how did you calculate this? is there an algorithm? $\endgroup$ – Ricky Kim Oct 16 '18 at 1:51
  • $\begingroup$ @RickyKim I just plucked the Latin square from Wikipedia. There are such arrangements for any $2n$ teams, except 12 teams. $\endgroup$ – Parcly Taxel Oct 16 '18 at 1:52
1
$\begingroup$

Since 10 is twice an odd number, the following is easy to remember:

Arrange the events in a circle. Half the teams move clockwise from one event to the next; the other half move anticlockwise.

$\endgroup$
  • $\begingroup$ Thanks! this helped me visualize the problem and understand better. $\endgroup$ – Ricky Kim Oct 16 '18 at 4:22

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.