1. A league has N teams. Devise a season schedule to let each team play every other team exactly once (explain the method for making this schedule.) Games are played at the same time each week. There are as many locations to play as needed. What is the minimum number of weeks needed for the season?
2. In a similar league, N teams begin a single elimination tournament. What is the minimum number of games needed to determine a champion team? What is the minimum number of weeks for the tournament?

Source: Yaacov Weiss, via email 9/24/97.

For Question 1:
For N even:  There are N/2 games per week that can be played
For N odd:   There are (N-1)/2 games per week that can be played.

Choosing 2 teams from N gives the total number of games that need to be
played:

               N!
Tgames =   ----------
             2(N-2)!

  Since # of weeks * games per week = total games played

  then

     for N even  # of weeks played is  2Tgames/N
     for N odd  # of weeks played is 2Tgames/(N-1)

  Simplified...I think.

        N even = N-1 weeks
        N odd  = N weeks

For Question 2:
# of games = N-1
# of weeks = Don't recall how to represent this math-wise but....
             The number of weeks is related to

                2^(#weeks) = N.  Using a few examples it's clear that

                ln(N)/ln(2) rounded up to the nearest integer is
                the number of weeks of play.

1.A league has N teams. Devise a season schedule to let each team play every
other team exactly once (explain the method for making this schedule.) Games are
played at the same time each week. There are as many locations to play as
needed. What is the minimum number of weeks needed for the season? 

Answer: It depends on N. If N is odd, the answer is N weeks. If N is even, the
answer is N-1 weeks.


2.In a similar league, N teams begin a single elimination tournament. What is
the minimum number of games needed to determine a champion team? What is the
minimum number of weeks for the tournament? 

Answer: Since all teams, but one, must lose once before there is a winner, the
tournament will take N-1 games. The number of weeks for the tournament is k
such that 2^(k-1) < N <= 2^k.

==========

Solution to Question 1:

When N is odd, we know that N weeks is the bare minimum because of the 
following reasoning: 
- It takes 2 teams to make a game. With an odd number of teams, one team will
sit out any given week
- Each team must play N-1 other teams.

Given that each team sits a week and plays N-1 weeks, we get N weeks for the
tournament when N is odd.

When N is even, the first condition (sitting out) doesn't occur, so we should be
able to do the tournament in N-1 weeks. What we do is generate the solution for
N-1 teams. In this solution, which takes N-1 weeks, one team is idle every week.
In any given week, we play that week's idle team against the Nth team. Since
each team is idle one week, team N ends up playing all other teams from 1 to
N-1, and the tournament takes N-1 weeks.

On to the tournament:

Create a N by N table of game pairings as follows:

     1   2   3   4   5   6   .   .   .   N  
1   1v1 1v2 1v3 1v4 1v5 1v6  .   .   .  1vN
2   2v1 2v2 2v3 2v4 2v5 2v6  .   .   .  2vN
3   3v1 3v2 3v3 3v4 3v5 3v6  .   .   .  3vN
4   4v1 4v2 4v3 4v4 4v5 4v6  .   .   .  4vN
5   5v1 5v2 5v3 5v4 5v5 5v6  .   .   .  5vN
6   6v1 6v2 6v3 6v4 6v5 6v6  .   .   .  6vN
.    .   .   .   .   .   .   .   .   .   .
.    .   .   .   .   .   .   .   .   .   .
.    .   .   .   .   .   .   .   .   .   .
N   Nv1 Nv2 Nv3 Nv4 Nv5 Nv6  .   .   .  NvN


We eliminate from the table all pairings that are impossible (a team versus
itself) and all pairings that are duplicated in the table (eg, 6v1 because 1v6
already exists). This essentially removes all pairings on the
upperleft-lowerright diagonal and below, as follows:

     1   2   3   4   5   6   .   .   .   N  
1    X  1v2 1v3 1v4 1v5 1v6  .   .   .  1vN
2    X   X  2v3 2v4 2v5 2v6  .   .   .  2vN
3    X   X   X  3v4 3v5 3v6  .   .   .  3vN
4    X   X   X   X  4v5 4v6  .   .   .  4vN
5    X   X   X   X   X  5v6  .   .   .  5vN
6    X   X   X   X   X   X   .   .   .  6vN
.    .   .   .   .   .   .   .   .   .   .
.    .   .   .   .   .   .   .   .   .   .
.    .   .   .   .   .   .   .   .   .   .
N    X   X   X   X   X   X   .   .   .   X 


Now, we put another copy of the table next to the first copy of the table,
creating a N X 2N table as follows (the row headers have been removed so the
table will fit on a 80-column screen):

1   2   3   4   5   6   .   .   .   N   1   2   3   4   5   6   .   .   .   N
X  1v2 1v3 1v4 1v5 1v6  .   .   .  1vN  X  1v2 1v3 1v4 1v5 1v6  .   .   .  1vN
X   X  2v3 2v4 2v5 2v6  .   .   .  2vN  X   X  2v3 2v4 2v5 2v6  .   .   .  2vN
X   X   X  3v4 3v5 3v6  .   .   .  3vN  X   X   X  3v4 3v5 3v6  .   .   .  3vN
X   X   X   X  4v5 4v6  .   .   .  4vN  X   X   X   X  4v5 4v6  .   .   .  4vN
X   X   X   X   X  5v6  .   .   .  5vN  X   X   X   X   X  5v6  .   .   .  5vN
X   X   X   X   X   X   .   .   .  6vN  X   X   X   X   X   X   .   .   .  6vN
.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
X   X   X   X   X   X   .   .   .   X   X   X   X   X   X   X   .   .   .   X 

To find the pairings for a specific week, we start at the second instance of
that number in the column header and go down and to the left. The matches
encountered on this diagonal are the matches for that week. Ie, to find the
pairings for the week #2, start at the second "2" header and follow the diagonal
that goes down and to the left. Using the diagonals for the second set of
headers, from 1 to N, gives us our N-week schedule for the tournament.

Specific example. Let's do a 7-week tournament. Here's the final 7 X 14 table:

1   2   3   4   5   6   7   1   2   3   4   5   6   7  
X  1v2 1v3 1v4 1v5 1v6 1v7  X  1v2 1v3 1v4 1v5 1v6 1v7
X   X  2v3 2v4 2v5 2v6 2v7  X   X  2v3 2v4 2v5 2v6 2v7
X   X   X  3v4 3v5 3v6 3v7  X   X   X  3v4 3v5 3v6 3v7
X   X   X   X  4v5 4v6 4v7  X   X   X   X  4v5 4v6 4v7
X   X   X   X   X  5v6 5v7  X   X   X   X   X  5v6 5v7
X   X   X   X   X   X  6v7  X   X   X   X   X   X  6v7
X   X   X   X   X   X   X   X   X   X   X   X   X   X

Final pairings:

Week #1: 1v7, 2v6, 3v5      4 sits out
Week #2: 2v7, 3v6, 4v5      1 sits out
Week #3: 1v2, 3v7, 4v6      5 sits out
Week #4: 1v3, 4v7, 5v6      2 sits out
Week #5: 1v4, 2v3, 5v7      6 sits out
Week #6: 1v5, 2v4, 6v7      3 sits out
Week #7: 1v6, 2v5, 3v4      7 sits out

Random Note:

Below, I'm chatting a lot about congruencies and saying things like "blah blah
blah is congruent to N (mod N)". I know that this is really 0 (mod N), but I'm
being lazy.

Interesting note:

- In a week X, the team K that sits out is the K such that 2*K is congruent to X
(mod N). This is because the sum of the numbers of the teams playing in week X
is congruent to X (mod N).

Why does it work?

Because for some number of teams N, some tournament week X, and some team number
A, there is only one other number B (where 0 < B <= N) such that A+B is
congruent to X (mod N). So, in any given week, each team can only be paired with
one other team (satisfying the condition that teams play only one game a week).
Since two given teams can only play in a certain week, this ensures that teams
will only play each other once during the course of the N-week tournament
(satisfying the exactly once condition). Also, as the week X moves from 1 to N,
a given team A's opponent goes from (1-A) mod N to (N-A) mod N, having N
distinct values from 1 to N. So, each team is ensured of playing each other team
at least once.

Enough about that.

==========

Solution to Question 2:

Each week, we can have at most [N/2] games (where "[X]" means the largest
integer <= X), since a game consists of 2 teams. So, every week we divide the
number of teams by 2 until we have 1 team left. If N is a power of two (2^k),
the tournament takes k weeks and we're done. If N isn't a power of two, we add
some "bye slots" the first week. The number of "bye slots" is however many teams
would be needed to get us to the next power of 2 greater than N. Any team that
plays a "bye slot" the first week automatically wins. After the first week,
we're at a number of teams that is a power of two and the tournament proceeds
from there.

Details on first week:
We have N teams. We add 2^k - N bye slots (where 2^k is the next power of 2
greater than N). So, 2^k - N teams automatically advance. The number of teams
that play each other is N - (2^k - N) = 2N - 2^k. Half these teams are
eliminated, leaving (2N - 2^k)/2 = N - 2^(k-1) teams. Add this to the teams that
automatically advanced and we get the number of teams left after the first week.

(2^k - N) + (N - 2^(k-1)) = 2^k - 2^(k-1) = 2^(k-1).

After this, the tournament takes k-1 weeks. Total weeks = k, where k is defined
as above.

1. Make an NxN table with N even (if N is odd, use a square table of size N+1; the last column will show the byes.)
2. Label it with the N team names in the same order on the top and the side. Remove the last row.

3. Load the first row numerically, from 1 to N-1. (Leave the last column blank.) These numbers will eventually represent the week each pair of teams plays. The table would now look like this:

   A B C D E F A 1 2 3 4 5 . B . . . . . . C . . . . . . D . . . . . . E . . . . . .

4. To fill each next row, copy the number in each location to the position immediately below and left. If in the first column, copy instead to the next-to-last column:

   A B C D E F A 1 2 3 4 5 . B 2 3 4 5 1 . C 3 4 5 1 2 . D 4 5 1 2 3 . E 5 1 2 3 4 .

5. Fill the last column with the same digit that's along the main diagonal (since teams won't be playing themselves.) Then cross out the main diagonal. The schedule is complete. The first column can be removed for clarity. Everything above the main diagonal shows which week each pair of teams plays. If N is odd, the last column shows the week a team does not play.

   B C D E F A 2 3 4 5 1 B . 4 5 1 3 C . . 1 2 5 D . . . 3 2 E . . . . 4