5
$\begingroup$

I came across this well known problem that goes something like this.

If $n$ people shake hands with each other. How many handshakes will be there in total?

The question can be interpreted as asking about the number of edges in a complete graph of with $n$ vertices, which will be $n \choose 2 $.

What if the question was changed to something more tricky?

If $n$ people take turns playing board games with each other. Each game needs exactly $k$ players to play. How many games are needed for everyone to have played a game with everyone else?

As you can see, for the case of $k=2$ this would be equivalent to the previous handshake problem.

I initially thought the answer would be $ n \choose k$, but in the case of $n = 6$ and $ k= 4$ , I can make everyone play everyone with just 3 games.

If the players are labeled $[1 .. n]$

$$ \text{Game 1: } {1,2,3,4} \\\text{Game 2: } {3,4,5,6} \\\text{Game 3: } {1,2,5,6} $$

Since $ {6 \choose 4} \neq 3 $, this cannot be the answer. The binomial is counting all possible games even when getting everyone to play each is possible with less games.

I suspect that considering the games as hyperedges of k-uniform hypergraph is the best way to approach this problem, but I lack any formal math training beyond high-school math, so I don't know where to start. I've tried doing some googling (which is how I know what a hypergraph is), but I've haven't gotten anywhere.

$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

Every game makes $\binom k2$ associations of players, and we need to cover all $\binom n2$ pairs of players, so a lower bound for the number of games is $\left\lceil\binom n2\big/\binom k2\right\rceil$. In your example case, $\left\lceil\binom 62\big/\binom 42\right\rceil = \lceil 15/6\rceil = 3$ so you have found the minimum.

However this minimum may not always be achievable. It's relatively straightforward to demonstrate that 10 people playing 6-player games cannot all experience all game partners within only 3 games, despite the lower bound $\left\lceil\binom {10}2\big/\binom 62\right\rceil = \lceil 45/15\rceil = 3$.

$\endgroup$
2
  • $\begingroup$ So there isn't any way to get the true minimum number of games besides brute force? $\endgroup$ Commented Nov 13, 2021 at 11:55
  • $\begingroup$ @Bejofo There is probably also an upper limit on the "true minimum" - I'd have to think about that - but between these two (in most cases) I would expect a bit of a search. According to this answer there is a special case but it would be rare. $\endgroup$ Commented Nov 13, 2021 at 21:41

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.