# Game tournament program, NP complete?

I have been trying to find a solution both theoretical and practical to my problem but I just can't. The question is you have x players that should play some rounds y of games in groups of 4. Now if a player was in a game with somebody else, he is not allowed to be ever again with that player in the same group. Now the question is give n groups that satisfy this conditions. With n being maximal amount of possible groups.

My first approach was to just take a player put him into a group, now for the next player check the array already_played_with_players of the first player for the second player if he's not in add him and add the players he played with to the already_played_with_players array. Proceed so too for the next two players. Then mark these 4 players as in a group and take the next player out of the pool and so on.

This is not some educational question, but a real world problem. I would like to organize a game tournament, but so that people meet new people and don't play with the same people again. I already ask multiple people mathematicians, physicians, computer scientist, but the solution was not really evident to anybody. So I was wondering if the problem is NP-complete? I know I would need to find a reduction from another NP-complete problem to my problem to prove that, but I don't even know how to formalize my problem exactly.

• Let n = 16, and the initial Groups: {1234, 5678, 9abc, defg}, now player 1 can never be grouped with 2,3 and 4? So for every play for each player the number of possible team members decrease by 3? And the objective is to return the maximal number of groups possible (here the output is such grouping not a number)? – Evil Dec 24 '16 at 1:46
• The objective is to return the maximal number of groups possible and a specific grouping being maximal. And yes you understood the question right. For 16 players there can be 3 rounds played. But for higher numbers the process get's difficult fast and for 16 I found it out more by guessing than by a formal method. – Hakaishin Dec 24 '16 at 3:09
• I think there can be 5 rounds – skan Apr 4 '17 at 11:59
• Can you elaborate and give a specific grouping please? – Hakaishin Apr 4 '17 at 15:59

Your problem has been solved by Brouwer in 1979 in his paper Optimal Packings of $K_4$'s into a $K_n$. Quoting from his paper, let $$J(2,4,v) = \begin{cases} \lfloor \frac{v}{4} \lfloor \frac{v-1}{3} \rfloor\rfloor - 1 & \text{if } v \equiv 7 \text{ or } 10 \pmod{12}, \\ \lfloor \frac{v}{4} \lfloor \frac{v-1}{3} \rfloor\rfloor & \text{otherwise}. \end{cases}$$ The maximal number of groups when there are $v$ players, denoted $D(2,4,v)$, is equal to $J(2,4,v)$ unless $v \in \{9,10,17\}$, in which case $D(2,4,v) = J(2,4,v)-1$, and unless $v \in \{8,11,19\}$, in which case $D(2,4,v) = J(2,4,v)-2$.
The more general case in which every pair can appear at most $\lambda$ times has been solved by Assaf in his paper The packing of pairs by quadruples.
• You calculate $\lfloor \frac{16}{4} \lfloor \frac{15}{3} \rfloor \rfloor = 20$. – Yuval Filmus Apr 3 '17 at 19:28