2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Weather Vane Jun 11 at 13:15
  • $\begingroup$ 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. $\endgroup$ – Lefth Jun 11 at 13:19
  • $\begingroup$ I assume OP doesn't want any single pair to play more than once $\endgroup$ – athin Jun 11 at 13:20
  • $\begingroup$ I mean, it should be possible to have up to 5 rounds without meeting more than once. $\endgroup$ – Weather Vane Jun 11 at 13:21
  • $\begingroup$ 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). $\endgroup$ – elias Jun 12 at 10:29
5
$\begingroup$
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;
}

string Intersect(string mask1, string mask2)
{
    return string.Join("", mask1.Zip(mask2, (x,y) => x == '.' ? '.' : y));
}
$\endgroup$
  • $\begingroup$ Ah! I came up with the exact same arrangement using C to back up my comment, to find you already did so. $\endgroup$ – Weather Vane Jun 11 at 14:05
  • $\begingroup$ 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. $\endgroup$ – Jaap Scherphuis Jun 11 at 14:25
  • $\begingroup$ 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. $\endgroup$ – Dark Thunder Jun 11 at 15:04
1
$\begingroup$

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(); } }

$\endgroup$
0
$\begingroup$

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;
  has_added boolean default false;

  --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;
$\endgroup$

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.