Splitting a set into two disjoint sets five times, minimizing pairs in the same set

Question

Suppose you have a class of 11 students . I want to split the class into two groups five different ways, minimizing the number of times that any two students are in the same group.

In more mathematical terms, I have a set of 11 elements $S = \{a, b, c, \dots, k\}$, or $S = \{x_1, x_2, x_3, \dots, x_{11}\}$. I want to select five partitions $A_k$ and $B_k$ that minimize the expression

$$ \max_{1 \le i < j \le 5} \sum_{k=1}^{5} f(x_i,x_j) $$

where

$$ f(x_i, x_j) = \begin{cases} 1 & \quad \text{if } x_i,x_j \in A_k \\ 1 & \quad \text{if } x_i,x_j \in B_k \\ 0 &\quad \text{else} \end{cases} $$

for any two elements $x_i$ and $x_j$.

Is there an easy selection process? An enumeration approach creates ${11 \choose 5} = 462$ partitions into two sets. Taking the first set as a fixed point without loss of generality, then there are ${461 \choose 4} = 1857486555$ possible sets of 5 partitions.

One guesswork approach: remove $x_{11}$ from the set to create an even number of elements. Offset by numbers coprime to each other and to 10: 1, 3, 7

$$ \begin{align*} \{x_1, x_2, x_3, x_4, x_5\} & \{x_6, x_7, x_8, x_9, x_{10}\}\\ \{x_1, x_4, x_7, x_{10}, x_2\} & \{x_3, x_5, x_6, x_8, x_9\}\\ \{x_1, x_8, x_5, x_2, x_9\} & \{x_3, x_4, x_6, x_7, x_{10}\}\\ \end{align*} $$

For the next try an offset of two:

$$ \begin{align*} \{x_1, x_3, x_5, x_7, x_9\} & \{x_2, x_4, x_6, x_8, x_{10}\} \end{align*} $$

For the last, grab-bag of things that look like they haven't paired with $x_1$:

$$ \begin{align*} \{x_1, x_3, x_6, x_8, x_{10}\} & \{x_2, x_4, x_5, x_7, x_9\} \end{align*} $$

The maximum overlap here (I believe) is 4, an example being $\{x_6, x_{10}\}$

Answer 1

$$\{A,B,C,D,E,F\}\{G,H,I,J,K\}$$ Starting with this first partition, we want to choose the second partition so that no subset with $4$ elements is repeated. We must therefore swap exactly $3$ elements between the two set. All such swaps are identical at this point, so we can fix the second partition as: $$\{A,B,C,G,H,I\}\{D,E,F,J,K\}$$ Next, we'll want to split the $\{A,B,C\}$, $\{D,E,F\}$, and $\{G,H,I\}$ subsets in the remaining $3$ partitions. We'll take $1$ from $\{A,B,C\}$ and two from each of $\{D,E,F\}$ and $\{G,H,I\}$ to avoid repeating a $4$-element subset. The final result is: $$\{A,B,C,D,E,F\}\{G,H,I,J,K\}\\ \{A,B,C,G,H,I\}\{D,E,F,J,K\}\\ \{A,D,E,G,H,J\}\{B,C,F,I,K\}\\ \{B,D,F,G,I,J\}\{A,C,E,H,K\}\\ \{C,E,F,H,I,J\}\{A,B,D,G,K\}$$ There are $15$ pairs with $1$ occurrence, $10$ with $2$ occurrences, and $30$ with $3$ occurrences. This is the best I've been able to achieve, and the only way that avoids having $4$ occurrences of any pair.

Answer 2

Note: The answer of @Logophobic seems to be very close to an optimal solution. Here is some elementary information which makes this claim reasonable together with some aspects which could be helpful to find a proper selection of the sets $A_k,B_k$.

If we denote the eleven players with $\{x_1,x_2,\ldots,x_{11}\}$ we observe that @Logophobic uses some kind of bisection to determine the members of the sets $A_k,B_k$ with $k=1,\ldots,5$. In the following table we write $0$ if the student is in $A_k$ and $1$ if it is in $B_k$. We sometime also denote due to a more compact notation the students simply with their index $i$ instead of $x_i$. We obtain

\begin{array}{cccccc} &\text{student }x_i&k=1&k=2&k=3&k=4\\ A&1&0&0&0&\\ B&2&0&0&1&0\\ C&3&0&0&1&1\\ D&4&0&1&0&0\\ E&5&0&1&0&1\\ F&6&0&1&1&\\ G&7&1&0&0&0\\ H&8&1&0&0&1\\ I&9&1&0&1\\ J&10&1&1&0\\ K&11&1&1&1\\ \end{array}

This is for the first $\lfloor \log_2(11)\rfloor+1=4$ steps a proper subdivision. The bisection guarantees, that in each step $k+1$ as much students as possible are separated into the sets $A_{k+1},B_{k+1}$ which were before in the same set $A_k$, resp. $B_k$.

In the following we look at this subdivision in some more detail which enables us to also find a proper separation for all steps till $k=5$.

It's convenient to use instead of OPs function $f$ a function $d$ (aka distance) which is $1$ if students $x_i$ and $x_j$ are in different sets and $0$ if they are in the same set. This reverses the task in finding sets $A_1,\ldots,A_5$ so that the minimum distance of two students $x_i$ and $x_j$ is maximal. We are looking for \begin{align*} \max_{{A_k\subset\{x_1,\ldots,x_{11}\}}\atop{1\leq k\leq 5}}\min_{1 \le i < j \le 11}\tag{1} \sum_{k=1}^{5} d_k(x_i,x_j) \end{align*} with

\begin{align*}d_k(x_i,x_j)= \begin{cases} 1&x_i\in A_k,x_j\in B_k\\ 1&x_j\in A_k,x_i\in B_k\\ 0&otherwise\\ \end{cases} \end{align*}

Step $k=1$:

Here and in the following steps we look at two tables. The first table is a $11\times 11$ matrix $M_k$ with entries $1$ if $x_i$ and $x_j$ are in the same set and $0$ otherwise. A second table is a $11\times 11$ matrix $S_k$ which sums up these entries.

The first selection is

\begin{array}{ll} A_1=\{x_1,x_2,x_3,x_4,x_5,x_6\}\quad&\quad B_1=\{x_7,x_8,x_9,x_{10},x_{11}\}\\ \end{array}

which corresponds to following tables

\begin{array}{ccccccccccccc} M_1=S_1&1&2&3&4&5&6&7&8&9&10&11\\ 1&&&&&&&1&1&1&1&1\\ 2&&&&&&&1&1&1&1&1\\ 3&&&&&&&1&1&1&1&1\\ 4&&&&&&&1&1&1&1&1\\ 5&&&&&&&1&1&1&1&1\\ 6&&&&&&&1&1&1&1&1\\ 7&1&1&1&1&1&1&&&&&\\ 8&1&1&1&1&1&1&&&&&\\ 9&1&1&1&1&1&1&&&&&\\ 10&1&1&1&1&1&1&&&&&\\ 11&1&1&1&1&1&1&&&&&\\ \end{array}

In the first step the matrix $M_1$ and the sum matrix $S_1$ are the same. The statistics table below summarizes some essential aspect. For each of student $x_j,1\leq j \leq 11$, we see the number - $d_0$ specifying the number of students which have always been in the same set as $x_j$ - $d_1$ specifying the number of students which was at least once a member of the other set. - prio students with prio $1$ should be separated in the next step withi highest priority, then students with prio $2$, etc.

\begin{array}{ccccccccccccc} k=1&1&2&3&4&5&6&7&8&9&10&11\\ d_0&5&5&5&5&5&5&4&4&4&4&4\\ d_1&5&5&5&5&5&5&6&6&6&6&6\\ prio&1&1&1&1&1&1&2&2&2&2&2\\ \end{array}

Strategy: In order to reach the maximum in (1) as close as possible, we have to eliminate all those which have a positive entry in $d_0$. The higher the number in $d_0$ the more students are in the same set as $x_j$. So, these numbers have to be reduced with highest priority.

We see that $x_1,\ldots,x_6$ have $d_0=5$. So, these have to be separated with prio $1$. The other five students $x_7,\ldots,x_{11}$ have $d_0=4$ and they will be separated with prio $2$.

In order to do so we will separate $x_1,x_2$ and $x_3$ from $x_4,x_5$ and $x_6$ and similarly for the other five students.

Step $k=2$:

The second selection is according to the paragraph above

\begin{array}{ll} A_1=\{x_1,x_2,x_3,x_4,x_5,x_6\}\quad&\quad B_1=\{x_7,x_8,x_9,x_{10},x_{11}\}\\ A_2=\{x_1,x_2,x_3,x_7,x_8,x_9\}\quad&\quad B_2=\{x_4,x_5,x_6,x_{10},x_{11}\}\\ \end{array}

which corresponds to following tables

\begin{array}{cccccccccccccccccccccccc} M_2&1&2&3&4&5&6&7&8&9&10&11&\ S_2&1&2&3&4&5&6&7&8&9&10&11\\ 1&&&&1&1&1&&&&1&1&\ 1&&0&0&1&1&1&1&1&1&2&2\\ 2&&&&1&1&1&&&&1&1&\ 2&0&&0&1&1&1&1&1&1&2&2\\ 3&&&&1&1&1&&&&1&1&\ 3&0&0&&1&1&1&1&1&1&2&2\\ 4&1&1&1&&&&1&1&1&&&\ 4&1&1&1&&0&0&2&2&2&1&1\\ 5&1&1&1&&&&1&1&1&&&\ 5&1&1&1&0&&0&2&2&2&1&1\\ 6&1&1&1&&&&1&1&1&&&\ 6&1&1&1&0&0&&2&2&2&1&1\\ 7&&&&1&1&1&&&&1&1&\ 7&1&1&1&2&2&2&&0&0&1&1\\ 8&&&&1&1&1&&&&1&1&\ 8&1&1&1&2&2&2&0&&0&1&1\\ 9&&&&1&1&1&&&&1&1&\ 9&1&1&1&2&2&2&0&0&&1&1\\ 10&1&1&1&&&&1&1&1&&&\ 10&2&2&2&1&1&1&1&1&1&&0\\ 11&1&1&1&&&&1&1&1&&&\ 11&2&2&2&1&1&1&1&1&1&0&\\ \end{array}

we obtain

\begin{array}{ccccccccccccc} k=2&1&2&3&4&5&6&7&8&9&10&11\\ d_0&2&2&2&2&2&2&2&2&2&1&1\\ d_1&6&6&6&5&5&5&5&5&5&6&6\\ prio&1&1&1&2&2&2&2&2&2&3&3\\ \end{array}

We see in the statistics table above that many entries $x_1,\ldots,x_9$ have two students which were never separated in different sets. But the first three $x_1,\ldots,x_3$ have also six students which have been separated only once from these. Since we want to reach a maximum of the minimum values, these three should be regarded with prio $1$. The other six students $x_4,\ldots,x_9$ get prio $2$ and the last two get prio $3$. Now we are ready for a proper selection in the next step.

Step $k=3$:

The next selection is according to the paragraph above

\begin{array}{ll} A_1=\{x_1,x_2,x_3,x_4,x_5,x_6\}\quad&\quad B_1=\{x_7,x_8,x_9,x_{10},x_{11}\}\\ A_2=\{x_1,x_2,x_3,x_7,x_8,x_9\}\quad&\quad B_2=\{x_4,x_5,x_6,x_{10},x_{11}\}\\ A_3=\{x_1,x_4,x_5,x_7,x_8,x_{10}\}\quad&\quad B_3=\{x_2,x_3,x_6,x_{9},x_{10}\}\\ \end{array}

which corresponds to following tables

\begin{array}{cccccccccccccccccccccccc} M_3&1&2&3&4&5&6&7&8&9&10&11&\ S_3&1&2&3&4&5&6&7&8&9&10&11\\ 1&&1&1&&&1&&&1&&1&\ 1&&1&1&1&1&2&1&1&2&2&3\\ 2&1&&&1&1&&1&1&&1&&\ 2&1&&0&2&2&1&2&2&1&3&2\\ 3&1&&&1&1&&1&1&&1&&\ 3&1&0&&2&2&1&2&2&1&3&2\\ 4&&1&1&&&1&&&1&&1&\ 4&1&2&2&&0&1&2&2&3&1&2\\ 5&&1&1&&&1&&&1&&1&\ 5&1&2&2&0&&1&2&2&3&1&2\\ 6&1&&&1&1&&1&1&&1&&\ 6&2&1&1&1&1&&3&3&2&2&1\\ 7&&1&1&&&1&&&1&&1&\ 7&1&2&2&2&2&3&&0&1&1&2\\ 8&&1&1&&&1&&&1&&1&\ 8&1&2&2&2&2&3&0&&1&1&2\\ 9&1&&&1&1&&1&1&&1&&\ 9&2&1&1&3&3&2&1&1&&2&1\\ 10&&1&1&&&1&&&1&&1&\ 10&2&3&3&1&1&2&1&1&2&&1\\ 11&1&&&1&1&&1&1&&1&&\ 11&3&2&2&2&2&1&2&2&1&1&\\ \end{array}

we obtain

\begin{array}{ccccccccccccc} k=3&1&2&3&4&5&6&7&8&9&10&11\\ d_0&0&1&1&1&1&0&1&1&0&0&0\\ d_1&6&3&3&3&3&5&3&3&5&5&3\\ prio&2&1&1&1&1&3&1&1&3&3&3\\ \end{array}

We see in the statistics table above, since $d_0=0$ five times that five students are at least once separated from all other students. So we keep the focus on the students with $d_0=1$. This suggest a separation $x_2,x_3$ and $x_4$ in one set and $x_5,x_7$ and $x_8$ in the other set. The separation of the other elements is accordingly. We obtain

Step $k=4$:

The next selection is according to the paragraph above

\begin{array}{ll} A_1=\{x_1,x_2,x_3,x_4,x_5,x_6\}\quad&\quad B_1=\{x_7,x_8,x_9,x_{10},x_{11}\}\\ A_2=\{x_1,x_2,x_3,x_7,x_8,x_9\}\quad&\quad B_2=\{x_4,x_5,x_6,x_{10},x_{11}\}\\ A_3=\{x_1,x_4,x_5,x_7,x_8,x_{10}\}\quad&\quad B_3=\{x_2,x_3,x_6,x_{9},x_{10}\}\\ A_4=\{x_2,x_4,x_6,x_7,x_9,x_{10}\}\quad&\quad B_4=\{x_1,x_3,x_5,x_{8},x_{11}\}\\ \end{array}

which corresponds to following tables

\begin{array}{cccccccccccccccccccccccc} M_4&1&2&3&4&5&6&7&8&9&10&11&\ S_4&1&2&3&4&5&6&7&8&9&10&11\\ 1&&1&&1&&1&1&&1&1&&\ 1&&2&1&2&1&3&2&1&3&3&3\\ 2&1&&1&&1&&&1&&&1&\ 2&2&&1&2&3&1&2&3&1&3&3\\ 3&&1&&1&&1&1&&1&1&&\ 3&1&1&&3&2&2&3&2&2&4&2\\ 4&1&&1&&1&&&1&&&1&\ 4&2&2&3&&1&1&2&3&3&1&3\\ 5&&1&&1&&1&1&&1&1&&\ 5&1&3&2&1&&2&3&2&4&2&2\\ 6&1&&1&&1&&&1&&&1&\ 6&3&1&2&1&2&&3&4&2&2&2\\ 7&1&&1&&1&&&1&&&1&\ 7&2&2&3&2&3&3&&1&1&1&3\\ 8&&1&&1&&1&1&&1&1&&\ 8&1&3&2&3&2&4&1&&2&2&2\\ 9&1&&1&&1&&&1&&&1&\ 9&3&1&2&3&4&2&1&2&&2&2\\ 10&1&&1&&1&&&1&&&1&\ 10&3&3&4&1&2&2&1&2&2&&2\\ 11&&1&&1&&1&1&&1&1&&\ 11&3&3&2&3&2&2&3&2&2&2&\\ \end{array}

we obtain

\begin{array}{ccccccccccccc} k=4&1&2&3&4&5&6&7&8&9&10&11\\ d_0&0&0&0&0&0&0&0&0&0&0&0\\ d_1&3&3&2&3&2&2&3&2&2&2&0\\ prio&1&1&2&1&2&2&1&2&2&2&3\\ \end{array}

This is what we like! We see that $d_0=0$ for all students. So, we have found a separation where each student is separated at least once from all the other students. We also see that student $x_{11}$ is even separated twice from each other student. We follow the strategy and reduce the highest values $d_1$. This implies the following final separation in step five.

Step $k=5$:

The next selection is according to the paragraph above

\begin{array}{ll} A_1=\{x_1,x_2,x_3,x_4,x_5,x_6\}\quad&\quad B_1=\{x_7,x_8,x_9,x_{10},x_{11}\}\\ A_2=\{x_1,x_2,x_3,x_7,x_8,x_9\}\quad&\quad B_2=\{x_4,x_5,x_6,x_{10},x_{11}\}\\ A_3=\{x_1,x_4,x_5,x_7,x_8,x_{10}\}\quad&\quad B_3=\{x_2,x_3,x_6,x_{9},x_{10}\}\\ A_4=\{x_2,x_4,x_6,x_7,x_9,x_{10}\}\quad&\quad B_4=\{x_1,x_3,x_5,x_{8},x_{11}\}\\ A_5=\{x_3,x_5,x_6,x_8,x_9,x_{10}\}\quad&\quad B_5=\{x_1,x_2,x_4,x_{7},x_{11}\}\\ \end{array}

which corresponds to following tables

\begin{array}{cccccccccccccccccccccccc} M_5&1&2&3&4&5&6&7&8&9&10&11&\ S_5&1&2&3&4&5&6&7&8&9&10&11\\ 1&&&1&&1&1&&1&1&1&&\ 1&&2&2&2&2&4&2&2&4&4&3\\ 1&&&1&&1&1&&1&1&1&&\ 2&2&&2&2&4&2&2&4&2&4&3\\ 3&1&1&&1&&&1&&&&1&\ 3&2&2&&4&2&2&4&2&2&4&3\\ 1&&&1&&1&1&&1&1&1&&\ 4&2&2&4&&2&2&2&4&4&2&3\\ 5&1&1&&1&&&1&&&&1&\ 5&2&4&2&2&&2&4&2&4&2&3\\ 6&1&1&&1&&&1&&&&1&\ 6&4&2&2&2&2&&4&4&2&2&3\\ 1&&&1&&1&1&&1&1&1&&\ 7&2&2&4&2&4&4&&2&2&2&3\\ 8&1&1&&1&&&1&&&&1&\ 8&2&4&2&4&2&4&2&&2&2&3\\ 9&1&1&&1&&&1&&&&1&\ 9&4&2&2&4&4&2&2&2&&2&3\\ 10&1&1&&1&&&1&&&&1&\ 10&4&4&4&2&2&2&2&2&2&&3\\ 1&&&1&&1&1&&1&1&1&&\ 11&3&3&3&3&3&3&3&3&3&3&\\ \end{array}

we obtain

\begin{array}{ccccccccccccc} k=5&1&2&3&4&5&6&7&8&9&10&11\\ d_0&0&0&0&0&0&0&0&0&0&0&0\\ d_1&0&0&0&0&0&0&0&0&0&0&0\\ d_2&6&6&6&6&6&6&6&6&6&6&6\\ \end{array}

Finally we could even get $d_1=0$ for all students. So, we have found a separation where each student is separated at least twice from all the other students. Here we've added instead of a row with priority a row with $d_2$ showing that each student has value $d_2=6$ which makes a substantial improvement $d_2=0$ in $k=5$ steps not plausible.

Final remarks:

• We've reached in step $k=4$ a separation for each student at least once from all the other students and in step $k=5$ even a separation for each student at least twice. Since the values of $d_2=6$ in all positions. We conclude that a significant improvment with $\max=3$ seems not feasible.

• In case of equal $d_0,d_1$ values a refinement with higher $d_2, d_3,\ldots$ may improve the result gradually.

• Here we stick on a division in $5$ and $6$ students for the $A_k$ and $B_k$. Note that if we select $1\leq m\leq 10$ students for $A_k$ (we don't want the sets to be empty), the number of $1$'s in the matrix $M_k$ is $2m(11-m)$ which reaches the maximum for $m=5$, resp. $m=6$. Since we want to separate as many students in each step as possible, the selection $m=6$ is reasonable.