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


1 Answer 1


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.

  • $\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
    Commented Sep 27, 2014 at 21:59
  • $\begingroup$ Perhaps, though the obvious idea doesn't work. $\endgroup$ Commented Sep 27, 2014 at 22:02
  • $\begingroup$ So, there may exists some psudo polylog algorithm to solve that problem? $\endgroup$
    – Tacet
    Commented Jan 20, 2016 at 23:07
  • $\begingroup$ I had an interesting thought regarding this language. As you showed the language is NP-Hard. I was trying to show it's Complete, but is the language really in NP? Because the witness is most likely to be a series of actions (filling buickets etc..), and that might be too long. Must we change something in the definition of the language for it to be in NP? And if we do not change any thing - Can we tell for sure it is not NP? That there is no better (polynomial) witness. $\endgroup$
    – Eric_
    Commented Jul 2, 2020 at 17:03
  • $\begingroup$ Sounds like an interesting question! Perhaps you'd like to ask it separately. $\endgroup$ Commented Jul 2, 2020 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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