10
$\begingroup$

In a table tennis tournament, there are 7 different tables and 10 players. Every player has to play exactly 7 matches (one match at each table). It's not allowed to play twice against the same opponent. Is it possible? If yes, give a solution.

$\endgroup$
1

6 Answers 6

8
$\begingroup$

A schedule is

possible

In more detail:

Here is a schedule. For each pair of players it shows at which table they play each other.

enter image description here

The solution can easily be extended to 9 tables.

My approach was trial and error. I started exactly like Alaiko, from the top, trying to fit matches on unused tables, but it started to be messy. I then restarted, trying to keep it nice and orderly. And somehow this solution emerged.

Further developments (bonus question in the comments):

I tried to pack the 9-table solution in 9 rounds, but managed only 10.

So I wrote a program to search for a solution. There are plenty of solutions, here is one of them for 10 players, 9 tables, 9 rounds. The rows are the rounds, the columns are the tables, but you can also read it the other way round.

    AB  __  __  GH  CD  __  IJ  __  EF
    __  AC  EI  __  HJ  __  BG  DF  __
    EG  BJ  AD  FI  __  __  __  __  CH
    __  __  __  AE  GI  DJ  CF  BH  __
    DH  __  GJ  __  AF  CE  __  __  BI
    CI  __  FH  BD  __  AG  __  EJ  __
    FJ  DI  __  __  BE  __  AH  CG  __
    __  EH  __  CJ  __  BF  __  AI  DG
    __  FG  BC  __  __  HI  DE  __  AJ
 

I ran the same program with only 7 tables, but no solution matched the tables assignment of the original solution. So I removed the constraint on the table assignments and found plenty of solutions. Here is one. I didn't find any specially nice or symmetric one.

    AB  EF  IJ  CD  GH  __  __
    EH  AC  __  FG  BI  DJ  __
    CF  GI  AD  __  __  BH  EJ
    GJ  BD  FH  AE  __  __  CI
    DI  HJ  __  __  AF  CE  BG
    __  __  BE  HI  CJ  AG  DF
    __  __  CG  BJ  DE  FI  AH
  

$\endgroup$
2
  • $\begingroup$ Bonus: Does this decompose nicely into a schedule of 7 rounds, where 5 tables are occupied during each round? $\endgroup$
    – Stef
    Commented Dec 25, 2023 at 12:03
  • $\begingroup$ For 9 tables, I found a schedule in 10 rounds. $\endgroup$
    – Florian F
    Commented Dec 25, 2023 at 16:21
5
$\begingroup$

This is

possible with the following matches at each table:

Table No: Groupings:
1 [A-B][C-D][E-J][F-G][H-I]
2 [A-C][B-I][D-J][E-F][G-H]
3 [A-D][B-J][C-G][E-H][F-I]
4 [A-E][B-C][D-F][G-I][H-J]
5 [A-F][B-D][C-H][E-I][G-J]
6 [A-G][B-E][C-I][D-H][F-J]
7 [A-H][B-F][C-J][D-I][E-G]

Here was my approach to find the pairings (may not be the best one, but it did work in this case):

Start with A. Assign it a partner from B to H.
Then, for B, start from Table 2. Since we left off at H in the list of partners, we begin with I this time for B. After assigning I and J to B, we cycle back to C since A has already been used up. The table will look like the following after these two steps:

Table No: Groupings:
1 [A-B]
2 [A-C][B-I]
3 [A-D][B-J]
4 [A-E][B-C]
5 [A-F][B-D]
6 [A-G][B-E]
7 [A-H][B-F]

Then, for C, we repeat - move one table down and start from Table 3. Continue by assigning G to C in table 3 (since we left off at F last when assigning to B). This strategy will be repeated for all the next letters that we are trying to assign to the tables.

If it is not possible to place the current letter at a particular table because it has already been assigned to that table, then move one table down for the next placement of that letter. If it is not possible to assign a partner to the current letter because that partner has already been assigned to that table or because there will be no more partners left for other tables, then move one down in the list of remaining partners.

Eventually, you will reach the table shown at the top.

$\endgroup$
4
$\begingroup$

Careful: I forgot the "one match at each table" when I wrote this answer. Therefore, it's either incomplete or wrong.


I believe this is

possible.

The total number of matches is

$\frac{7 \times 10}{2}=35$ (each of the 10 players has to play 7 matches, and a match consists of 2 players)

The total number of possible pairing of players is

$\binom{10}{2}=45$ (to make a possible pairing, you choose two distinct players from the set of 10 players)

Now, since each player has to play against 7 other players,

each player will not encounter exactly two players. Among the 45 possible pairs, 10 of them must not appear in the 35 played matches.

Which means

if we manage to find ten pairs with every player appearing exactly two times, that means the 35 other pairs will form a set of matches such that every player plays exactly 7 matches against different opponents.
For example : (1,2) ; (3,4) ; (5,6) ; (7,8) ; (9, 10) ; (1,3) ; (2,4) ; (5,10) ; (6,8) ; (7,9)

Visual explanation:

solution

$\endgroup$
2
  • 5
    $\begingroup$ That just shows that there are enough pairings. You still need to show how they can be scheduled so that every player uses every table once. $\endgroup$
    – fljx
    Commented Dec 22, 2023 at 13:38
  • $\begingroup$ Oops, you're right, I totally overlooked that condition. $\endgroup$
    – Jujustum
    Commented Dec 22, 2023 at 14:16
4
$\begingroup$

As I suspected earlier, there is an elegant way to generate solutions to this puzzle. It's essentially a round-robin tournament, except that the rounds have been replaced by tables. The standard algorithms for scheduling such tournaments use a ring-based procedure. Wikipedia has several diagrams, and a proof that each pair of players is generated exactly once. I think the circle diagram of Lucas is the clearest.

This algorithm can be easily implemented in a few lines of Python.

Code

""" Round Robin Tournament
    Lucas circle method
    Written by PM 2Ring 2023.12.24
"""

# Must be even
num = 10
w = num // 2

ring = list(range(1, num))

for i in range(1, num):
    seq = [0] + ring
    print(i, *zip(seq[:w], seq[:w-1:-1]))
    ring = ring[-1:] + ring[:-1]

Output

1 (0, 9) (1, 8) (2, 7) (3, 6) (4, 5)
2 (0, 8) (9, 7) (1, 6) (2, 5) (3, 4)
3 (0, 7) (8, 6) (9, 5) (1, 4) (2, 3)
4 (0, 6) (7, 5) (8, 4) (9, 3) (1, 2)
5 (0, 5) (6, 4) (7, 3) (8, 2) (9, 1)
6 (0, 4) (5, 3) (6, 2) (7, 1) (8, 9)
7 (0, 3) (4, 2) (5, 1) (6, 9) (7, 8)
8 (0, 2) (3, 1) (4, 9) (5, 8) (6, 7)
9 (0, 1) (2, 9) (3, 8) (4, 7) (5, 6)

Here's a live version running on SageMathCell.

$\endgroup$
1
  • $\begingroup$ That's a great find. $\endgroup$
    – Simd
    Commented Dec 24, 2023 at 11:47
2
$\begingroup$

This is a generalised exact cover problem. Donald Knuth gives an algorithm for solving exact cover problems which he calls Algorithm X. It's a "recursive, nondeterministic, depth-first, backtracking algorithm".

In an exact cover problem, we have a set X and a collection Y of subsets of X. The goal is to select subsets from Y that cover X. That is, the selected subsets contain all the elements of X exactly once. In a generalised exact cover problem, we have primary elements which must be covered exactly once, but we also have secondary elements that may be covered at most once. Knuth realised that we can easily convert a generalised problem to a standard exact cover by supplying "dummy" subsets to cover the secondary elements. Any secondary elements which don't get covered by the main subsets will get covered by the dummy subsets.

Algorithm X is used to solve many well-known combinatorial problems, eg Sudoku, Eight queens, graph colouring, and polyomino tilings.

Knuth admits that Algorithm X is just a systematic brute-force solution, but at least it works. ;) There are often more efficient algorithms for solving exact cover, especially when the problem has lots of symmetry. So I expect that there's a smarter solution to this tournament puzzle.

The usual way to implement Algorithm X uses Knuth's Dancing Links, which involves a grid of doubly-linked circular lists. That's great in languages like C, but it's a bit tedious in languages which don't have pointers. In Python, it's more convenient to implement Algorithm X using dictionaries.

In this puzzle, we must cover each player+table combination, and we may cover each player+player combination. In my Python implementation I label the players with integers and the tables with letters. The set X consists of all the player+table pairs plus all player+player pairs. The primary subsets in Y are of the form

Y[t, p0, p1] = [(p0, t), (p1, t), (p0, p1)]

where t is the table letter and p0 & p1 are player numbers.

The "dummy" subsets are of the form

Y[p0, p1] = [(p0, p1)]

Any dummy subsets found in a solution are simply discarded.

Here is my Python code, running on the SageMathCell server. When a solution is found, we create lists so that we can verify (by inspection) that each player plays at every table and that they meet each other player once, at most. Here's the first solution.

A 0 7
A 1 8
A 2 6
A 3 5
A 4 9
B 0 9
B 1 7
B 2 8
B 3 6
B 4 5
C 0 6
C 1 5
C 2 7
C 3 4
C 8 9
D 0 5
D 1 3
D 2 9
D 4 6
D 7 8
E 0 8
E 1 9
E 2 3
E 4 7
E 5 6
F 0 2
F 1 4
F 3 7
F 5 8
F 6 9
G 0 3
G 1 6
G 2 5
G 4 8
G 7 9

0 ABCDEFG
[2, 3, 5, 6, 7, 8, 9]

1 ABCDEFG
[3, 4, 5, 6, 7, 8, 9]

2 ABCDEFG
[0, 3, 5, 6, 7, 8, 9]

3 ABCDEFG
[0, 1, 2, 4, 5, 6, 7]

4 ABCDEFG
[1, 3, 5, 6, 7, 8, 9]

5 ABCDEFG
[0, 1, 2, 3, 4, 6, 8]

6 ABCDEFG
[0, 1, 2, 3, 4, 5, 9]

7 ABCDEFG
[0, 1, 2, 3, 4, 8, 9]

8 ABCDEFG
[0, 1, 2, 4, 5, 7, 9]

9 ABCDEFG
[0, 1, 2, 4, 6, 7, 8]

The code can quickly generate many thousands of solutions. Of course, many solutions will be isomorphic, since we can generate new solutions by reordering the players or the tables.

$\endgroup$
2
  • $\begingroup$ Sorry, I'm on my phone & I don't know a simple way to put my solution into a spoiler. $\endgroup$
    – PM 2Ring
    Commented Dec 23, 2023 at 10:00
  • $\begingroup$ I think you just add >! before a paragraph. $\endgroup$
    – Simd
    Commented Dec 23, 2023 at 10:13
1
$\begingroup$

Attempt at an organized answer:

Pretend the players are vertices. If we can draw a path that loops through each vertex exactly once, it will have length 10, and we can take alternating steps to divide the players into five disjoint pairs. Five pairs constitutes a table (since we can count that 5 games must be played at each table). There are two disjoint ways to do this for such a looping path. It will be convenient, then, if we can find multiple disjoint paths of this kind.

Imagine the vertices in the shape of a pentagonal prism (which will give some structure involving the factorization of $10=5\cdot 2$ that is less clear if we just put the vertices evenly spaced around a circle). If we consider only edges connecting the two pentagons, there are only 5 possible opponents for each player. This isn't enough, so some of our paths must have intra-pentagon edges. Let $A, B, C, D, E$ be the vertices of one pentagon, and $F, G, H, I, J$ be the corresponding vertices of the other. We can easily make two paths using intra-pentagon edges -- one using the boundary of the pentagons and one using the pentagrams; both traveling only between corresponding vertices (at different locations). These are, e.g. $A, B, C, D, E, J, I, H, G, F$ and $B, E, C, A, D, I, F, H, J, G$. Then, we can easily find two paths that alternate between the pentagons; in the first we will shift by one when alternating: $A, G, C, I, E, F, B, H, D, J$. In the second, we will shift by two: $A, H, E, G, D, F, C, J, B, I$. (We have avoided traveling between corresponding vertices as we have already used some of those edges.) This is enough for 8 tables (of which we can choose any 7). We have used 40 out of 45 edges. Because the 40 edges touch each vertex the same number of times, so must the remaining 5 edges; in other words, the remaining 5 edges must form a 9th disjoint table. For this example, these edges are: $(C, H); (A, E); (B, D); (F, J); (G, I)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.