# Optimal tournament design puzzle

There are four people playing a tournament for a game that has two players per game

The problem is how to set up the games of the tournament so that no one person sits out for more than N games in a row.

Below is a scheme where no one person sits out for more than 2 games in a row
(Each column denotes a game, ‘x’ denotes that a player is playing in a particular game, ‘-’ denotes they are sitting it out)

``````
Joe    x--x-x
Bill   xx--x-
Ted    -xx--x
Bob    --xxx-

``````

Is there a scheme where no one person sits out for more than 1 game in a row? I assume not, but is there a way to prove that?

It seems to me that if there are M players, there is a minimum N number of games that players must sit out in a row, under any scheme.

Has this problem (i.e. finding N as a function of M) been solved in some area of mathematics, under a different guise?

I’m assuming you only have the facilities to run one game at a time, and that everyone shows up at the beginning. No, there is no such scheme.

Four players mean each plays three games, and there are six total games. For people to play every other game is possible, but the pairings wouldn’t change. Therefore, in a tournament format at least one person is going to sit out multiple games in a row.

Assumptions:

• There are 4 players
• A game consists of 2 people
• Only one game can be played at a time
• Each player must play every other player.

Pick two people at random to play first, label them A and B; label the others C and D. In order for C or D to not sit out twice in a row, they must both be in the next game. In determining who shall play the third game, A and B just sat out so they must play again. But then A never plays anyone but B. Thus any schedule that has each player play someone else will require someone to sit out two or more games in a row.

The same reasoning shows that someone must play two games in a row.
As for extending it to larger number, it’s possible but much harder.

Missed edit window after i realized I knew what was going on, ugh.

I’m sure someone that’s deep into combinatorics has studied this problem. In combinatorics I remember studying something called “balanced incomplete block designs” which is a more inclusive name to schemes of forming various groups in a systematic way such that each member was included in the same number of groups and each group had the same number of members(that is, balanced), but each group did not contain every member(incomplete). I recall a bunch of equations relating some of the important quantities, but not anything related to the spans of groups of which a member is not part of. I think there might be a counting argument similar to the smallest non-trivial case you just suggested, but I’d have to look into it.

A v B -> W1
C v D -> W2
W1 v W2