# 16 people, make 3 consecutive round of 4 players

I am struggling with this issue for a tournament I am planning.

Take 16 people.
Consider a 4-player game.
To be clear, in each round all 16 players must play the game once.

I want to make at least 3 rounds of the game with players that have never encountered each other before.

Example, where players are named from "A" to "P"

First round:

ABCD   EFGH   IJKL   MNOP


Second round:

AEIM   BFJN   CGKO   DHLP


Etc..

Is 3 feasible?

Is it feasible with these specific first 2 rounds?

Is it possible to go to 4 or more?

If not, is there a proof that 3 is the max?

• Each player meets 3 other players in each round, and there are 15 other players. So it takes at least 5 rounds to play with every other player. Jun 11, 2019 at 13:15
• The question is not to find how many rounds, but the possible distribution of the first rounds, where "playing versus someone never encountered" is only a constraint. Jun 11, 2019 at 13:19
• I assume OP doesn't want any single pair to play more than once Jun 11, 2019 at 13:20
• I mean, it should be possible to have up to 5 rounds without meeting more than once. Jun 11, 2019 at 13:21
• Some directions towards the theory behind this question: it is closely related to the field of block designs, namely Steiner systems. If I get it right, your problem is related to the parametrization S(2,4,16). A better known very similar problem is Kirkman's schoolgirl problem, which addresses a similar question but is related to S(2,3,15). Jun 12, 2019 at 10:29

ABCD EFGH IJKL MNOP
AEIM BFJN CGKO DHLP
AFKP BELO CHIN DGJM
AGLN BHKM CEJP DFIO
AHJO BGIP CFLM DEKN


Generated with C#:

void Main()
{
// List of players A...P
var players = string.Join("", Enumerable.Range(0, 16).Select(i => (char)('A' + i)));

// Set of players each has yet of meet.
var unmet = players.ToDictionary(c => c, c => players.Replace(c, '.'));

Console.WriteLine(BuildGroups(players, unmet));
Console.WriteLine(BuildGroups(players, unmet));
Console.WriteLine(BuildGroups(players, unmet));
Console.WriteLine(BuildGroups(players, unmet));
Console.WriteLine(BuildGroups(players, unmet));
}

string BuildGroups(string players, Dictionary<char, string> unmet)
{
var result = "";
for (int iGroup = 0; iGroup < 4; iGroup++)
{
var remaining = players;
var currentGroup = "";
for (int iPosition = 0; iPosition < 4; iPosition++)
{
var player = remaining.FirstOrDefault(_ => _ != '.');
if (player == default(char)) return null; // No player possible. Abort.

currentGroup += player;
remaining = Intersect(remaining, unmet[player]);
players = players.Replace(player, '.');
}
if (result != "") result += " ";
result += currentGroup;
}

// Update 'unmet'. Remove players that are now in the same group.
for (int i = 0; i < result.Length; i++)
{
if (result[i] == ' ') continue;
for (int j = i + 1; j < result.Length; j++)
{
if (result[j] == ' ') break;
unmet[result[i]] = unmet[result[i]].Replace(result[j], '.');
unmet[result[j]] = unmet[result[j]].Replace(result[i], '.');
}
}
return result;
}

{
return string.Join("", mask1.Zip(mask2, (x,y) => x == '.' ? '.' : y));
}

• Ah! I came up with the exact same arrangement using C to back up my comment, to find you already did so. Jun 11, 2019 at 14:05
• So it looks like it does have to do with mutually orthogonal latin squares after all (Glorfindel mentioned them in his now-deleted incorrect answer). If you put the 16 people in a 4x4 square, the first round groups the rows together for each game, the second round groups the columns together, but the groups of the last three rounds correspond to three orthogonal Latin squares. Jun 11, 2019 at 14:25
• Oh, cool, this also applies to that wolves and sheep problem asked a while back. The 100-players in 10-player game equivalent of this question should have an answer of 4 maximum rounds, based on what I'm reading in OEIS A001438. That's why groupings of 10 isn't a good approach to that question. Jun 11, 2019 at 15:04

Exactly the same result as Markus Jarderot, who got there while I was writing.

Result from C code:

 ABCD   EFGH   IJKL   MNOP
AEIM   BFJN   CGKO   DHLP
AFKP   BELO   CHIN   DGJM
AGLN   BHKM   CEJP   DFIO
AHJO   BGIP   CFLM   DEKN

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLES  4
#define SEATS   4
#define PLAYERS 16

int met[PLAYERS][PLAYERS];
int table[TABLES][SEATS];
int seated[PLAYERS];

void show(void)
{
for(int t=0; t<TABLES; t++) {
for(int s=0; s<SEATS; s++) {
printf("%c", 'A' + table[t][s]);
}
printf("   ");
}
printf("\n");
}

void seating(void)
{
memset(seated, 0, sizeof seated);
for(int t=0; t<TABLES; t++) {
for(int s=0; s<SEATS; s++) {
int found = 0;
for(int p=0; p<PLAYERS; p++) {
if(seated[p] == 0) {
int prev = 0;
for(int i=0; i<s; i++) {
if(met[ table[t][i] ][ p ]) {
prev = 1;
break;
}
}
if(prev == 0) {
table[t][s] = p;
for(int i=0; i<s; i++) {
met[ table[t][i] ][ p ] = 1;
met[ p] [ table[t][i] ] = 1;
}
seated[p] = 1;
found = 1;
break;
}
}
}
if(found == 0) {
puts("Can't find a person");
exit(1);
}
}
}
}

int main(void) {
for(int i=0; i<PLAYERS; i++) {
seating();
show();
}
}

Just for a bit of variety same answer as above but using PL/SQL

ABCD
EFGH
IJKL
MNOP
------------------------------------------------
AEIM
BFJN
CGKO
DHLP
------------------------------------------------
AFKP
BELO
CHIN
DGJM
------------------------------------------------
AGLN
BHKM
CEJP
DFIO
------------------------------------------------
AHJO
BGIP
CFLM
DEKN
------------------------------------------------


Program

 declare

-- declare variables
v_round_num number default 1;
v_game_num number := 1;
can_continue boolean default true;

--declare types
type players is TABLE of VARCHAR2(1);
type game is TABLE of varchar2(1);
type round is TABLE of game;
type rounds is TABLE of round;

-- declare instances of our types
my_game1 game := game();  my_game2 game := game();  my_game3 game := game();  my_game4 game := game();
my_round round := round();
my_rounds rounds := rounds();
my_players players := players('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P');

-- function to check if current player has played anyone else in the game previously
function has_played(player1 varchar2, cur_game game) return boolean is

v_check_round number default 1;
v_has_played boolean default false;

begin
-- need to check all previous rounds
while v_check_round <= v_round_num loop
-- need to check all games in the prevous rounds
for v_game_check in 1..4 loop
-- check against all players in the game
for v_player2 in 1..cur_game.count loop
begin
-- actual check
v_has_played := player1 member of my_rounds(v_check_round)(v_game_check) and  cur_game(v_player2) member of my_rounds(v_check_round)(v_game_check);
exception when SUBSCRIPT_BEYOND_COUNT then
-- means we have got to the final game that is not yet full so can just return
exit;
end;
if v_has_played then
return v_has_played;
end if;
end loop;
end loop;
v_check_round := v_check_round + 1;
end loop;
return v_has_played;
end has_played;

begin

while can_continue = true loop

-- extend and itialise arrays for new round
my_rounds.extend(); my_round := round(); my_rounds(v_round_num) := my_round;

-- loop through each of the players and try and add them to one of the games.
-- if the game is full move or they have already played someone in that game move on to the next game and try again
-- if they cannot be added to any game then we are done.
for i in 1..16 loop
if my_game1.count < 4 and has_played(my_players(i), my_game1) = false then
my_game1.extend(); my_game1(my_game1.count) :=  my_players(i);
elsif my_game2.count < 4 and has_played(my_players(i), my_game2) = false then
my_game2.extend(); my_game2(my_game2.count) :=  my_players(i);
elsif my_game3.count < 4 and has_played(my_players(i), my_game3) = false then
my_game3.extend(); my_game3(my_game3.count) :=  my_players(i);
elsif my_game4.count < 4 and has_played(my_players(i), my_game4) = false then
my_game4.extend(); my_game4(my_game4.count) :=  my_players(i);
else
-- if we can not find anywhere to add the player then we are done.
can_continue := false;
exit;
end if;
end loop;

if can_continue then
--extend and add the games for this round to the array
my_rounds(v_round_num).extend; my_rounds(v_round_num)(1) := my_game1;
my_rounds(v_round_num).extend; my_rounds(v_round_num)(2) := my_game2;
my_rounds(v_round_num).extend; my_rounds(v_round_num)(3) := my_game3;
my_rounds(v_round_num).extend; my_rounds(v_round_num)(4) := my_game4;

-- reset games to blank ready for next iteration.
my_game1 := game();  my_game2 := game();  my_game3 := game();  my_game4 := game();

-- for each of the four games in a round output the each of the players
for disp_game in 1..4 loop
dbms_output.put_line(my_rounds(v_round_num)(disp_game)(1) || my_rounds(v_round_num)(disp_game)(2) || my_rounds(v_round_num)(disp_game)(3) || my_rounds(v_round_num)(disp_game)(4));
end loop;

dbms_output.put_line('------------------------------------------------');
v_round_num := v_round_num + 1;
end if;
end loop;
end;