2
$\begingroup$

Suppose you have n players in a tournament. In each game, exactly 4 players play against each other. What is the minimum number of games needed such that every player has played every other player at least once.

For example, supposed a tournament has 5 players $\{a, b, c, d, e\}$. Then the rounds could be $\{a, b, c, d\}$, $\{a, b, c, e\}$, $\{d, e, a, b\}$. So each player has played every other player at least once in 3 games.

This is similar to a round robin tournament, except each game consists of more than two players (in this case it consists of 4 players).

$\endgroup$
  • $\begingroup$ Since there are ${n(n-1)\over2}$ pairs of players, and $6$ pairs in a game, then $\left\lceil{n(n-1)\over12}\right\rceil$ games are necessary, but as your example with $n=5$ shows, this may not be sufficient. $\endgroup$ – saulspatz Jul 2 '19 at 17:02
2
$\begingroup$

There are two cases where I know how to do it, when the number of players $m$ is of the form $m=4^n$, and when $m$ is of the form $m={3^n-1\over2}$. These correspond to two types of finite geometries with $4$ points on a line. In the first case, we can consider the players as points in affine $n$ space over $\mathbb{F}_4$, the field with four elements. In the second case, we consider them as points in projective $n-1$ space over $\mathbb{F}_3.$ In either case, two points determine a line, so if we take all the lines as the games, each pair of players will meet exactly once, which is clearly the best possible. In these cases then, the minimum number of games is $$\left\lceil{m(m-1)\over12}\right\rceil.$$

I suspect these are the only cases in which this minimum can actually be achieved.

Unfortunately, these cases don't seem to cast any light on the remaining ones. In those cases, we have to have some pairs meet more than once, which eliminates any possibility of considering the games as lines.

We also need a good way of determining the minimum number is specific cases, so we can try to guess the pattern (if there is one.) For example, the best I've done so far with $8$ players is $6$ games, but is it the minimum? How to check?

P.S.

I realize of course that one can check with a computer program; I meant, "Is there an easy way to check by hand?"

EDIT

This appears to be A011976, the covering number $C(n,4,2).$ Since OEIS only lists values up to $n=20$, computation is probably hard. Apparently, it is an open problem to find a formula, but I don't know how up to-date-this site is. This paper discusses upper and lower bounds, and construction of coverings in some cases. A much more extensive table is cited by @Henry in the comments.

$\endgroup$
  • 1
    $\begingroup$ A better lower bound could be $\left\lceil{\frac{n}{4}\left\lceil{\frac{n-1}{3}}\right\rceil}\right\rceil$ saying that each player must play at least $\left\lceil\frac{n-1}{3}\right\rceil$ games so at least $n\left\lceil\frac{n-1}{3}\right\rceil$ player-games and at least $\frac n4\left\lceil\frac{n-1}{3}\right\rceil$ games in total since each game accommodates $4$ players. This deals with your $8$ player case but is still too low for $7$ players $\endgroup$ – Henry Jul 2 '19 at 23:51
  • $\begingroup$ @ Henry This is apparently the Schönheim bound, mentioned at the start of the paper I cited. $\endgroup$ – saulspatz Jul 3 '19 at 14:08
  • 1
    $\begingroup$ ljcr.dmgordon.org/cover/table.html seems to gives values (or upper bounds?) in the second column of the first table up to $n=99$ and links to example covers $\endgroup$ – Henry Jul 3 '19 at 14:43
  • $\begingroup$ @Henry In the second column, all the numbers are in bold, so far as I can tell so they should all be the best possible. Good find. I need to find out how they computed these. My program was painfully slow. $\endgroup$ – saulspatz Jul 3 '19 at 14:52

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.