Assigning tennis players to clubs

Question

Some tennis players are to be assigned to one of two rival tennis clubs. Each club has two coaches, and each coach likes a subset of the players of even size. Can we find an assignment such that if a coach likes $2d$ players, then the coach's club receives at least $d$ of those players?

---

Example: $d=1$ for all coaches - we want to give every coach at least one good player. If in the same club two coaches like the same player, it suffices to assign that player to the club. If one coach likes a player that the other club doesn't care about, that only makes things easier. Else we are in a situation where one coach likes $p_1,p_2$ and the other coach $p_3,p_4$. There are three cases depending on who the coaches in the second group like:

1. One likes $p_1, p_2$ and the other $p_3, p_4$. Assign $p_1, p_3$ to the first group and $p_2, p_4$ to the second group.

2. One likes $p_1, p_3$ and the other $p_2, p_4$. Assign $p_1, p_4$ to the first group and $p_2, p_3$ to the second group.

3. One likes $p_1, p_4$ and the other $p_2, p_3$. Assign $p_1, p_3$ to the first group and $p_2, p_4$ to the second group.

Answer 1

We have four coaches $1,2,3,4$. For $x=(a_1,a_2,a_3,a_4) \in \mathbf{F}_2^4$ where $a_i\in \{0,1\}$, let $A_x$ be set of players that are favourited by coach $i$ where $a_i=1$ and are not favourited by coach $i$ if $a_i=0$. Notice that $A_x \cap A_y=\varnothing$ for $x \ne y$ and $\bigcup_{x \in \mathbf{F}_2^4}A_x$ is the set of all players. In particular, $\displaystyle\bigcup_{x=(1,a_1,a_2,a_3)}A_x$ is set of players that coach $1$ likes.

Say coaches $1,2$ are from the first club, coaches $3,4$ from the second club.

Step 1: For each $A_x$ so $|A_x|$ is even, put half of the players from $A_x$ in one club and the other half in the other club.

If $A_x$ is odd and $x \in \{(1,1,a_3,a_4), (a_1,a_2,0,0)\}\setminus \{(1,1,1,1)\}$ then put $(|A_x|+1)/2$ players from $A_x$ to the first club, the rest put to second club. Similarly for $A_{y}$ where $y \in \{ (a_1,a_2,1,1),(0,0,a_3,a_4)\} \setminus \{(1,1,1,1)\}$ then we put more players to second club.

After this, we can guarantee that:

• For each $i$, out of $k_i$ players favourited by coach $i$ that have been selected until now, at least $(k_i-1)/2$ of them are chosen by coach $i$. It is exactly $(k_i-1)/2$ when (suppose $i=1$) $A_{(1,0,1,1)}$ is odd and $A_{(1,1,a_3,a_4)}$ is even ($(a_3,a_4) \ne (1,1)$).
• This follows that for coaches $i,j$ from different clubs: if current number of chosen players of coach $i$ is $(k_i-1)/2$ then for coach $j$ it cannot be $(k_j-1)/2$.
• First observation also implies that if two coaches $1,2$ from same club have $(k_1-1)/2$ and $(k_2-1)/2$ respectively then coaches $3,4$ have more than $k_3/2$ and $k_4/2$ players, respectively.

Step 2:

Note that we left with $x \in \{(1,0,1,0),(1,0,0,1),(0,1,0,1),(0,1,1,0),(1,1,1,1)\}$. With these observations, we can choose to plit the rest $A_x$ accordingly. I can't think of an shorter way other than caseworks using the observations.

The case where coaches $1,2$ have $(k_1-1)/2$ and $(k_2-1)/2$ players after step $1$ is short if we use the third observation.

For the other case, if coach $1$ has $(k_1-1)/2$ players (and other coaches $i$ has at least $k_i/2$) then we first try to make up for coach $1$. Since $k_1$ is odd, which means the number of coach $1$'s favourited players that have not been selected must be odd, i.e. one of $|A_x|$ for $x \in \{(1,0,1,0),(1,0,0,1),(1,1,1,1)\}$ must be odd. Pick the the odd set and split that set so first club has more players. WLOG, it is $x=(1,0,1,0)$. If coach $3$ has more than $k_3/2$ after step 1 then we have no problem, but if it is exactly $k_3/2$ then $k_3$ even, i.e. must exists one $y \in \{(0,1,1,0),(1,1,1,1)\}$ so $A_y$ is odd. We can then make up for coach $3$. After that, we can go and make up for coach $2$ (with the same argument).

Answer 2

This answer is improvement of @Toan Pham's answer.

Let four coaches $1, 2, 3, 4$. For $x \in F_2^4$, let $A_x$ be set of players that are only favorites of coach $i$ if and only if $a_i=1$. For example, $A_{1, 0, 1, 0}$ is the set of players who coach $1, 3$ want and $2, 4$ does not want.

Now we can assign each players in each $A_x$ to each team equally except one at most. It leaves just $2^{16}=65536$ possible cases for the size of each $A_x$ and we can brute force it. Moreover, the number of case decreases as $\displaystyle\bigcup_{x=(1,a_1,a_2,a_3)}A_x$ and other similar sets need to have even number of elements.

Try it online!