Problem of the Week 926


Here is a real-world problem (from the new professional football league):

Design a schedule for a 10-week season involving 8 teams playing one game a week, on Sunday. The teams are divided into two divisions, east and west.

  1. Each team plays the teams in its division twice, home and away.
  2. Each team plays the teams in the other division once.
  3. Each team plays 5 home games and 5 away games.
  4. No team ever has 3 home games in a row, or 3 away games in a row.
Source: J. Dinitz and D. Froncek, U of Vermont (Dinitz was hired as a consultant by the XFL to design their schedule).

© Copyright 2001 Stan Wagon. Reproduced with permission.

30 Jan 2001