# 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$.

• Interesting problem! It seems clear that for any combination of "number of books" and "values", there will always be a constant $\epsilon \gt 0$ which every person will attain. It is less clear that a minimum value exists which applies to all combinations. After a number of trials, the worst case minimum I have been able to get is $0.25$. Has anyone found a lower bound? – Jens May 13 '16 at 16:32
• @Jens What is your example for $0.25$? – pi66 May 13 '16 at 23:26
• Four books with the values $B_1 = (0.5, 0, 0.5, 0)$, $B_2 = (0, 0.5, 0.5, 0)$, $B_3 = (0.25, 0.25, 0, 0.5)$ and $B_4 = (0.25, 0.25, 0, 0.5)$. The values are given as $(b_1, g_1, b_2, g_2)$. – Jens May 14 '16 at 2:34
• In that case, wouldn't giving $B_3$ to the first group and $B_4$ to the second group be enough? Anyway, it's very similar to an example I found for $0.25$, so I guess you're just switching some values. – pi66 May 14 '16 at 3:16
• The second group must have at least one of the books $B_1$ or $B_2$ and at least one of the books $B_3$ or $B_4$. But this means either $b_1$ or $g_1$ can at most get $0.25$. What is your example? – Jens May 14 '16 at 3:24

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.

• I'm trying to understand your argument but I'm not big on sets. When you use the term "disjoint union" are you using it in the sense given here: mathworld.wolfram.com/DisjointUnion.html ? I understood $A_i$ to be a set of books, e.g. $A_i = \{x_2, x_5\}$, not a set of ordered pairs. Isn't $A_i$ just the union of 8 $S_j$'s? Also, I'm confused about the sets $T$. What is their relation to the $S_j$'s or $A_i$'s? Could you perhaps make a small example? Thanks. – Jens May 18 '16 at 23:01
• Yes, each $A_i$ is just a set of books and each $A_i$ is just the union of 8 $S_j$'s. I think I misused the term "disjoint union" here (I've edited my answer to fix this); I just wanted to emphasize that each of the $S_j$'s themselves were disjoint. – mhum May 18 '16 at 23:05
• Each $T$ is just one of the $S_j$'s, referred to without specifying exactly which $S_j$ it's representing. Also, note that there's a difference between $T$ and $\mathcal{T}$. The latter represents a pair of sets. – mhum May 18 '16 at 23:08
• I've made a few more edits that hopefully clears some of this up. – mhum May 18 '16 at 23:34
• Thanks, that cleared it up for me. I'm going to work my way through the rest of your argument, but it'll have to wait to tomorrow. – Jens May 18 '16 at 23:46

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. • The claim is wrong:$(0,0.5,0.5)$for$p$and$(0.5,0.25,0.25)$for$q$. – zhoraster May 23 '16 at 12:04 • Not so. A=2nd book, B=1st and 3rd books. – Aravind May 23 '16 at 15:20 • Sorry, I've misread the claim. – zhoraster May 23 '16 at 16:47 • What if$p$has$(0.4,0.1,0.2,0.3)$and$q$has$(0.1,0.3,0.4,0.2)$? The claim is still true, but in its proof, no$R\cap S$has weight at least$0.25$. – pi66 May 24 '16 at 21:58 • I don't see why one of$(B\cap C)\cup U$and$(B\cap D)\cup U$must have weight at least$0.25$for the first couple. Take$B$to contain two items$b_1,b_2$, where the first couple have weights$(0.5,0)$and$(0,0.5)$, and$C=\{b_1\},D=\{b_2\}$. Then neither of the sets have weight at least$0.25\$ to the first couple. – pi66 May 28 '16 at 16:42