# Emptying jugs by choosing partition of subsets

Let $c\in [0,1/2]$ and $n\in\mathbb{Z}^+$. We have $2^n-1$ jugs of water labeled with distinct nonempty subsets of $A=\{1,2,\dots,n\}$. A jug labeled with a subset of size $k$ contains $c^k(1-c)^{n-k}$ liters of water. An allowed operation is to choose some jugs whose labels form a partition of $A$, and pour out the same amount of water from each of these jugs. Can we empty the water in all jugs using this operation repeatedly?

For example, when $n=4$ we can empty all jugs as follows:

• Pour out all water from the jug labeled $\{1,2,3,4\}$.

• Pour out $c^3(1-c)$ liters of water from the jugs labeled $\{1,2,3\}$ and $\{4\}$. (Note that $c^3(1-c)\le c(1-c)^3$, so we can do this.) Similarly with $\{1,2,4\}$ and $\{3\}$, $\{1,3,4\}$ and $\{2\}$, and $\{2,3,4\}$ and $\{1\}$.

• Pour out $c(1-c)^3-c^3(1-c)=c(1-c)(1-2c)$ liters of water from the jugs labeled $\{1\},\{2\},\{3\},\{4\}$.

• Pour out $c^2(1-c)^2$ liters of water from the jugs labeled $\{1,2\}$ and $\{3,4\}$. Similarly with $\{1,3\}$ and $\{2,4\}$, and $\{1,4\}$ and $\{2,3\}$.

In general, we can empty a jug whose label has size at least $n/2$ by pairing it with its complement, but how can we make sure we empty the jugs with label of size less than $n/2$? As pointed out in a comment, for small enough $c$ (in terms of $n$) this can be done by using the singletons to empty everything else.

• For small enough $c$ then yes. Use the singletons to empty everything else, so, if we want to empty subset $A$ we choose $A$ along with every other other singleton not contained in $A$. for large enough values of $A$ there is more water in the singletons than the rest of the subsets, after that just empty the singletons at once, since the singleton's form a partition. Jan 1, 2016 at 20:21
• Do you want to find the values of $n$ such that it is possible to empty the bucket regardless of what the values for $k$ are? Jan 3, 2016 at 1:44
• I think if $n>4$ and $c$ is amost $\frac{1}{2}$ it is always impossible. Jan 3, 2016 at 1:53
• @dREaM I'm asking whether it's possible for all $n$ and all $c\in[0,1/2]$ (so your question is "harder" than mine). I'm not sure about your latter statement, since you wrote yourself that when $c$ is small enough it is possible.
– nan
Jan 3, 2016 at 3:12
• Oh ok, so then it would be enough if I give you a value for $n$ and a value for $c$ for which it is impossible? Of course, along with a proof that it is impossible? Jan 3, 2016 at 4:21

We let $n=11$ and we let $c=\frac{1}{2}-\epsilon$.

Notice the only way to empty $\{1,2,3\dots 11\}$ is by itself, so we get that over with first.

The only way to empty the buckets of size $10$ is with their complements, so we do that next.

Now we move on to the buckets of size $9$. If we make $\epsilon$ small enough, the buckets of size $1$ will be almost empty (because we used them previously), so if we want to empty the bottles of size $9$ we will have to use their complements.

Using the same arguments for the buckets of sizes $8,7,6$ we end up in the following situation:

All the bottles of sizes $1,2,3$ and $4$ have been used at least once, and all of the bottles of size $5$ have been used exactly once. So only the buckets of sizes $1,2,3,4,5$ remain and the buckets with the most liquid left, have almost the same amount as the buckets of size $5$.

Now, notice that for every two buckets of size $5$ we want to empty we need at least one bucket of size $1,2$ or $3$ in other words, every time we empty a bucket of size $5$, a bucket of size $1,2$ or $3$ is also used (although we can empty two buckets of size $5$ at the same time). So we need at least $\binom{11}{5}/2=231$ buckets of sizes $1,2$ and $3$, while only $11+55+165=231$ exist. But notice that it is impossible to empty two buckets of size $5$ at the same time by only using one bucket of size $2$. So it is in fact impossible to do it by using exactly $231$ buckets. Hence it is impossible when $n=11$ and $\epsilon$ is sufficiently small.

• "So we need at least $\binom{11}{5}/2=231$ buckets of sizes $1$ and $2$" -- do you mean of size $1,2,3$? ; "But notice that it is impossible to empty two buckets of size $5$ at the same time by only using one bucket of size $1$." -- it's possible, isn't it?
– nan
Jan 3, 2016 at 16:30
• Hmm, you're right, is it ok now? Jan 3, 2016 at 16:33
• Yes, should be ok now (:
– nan
Jan 3, 2016 at 16:34