1

I believe this problem is unsolvable (as in there is no correct solution). Can somebody confirm that there is no solution?

If there were 4 Teams of 4 Players as follows...

Team A

Art (A1) Andy (A2) Angela (A3) Adam (A4)

Team B

Brian (B1) Brenda (B2) Brady (B3) Bobby (B4)

Team C

Carl (C1) Connie (C2) Colt (C3) Cam (C4)

Team D

Dan (D1) Dave (D2) Debbie (D3) Dennis (D4)

If they each play in a 4-Player game is there any combination of game pairings such that each player plays each player not on his team exactly once?

-Brian

Brian Muller
  • 11

1 Answers1

2

Here is a solution:

First round    Second round   Third round   Fourth round
-----------    ------------   -----------   ------------
A0,B0,C0,D0    A0,B1,C2,D3    A0,B2,C3,D1   A0,B3,C1,D2
A1,B1,C1,D1    A1,B0,C3,D2    A1,B3,C2,D0   A1,B2,C0,D3
A2,B2,C2,D2    A2,B3,C0,D1    A2,B0,C1,D3   A2,B1,C3,D0
A3,B3,C3,D3    A3,B2,C1,D0    A3,B1,C0,D2   A3,B0,C2,D1

Each round looks like:

A0,Bx,Cy,Dz
A1,B-,C-,D-
A2,B-,C-,D-
A3,B-,C-,D-

and the indices of the players in the lower right 9 positions (indicated by - in the general shape) is always the binary XOR of the A player in the game and the index of the player from their own team who meets A0 in that round.

(This use of XOR is why I renumbered the players from 1-4 to 0-3).

I believe this is the unique solution, up to permutations of the rounds and permutations within each team. In particular, by exhaustive search I think for any solution it's always possible to renumber the just the players such that the first two rounds are exactly as above; the third and fourth then seem to be forced to be the above ones too.

hmakholm left over Monica
  • 286,031