Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Inspired by this post. I am thinking of a general case.

Reference to read.

Suppose $N,L_1,L_2,p,q$ are integers, and $N L_1 = pq$. with $p\ge 2$ and $L_1>L_2$.

Now you have $N+1$ buckets, the first $N$ buckets are full of water, each of these buckets can hold $L_1$ liters of water, the left one is a small bucket which is empty at first, the small bucket can hold $L_2$ liters of water.

Now the problem is I want to split the $N L_1$ liters of water to $p$ people evenly, everybody can get $q$ liters of water.

Question: in what situation $(L_1,L_2,N,p,q)$ we can split the water evenly, in what case we cannot.


For $p=1$ case, that means all the water will go to one people, that is easy.

For the original problem setting, if we change the capacity of the small bucket, let $(L_1,L_2,N,p,q)=(8,L_2,2,4,4)$, we can see that

  1. when $L_2 = 1$, it is easy to do, we just get $1$ liter of water every time.
  2. when $L_2 = 2$, it also easy, we just get $2$ liters of water every time.
  3. $L_2 =3$ is done in the post.
  4. $L_2=4$ is also easy as the first two.
  5. I can prove when $L_2 = 6,7$, we cannot succeed.

I guess, if $L_2>q$, then we cannot succeed. I am trying to cook up a theory on this, but very limited. Since to find out a proper way to split is kind of NP hard.

Conjecture 1: $gcd(L_1,L_2)\mid q$ and $L_2\le q$ are necessary(not sufficient) to find a solution.

share|improve this question
    
Unless you are down to the molecular level, any amount of water can be split evenly into any number of parts. Where is the problem? –  Marc van Leeuwen Mar 10 '13 at 5:35
    
If you have read the original post, you need to use the buckets to split the water. There are a lot of cases that you cannot do this. –  Yimin Mar 10 '13 at 15:14

1 Answer 1

up vote 1 down vote accepted

I think you mean $\gcd(L_1,L_2) \mid q$? It is clear that if $\gcd(L_1,L_2) \nmid q$, then no solution can exist, as all the amounts of water moved around are divisible by $\gcd(L_1, L_2)$. I shall also prove that if $L_2>q$, no solution can exist.

Indeed suppose $L_2>q$, and we assume without loss of generality that a solution exists. There are 2 possible operations.

  1. Choose a non-empty bucket $A$, and a bucket $B$ which isn't full, and pouring water from $A$ to $B$ till either $A$ is empty or $B$ is full.
  2. Choose a non-empty bucket $A$, and give all of its contents to 1 of the $p$ people.

Let $m$ be the number of buckets with $>q$ litres of water in them, at that point in time. (so $m$ changes as we make moves) Note that $m$ can decrease by at most 1 at each turn. Since we start at $m=n$ (all big buckets have $L_1>q$), and end at $m=0$ (all water distributed), there must be a move taking us from $m=1$ to $m=0$. Suppose that just before that move, bucket $P$ is the only bucket with $>q$ litres of water. In order for $m$ to become $0$, we must perform an operation involving $P$. It is clear that we cannot perform operation $2$, as that would lead to one of the $p$ people getting $>q$ litres of water. Thus we must have performed operation $1$, by pouring water from $P$ to another bucket $Q$. If we pour till $P$ is empty, then now bucket $Q$ has $>q$ litres of water, contradicting $m=0$. If we pour till $Q$ is full, then obviously bucket $Q$ has $\geq L_2>q$ litres of water, contradicting $m=0$.

Thus there can never be a move bringing us from $m=1$ to $m=0$, so no solution exists when $L_2>q$.

Now let us consider the special case $N=1$, so $L_1=pq$, $p \geq 2$. We have a solution if and only if $L_2 \mid q$. It is easy to see that a solution exists when $L_2 \mid q$ (just keep pouring water into the small bucket for distribution.

For the converse, note that if $L_2 \nmid q$, we can never finish distributing $q$ litres of water by just giving $L_2$ litres of water at a time. If we call a transfer of water using operation $2$ which transferred $\not =L_2$ litres as a special transfer, then we must have at least $p \geq 2$ special transfers.

We show that we can treat all special transfers as from operation $2$ applied to the big bucket. Note that the only way for the small bucket to be partially full at any point in time is by pouring water from the big bucket till the big bucket is empty (If we perform operation $2$ on the small bucket it would be empty) But in that case, if we had performed operation $2$ on the small bucket to get a special transfer, we can equivalently pour all the water in the small bucket into the big bucket and perform operation $2$ on the big bucket instead.

Consider the situation right after we had made the first special transfer. Then by the above argument we can treat it as having resulted from operation $2$ on the big bucket, so the big bucket is now empty. Consider the situation just before the special transfer. Then at that time, the big bucket has some water, so by above the small bucket must be either empty or full by the above argument. Now let's return to the point in time after the special transfer. Now the big bucket is empty and the small bucket is either empty ($0$ litres) or full ($L_2$ litres). It is clearly now impossible to make any more special transfers, so at most $1$ special transfer has been made, contradicting the fact that we need at least $p \geq 2$ such transfers.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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