[Math] Tournament bracket for a 4-players game

algebraic-graph-theorycombinatorial-designscombinatoricsgraph theory

for Christmas a friend is trying to organize a tournament for 13 players. Each game will be played by 4 persons, each player will play 4 games and must play against everybody else.

I can find a solution, but I'd like to minimize the number of players playing two games in a row, and my solution is terrible. If someone can help us … 🙂

The problem is similar to the social golfer and the schoolgirls, but the games will be played 1 by 1.

Thank you in advance.

Best Answer

An easy way to set up such a tournament makes use of the fact that the projective plane $PG(2,3)$ consists of $13$ points on $13$ lines, each line containing $4$ points (for a graphic of that plane, see e.g. https://tex.stackexchange.com/questions/336897/).

So, you can identify the players with the points and the games with the lines, and run them in any order: Since you have a projective plane, any two lines will intersect in a single point, i.e. any two games will have one player in common. That will add up to $12$ players having to play two games in a row — I don't know how far this is from the minimum you are trying to achieve.

Related Question