5
$\begingroup$

Given three containers of specified volume, how many different volumes can you measure ?

For example, suppose we have cans with capacities 2, 3, 4 litres. We can measure :

1 litre by filling the 3 litre can and pouring it in the 2 litre can.

2, 3, 4 litres are trivial.

5 litres by filling both the 2 and 3 litre cans.

6 litres by filling the 4 litre can with 3 litres and filling the 3 litre can fully or filling the 2 and 4 litre cans.

7 litres by filling the 3 and 4 litre cans.

8 litres by getting 6 litres and filling the 2 litre can.

9 litres by filling all the cans.

The answer for this case is 9.

Is there a general way to answer this for three capacities a, b, c?

2 Answers 2

2

For the case where we have cans with $2,3,4$ liters, consider the polynomial

\begin{equation} (1+x^2)^3 (1+x^3)^2(1+x^4)^2\left(1+\frac{1}{x^2}\right)^2\left(1+\frac{1}{x^3}\right) \left(1+\frac{1}{x^4}\right) \end{equation}

Look at the terms $x^k$ where $k\geq 1$. I believe all those powers of $x$ are the capacities you can measure using the three cans.

Reasoning:

Any term of the form $1+x^a$ allows for two choices - You either fill the can of volume $a$ or you don't fill it. If we multiplied three terms and wrote $(1+x^2)(1+x^3)(1+x^4)$, this will allow you to find out how many different volumes you can measure if you are allowed to fill each can at most once and if a can once filled is never emptied.

Also, in the case of cans of size $2,3$ and $4$, it is possible to fill the 2 liter can once, empty it into the 4 liter can, fill the 2 liter can again, pour it into the 4 liter can again and fill the 2 liter can a third time. This is why we have $(1+x^2)^3$. Similarly for the 3 litre can. The 4 litre can could be emptied into the 2 and 3 liter cans combined and the refilled, so we have the term $(1+x^4)^2$ as well.

We should also allow for subtracting of volumes - This implies that terms of the form $(1+\frac{1}{x^a})$ should be present. If we look at the 2 liter can, you could fill it (and empty it) from the 4 liter can twice. Therefore, we have a term $(1+1/x^2)^2$. Similarly we get the term $(1+1/x^3)$. The 4 liter can could also be emptied once after filling it from the other two cans. Combining all of this, we get

\begin{equation} (1+x^2)^3 (1+x^3)^2(1+x^4)^2\left(1+\frac{1}{x^2}\right)^2\left(1+\frac{1}{x^3}\right) \left(1+\frac{1}{x^4}\right) \end{equation}

This idea can be extended to other values of $a,b$ and $c$. I tried it for a few other values (using Wolfram Alpha to expand the expressions) and it seems to work.

1

If gcd(a,b,c) is not 1, you can only get multiples of this gcd. You can't get more than a+b+c. I think if you play around you can convince yourself you can get any multiple of the gcd, but you would need to define the allowable activities carefully to be able to prove it.

  • 1
    And if the gcd is 1, as in the given case...?2010-10-28