[Solved]: The buckets of water problem

Problem Detail: 

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 http://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).

Asked By : George

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30357