Dividing books between two couples

Two couples of boys and girls, $(b_1,g_1)$ and $(b_2,g_2)$, are dividing a pile of books. Every book will go to one of the couples, and they'll read it together. Each person has a (nonnegative) value for each book they read and a total value of $1$ for the whole set of books in the pile; moreover some subset of books gives him/her value exactly $0.5$.

Does there exist a constant $c>0$ for which it is always possible to give everyone value at least $c$, no matter the values and the number of books?

Without the $0.5$ condition, the answer is no. For example, there is only one book that everyone values $1$, so one couple will get $0$.

Solution 1:

This is too late for the bounty but here I will show a lower bound of $c \geq \frac{1}{16}$. This bound can probably be improved.

First, some notation.

• Let us rename the people in the two couples as $(p_1, p_2)$ and $(p_3, p_4)$.
• Let $X$ be the total set of books.
• For each $i=1,2,3,4$ and each subset $Y \subseteq X$, let $v_i(Y)$ be the value that $p_i$ places on books in $Y$.
• Let $A_i$ be a subset of $X$ such that $v_i(A_i) = 0.5$.
• Let $\overline{A_i} = X - A_i$; note that $v_i(\overline{A_i}) = 0.5$.

Now, each element of $x \in X$ may be categorized based on which $A_i$'s it is also a member of; there are $2^4 = 16$ such possible categories. Let $S_j$ for $j=1,2,\ldots,16$ be subsets of $X$ representing each of these categories (some of the $S_j$'s may be empty).

By definition, we know that for all $i=1,2,3,4$ $$ \sum_{j=1}^{16} v_i(S_j) = 1 $$ So, for each $i$, there is some $j$ such that $$v_i(S_{j}) \geq \frac{1}{16}$$ In fact, we know even more than this. Notice that each $A_i$ is the union of 8 of the 16 $S_j$'s and $\overline{A_i}$ is the union of the other 8. Since $v_i(A_i) = v_i(\overline{A_i}) = 0.5$, then we conclude that there are actually two different $S_j$'s for each $i$ (one contained in $A_i$ and the other contained in $\overline{A_i}$) such that $v_i(S_j) \geq \frac{0.5}{8} = \frac{1}{16}$. So, for each $i=1,2,3,4$, let $\mathcal{T_i}$ represent a collection of two, disjoint sets of books such that $v_i(T) \geq \frac{1}{16}$ for each $T \in \mathcal{T_i}$ (i.e.: each $\mathcal{T_i}$ consists of two of the $S_j$ sets that $p_i$ values above $\frac{1}{16}$).

Now, we get into some case splitting.

Case 1: There exists some set $T$ such that $T \in \mathcal{T_1} \cap \mathcal{T_2}$. In other words, one of the couples shares one subset that they both value above $\frac{1}{16}$. This case is easy. Just assign $T$ to couple $(p_1, p_2)$ (which will satisfy both members) and each member of $(p_3, p_4)$ is free to pick one of the subsets out of their $\mathcal{T_i}$ sets.

Case 2: There exists some set $T \in \mathcal{T_1}$ such that $T \notin \mathcal{T_3} \cup \mathcal{T_4}$. In other words, person $p_1$ has a set that they value above $\frac{1}{16}$ that does not appear in the other couple's desired sets. Again, this is also an easy case to resolve. Assign $T$ and any set $U \in \mathcal{T_2}$ to couple $(p_1, p_2)$. Since only $U$ might appear in couple $(p_3, p_4)$'s desired sets, both of them are once again free to pick one of the subsets out of their $\mathcal{T_i}$ sets.

Case 3: Anything not covered by Case 1 or Case 2. By inspection, we realize that there are only two configurations not covered in the first two cases (each $A,B,C,D$ are distinct from one another): $$\mathcal{T_1} = \{A, B\} \qquad \mathcal{T_2} = \{C, D\} \\ \mathcal{T_3} = \{A, B\} \qquad \mathcal{T_4} = \{C, D\} $$ or $$\mathcal{T_1} = \{A, B\} \qquad \mathcal{T_2} = \{C, D\} \\ \mathcal{T_3} = \{A, C\} \qquad \mathcal{T_4} = \{B, D\} $$ Both of these cases are, of course, easily resolved as well.

Solution 2:

EDIT: This answer is wrong, except for the Claim and its proof.

Claim: Fix a pair $p,q$ of two persons. Then there exist two disjoint sets $A,B$ of books such that $A$ has weight at least 0.25 for both $p$ and $q$ and $B$ has weight at least 0.5 for both $p$ and $q$. As a shorthand, I say that $A$ has weight 0.25 for the couple {p,q}$.

Assuming the claim, let's prove a lower bound of 0.25.

Let $A,B$ be the disjoint sets of weight 0.25, 0.5 respectively for the first couple and $C,D$ be the disjoint sets of weight 0.25, 0.5 resp. for the second couple.

Let $U=B \setminus \{C \cup D\}$.

One of $(B \cap C) \cup U$ and $(B \cap D) \cup U$ must have weight at least 0.25 for the first couple.

In the first case, give the books of $(B \cap C) \cup U$ to the first couple and the books of $D$ to the second couple. In the second case, give the books of $(B \cap D) \cup U$ to the first couple and the books of $C$ to the second couple.

This completes the proof assuming the claim.

Proof of Claim:

Let $R,S$ be the sets of weight 0.5 for $p,q$ respectively. Note that $\bar{R},\bar{S}$ also have weights 0.5 for $p,q$ respectively.

Since $S,\bar{S}$ is a partition of the books, we know that one of $S$ and $\bar{S}$ must have weight at least 0.5 for $p$, say $S$.

Thus $S$ has weight at least 0.5 for both $p,q$. By a similar argument, we can assume that $R$ has weight at least 0.5 for both $p,q$.

Now I show that we can take the pair $(A,B)$ be to be one of the following: $(\bar{S},S)$, $(\bar{R},R)$, $(R \cap S$, $\bar{R} \cup \bar{S})$.

For contradiction, suppose the first two pairs don't satisfy the claim.

Then $w_1(\bar{S}) \leq 0.25$ and $w_2(\bar{R}) \leq 0.25$.

This implies that $w_1(R \cap S) \geq 0.25$ and $w_2(S \cap R)\geq 0.25$, which means that the third pair satisfies the claim.