# Permutations of 10 players within 2 Badminton courts: Covering $10$-vertex complete graph $K_{10}$ by two disjoint $K_4$

I am facing this everyday problem and I wanted to actually see how to formalise and reason on. We have 10 players and two courts in our badminton matches. We define a shift to be an instance of badminton games happening where two teams of 4 players are playing against each other in the respective courts and the remaining two are resting. We assume that we always are able to have the two games happening side by side in the two courts and they both end at around the same time. That is one can imagine in a permutation of these ten players in each subsequent shifts.

Now I want to solve for taking the least number of shifts to get all the players to encounter each other. I can combinatorially create permutations where following 6 shifts each player encounters another. I would like to know whether there can be no possibility of getting the solution with lesser number of shifts.

I want to know more on how to reason for the above problem or what tools to use to solve such a combinatorial situation? How does one go about formalising and algorithmically strategising such combinatorial problems? Thank you.

My playing around with the problem solution instance and coming up with 6 shifts. Let $$\{\ a,b,c,\ldots,j\ \}$$ be the set of players. $$a^x$$ at shift $$k$$ indicates that player $$a$$ has encountered $$x$$ many different players by and including shift $$k$$, for eg. in shift $$1$$, each player playing the game has encountered three other distinct players:

Shift $$1:\ a^3 b^3 c^3 d^3\ -\ e^3 f^3 g^3 h^3\ -\ i^0 j^0$$

Shift $$2:\ a^6 i^3 e^5 f^5\ -\ b^6 j^3 g^5 h^5\ -\ c^3 d^3$$

Shift $$3:\ i^6 g^7 c^6 h^7\ -\ e^7 f^7 j^6 d^6\ -\ a^6 b^6$$

Shift $$4:\ a^8 g^9 h^9 d^8\ -\ e^9 f^9 b^8 c^8\ -\ i^6 j^6$$

Shift $$5:\ a^9 c^9 j^8 e^9\ -\ b^9 i^8 d^9 f^9\ -\ g^9 h^9$$

Shift $$6:\ a^9 b^9 i^9 j^9\ -\ c^9 d^9 g^9 h^9\ -\ e^9 f^9$$

I am quite sure taking out $$ij$$ in the 4th shift is where it took more shifts!

• Are the pairings fixed? If not then does playing with someone constitute encountering? In other words, will I "encounter" 2 or 3 people in my first game? Commented Apr 14 at 18:04
• yes, playing with someone constitutes encountering. yes, 3 people in the first game for 8 of them. for the two who didn't get a chance, it'd be zero. Commented Apr 14 at 19:00
• And the pairings? Do you have the same partner for all games? Commented Apr 14 at 19:44
• No you are free to pair up with whomever you want Commented Apr 15 at 6:13
• Could you include your six-shift solution in the OP? The problem definition needs some illustration to be clarified.
– Amir
Commented Apr 15 at 7:16

It is related to covering graph problems, in which the minimum number of subgraphs of a given graph $$G$$ with a specific property is determined such that the union of the subgraphs is $$G$$. The problem in the OP, $$G=K_{10}$$ and each subgraph is composed of two disjoint $$K_4$$. Now you are able to find the relevant literature.

The case of covering a complete graph with $$K_4$$ is an old problem also known as covering pairs with quadruples, and the covering number is denoted by $$C(n,4,2)$$. From Section 7 of the linked paper, we have $$C(10,4,2)=9$$. Hence, the solution of the OP is at least

$$\left \lceil \frac{C(10,4,2)}{2} \right \rceil=5.$$

The existing 9 quadruples cannot be paired in 5 shifts (three of matches need to be held in a single shift).

Update: It turns out the optimal value is $$\color{blue}{5}$$, and the solution is

$$S_1: (1, 4, 5, 8), (2, 7, 9, 10)$$ $$S_2: (5, 6, 8, 9), (2, 3, 4, 7)$$ $$S_3: (1, 4, 6, 9), (3, 5, 8, 10)$$ $$S_4: (1, 3, 9, 10), (2, 5, 6, 7)$$ $$S_5: (3, 4, 6, 10), (1, 2, 7, 8)$$

• Thanks so much for the tools to approach such problems, I was totally lost on where I should even try to begin! Commented Apr 15 at 12:29
• @Ramit You are welcome!
– Amir
Commented Apr 15 at 15:33
• thanks for the update! :) Commented Apr 22 at 15:48