5
$\begingroup$

Let's consider the following problem (buckets/pails of water problem) (This problem may be known with different name. If does, please correct me).

Let $B=\{b_1,...,b_n\}$ be a set of $n$ buckets. Suppose each bucket has a maximum capacity $c_i \in \mathbb{Z}$. This also can be written as a maxium capacity function $f:B \rightarrow \mathbb{Z}$ such that $f(b_i)=c_i$.

Let $g:B \rightarrow \mathbb{Z}$ be a function such that $g(b_i)$ is the current amount of water in bucket $b_i$.

Suppose that we can do the following operations.

1.Fill bucket $b_i$ from tap until its full, i.e. $g(b_i)=f(b_i)$.

2.Move water from bucket $b_i$ to bucket $b_j$ until $b_i$ is empty or $b_j$ is full.

3.Empty bucket $b_i$.

Now, the problem is given a number $m \in \mathbb{Z}$ to find a sequence of operations $s_1,...,s_k$ such that after $s_k$ we have a bucket with $m$ amount of water, i.e. $g(b_i)=m$ for some $i \in \{1,...,n\}$, or return that such sequence doesn't exist.

My questions are :

1.How to solve this problem? Is this problem NP Hard? If it is NP Hard, why? How to prove this?

2.What about the case when we are interested in the optimal $k$, i.e. we want minimum number of steps?

3.Does this is a well known problem? If yes, what is the known name for the problem and what good references exists for this problem?

I want to note that I fully understand the case of $n=2$, and I am interested in the generalization of $n$ buckets instead of just $2$. The $n=2$ case described in https://mathoverflow.net/questions/5800/generalization-of-the-two-bucket-puzzle.

Edit: I now know how to prove that this is NP Hard problem. I want to know if there is an efficient algorithm for solving this (maybe some pseudo polynomial algorithm).

$\endgroup$
5
$\begingroup$

The problem is NP-hard, by reduction from SUBSET-SUM. Given a multiset of numbers $x_1,\ldots,x_n$ and a target $T$, consider $n$ buckets with capacity $C=x_1+\cdots+x_n$, initially filled with $x_1,\ldots,x_n$, and ask whether you can obtain a bucket filled with exactly $T$. You can prove by induction that all buckets are always with filled either with $C$ or with the sum of some (possibly empty) subset of the $x_i$s.

$\endgroup$
  • $\begingroup$ Thank you. I understood your reduction. I know how to solve the subset sum problem with dynamic programming in pseudo polynomial time. Is there a similar algorithm for solving the buckets problem? $\endgroup$ – George Sep 27 '14 at 21:59
  • $\begingroup$ Perhaps, though the obvious idea doesn't work. $\endgroup$ – Yuval Filmus Sep 27 '14 at 22:02
  • $\begingroup$ So, there may exists some psudo polylog algorithm to solve that problem? $\endgroup$ – Tacet Jan 20 '16 at 23:07

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.