14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Jens May 13 '16 at 16:32
  • $\begingroup$ @Jens What is your example for $0.25$? $\endgroup$ – pi66 May 13 '16 at 23:26
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Jens May 14 '16 at 2:34
  • $\begingroup$ 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. $\endgroup$ – pi66 May 14 '16 at 3:16
  • 1
    $\begingroup$ 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? $\endgroup$ – Jens May 14 '16 at 3:24
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jens May 18 '16 at 23:01
  • $\begingroup$ 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. $\endgroup$ – mhum May 18 '16 at 23:05
  • $\begingroup$ 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. $\endgroup$ – mhum May 18 '16 at 23:08
  • $\begingroup$ I've made a few more edits that hopefully clears some of this up. $\endgroup$ – mhum May 18 '16 at 23:34
  • $\begingroup$ 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. $\endgroup$ – Jens May 18 '16 at 23:46
5
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The claim is wrong: $(0,0.5,0.5)$ for $p$ and $(0.5,0.25,0.25)$ for $q$. $\endgroup$ – zhoraster May 23 '16 at 12:04
  • $\begingroup$ Not so. A=2nd book, B=1st and 3rd books. $\endgroup$ – Aravind May 23 '16 at 15:20
  • $\begingroup$ Sorry, I've misread the claim. $\endgroup$ – zhoraster May 23 '16 at 16:47
  • 1
    $\begingroup$ 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$. $\endgroup$ – pi66 May 24 '16 at 21:58
  • 1
    $\begingroup$ 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. $\endgroup$ – pi66 May 28 '16 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.