# How to find the least number of containers required to fill up a certain quantity?

I'm still stuck on this problem involving finding the least number of bottles. I am not sure whether if this problem belongs to combinatorics or maybe does it has to do with greatest common divisor or perhaps with least common multiples.

The problem is as follows:

At a dairy products plant in Neihu the technician responsible to oversee the production in the factory has been assigned to pack $$119$$ liters of yogurt, however there are only bottles from $$1,\,4,\,16$$ and $$64$$ in capacity, many of each kind. How many of these bottles can be used at least to pack the assigned litters of the yogurt if all mentioned containers must been full?

The alternatives given in my book given are:

$$\begin{array}{c} \textrm{1. 9}\\ \textrm{2. 8}\\ \textrm{3. 11}\\ \textrm{4. 7}\\ \textrm{5. 10} \end{array}$$

Initially I thought that maybe would a simple system of equations could work in this case:

So what I tried to do was to assign the same quantity of bottles per capacity to fill up the $$119$$ liters:

$$1x+4x+16x+64x=119$$

$$85x=119$$

Since the later doesn't produce an integer (it is not allowed to have half a bottle for example), then I reformulated the previous equation as:

$$4x+16x+64x=119$$

$$84x=119$$

Again this doesn't produce an integer, but I thought, the easiest would be to fill up with the least amount each of the bigger bottles and leave out the smallest one to make it up for the remaining quantity.

so it would become into:

$$84x=84$$

$$x= 1$$

Therefore $$119-84= 35\,\textrm{L remaining}$$

So I would use 35 of the 1 L capacity bottles to make it up for until completion to $$119\,L$$. So with that the least number of bottles would be, those $$\textrm{35 + 1 (of the 4) + 1 (of the 16) + 1 (of the 64) = 38 bottles}$$ But it doesn't appear in the alternatives, needless to say that this method doesn't look to be right approach for this problem.

On realizing this what I tried to do is to re think again and I thought that it might have to do with least common multiples or greatest common divisor. But this arises the problem as 119 is a prime or at least it looks like one. The only quantity closer to the common divisor being $$4$$ to $$\textrm{4, 16 and 64}$$ is $$116$$. So I decided to go on with that route.

If I were to chose the first then this would become into:

$$\begin{array}{r r r r r} & 116 & 4 & 16 & 64\\ 4 & 29 & 1 & 4 & 16 \\ \end{array}$$

But that's where I am stuck, what can I do with those numbers, $$29,\,1,\,4,\,4$$ and $$12$$.

Then I thought to use least common multiples:

$$\begin{array}{r r r r r} & 116 & 4 & 16 & 64\\ 2 & 58 & 2 & 8 & 32 \\ 2 & 29 & 1 & 4 & 16 \\ 2 & 29 & 1 & 2 & 8 \\ 2 & 29 & 1 & 1 & 4 \\ 2 & 29 & 1 & 1 & 2 \\ 2 & 29 & 1 & 1 & 1 \\ \end{array}$$

And I'm left with $$2^{6}\, 29$$ but again don't know what can or should do with these numbers.

That's where I'm still stuck. Can somebody help me to find an easy method to solve this kind of riddle?. I could try to plug in numbers randomly each trial but this would consume time and I don't believe that would be the right approach for this situation. There is also the fact that I'm confused at trying to understand from the passage that there are many bottles of each kind. I assume that if its at the technician's availability then maybe the intended question is to find a number of bottles to fill up 119 liters using at least each of the assigned capacities but the least number of them. That's the tricky part because if this is the intended question, how am I supposed to find that number?. I tried all what mind could come up with at this point but I can't imagine any other methods.

Needless to say I'm not yet able to solve this problem by myself. Help would be much appreciated. An answer which would help me the most is one which could be very detailed in steps so I could catch on what's going on and that similar strategy could be used in similar problems.

You just have to use the bigger one until I can't no more : $$119- 1\times64=55$$.

Then 54 left, I use, the 16 until I can't : $$55 - 3\times 16 = 7$$

The remaining is trivial: $$7= 1\times4 + 3\times1$$

So it's : $$1 \times 64 + 3 \times 16 + 1\times 4 + 3 \times 1 = 119$$ and I get; $$1+3+1+3 = 8$$ bottles

I mean, why would I use the bottle of 4 4-times, when I can just use a bigger one ( the 16) once. So the reasoning is simple, use the bigger one until you can't. This is going to always work.

• It would improve your Answer to give an argument why no smaller number of containers will work. This may be intuitively clear, but articulating a proof would be the kind of good content we are striving to collect. Commented Feb 11, 2019 at 17:30
• The more of the larger containers you can use, the smaller number of total containers you will need. For a proof, you might look into the floor or mod functions to identify remainders as you descend in size from the largest to the smallest. As with the answer above, the remainder from each feeds the next smaller size. Commented Feb 11, 2019 at 18:20
• @M. Di That's an interesting and pretty simple approach to understand buddy. Using the biggest until it cannot be would minimize the number of uses by last trial, this greatly reduces the need to be guessing. However I believe your answer can be improved if you would use a bit mathjax to the sentence indicating the number of times each bottle is used. Commented Feb 12, 2019 at 16:56
• @M. Di In other words to be shown as $1\times 64 + 3\times 16 + 1\times 4 + 3\times 1$ so $1+3+1+3=8$ so the least ammount of bottles would be $8$ by going your approach. Do I understand this part right?. As for the proofs, I'm okay without one for the moment. Commented Feb 12, 2019 at 16:56
• Yes you understand. It's 8 Commented Feb 12, 2019 at 17:04