Associated Topics || Dr. Math Home || Search Dr. Math

### Counting Possible Combinations of Weights

```Date: 10/07/2004 at 20:09:18
From: Sean
Subject: Number of possible combinations of weights

Dear Dr. Math -

If you have a set of weights, in sizes 50g, 25g, 15g, and 5g, how
would you go about determining how many possible combinations of
weights you could make to equal 85g?  I am trying to help my daughter
with her homework, and must confess to being a bit stumped.  Help,

We started out by listing all combinations of 5g weights with one
other size of weight, and once we got through that, we moved up a size
and repeated the process, but soon realized that there were many more
combinations than we were going to be able to write out in a practical
amount of time.

```

```
Date: 10/07/2004 at 22:33:30
From: Doctor Greenie
Subject: Re: Number of possible combinations of weights

Hello, Sean.

This problem is made easier by the fact that it asks you to determine
how many ways there are rather than asking to list all the possible ways.

In my mind, there are two keys to finding the answer to this question
efficiently.

(1)  We will use a "greedy" algorithm - that is, we will use the
largest number of largest weights possible at every stage.

(2) Note that, if we have a solution involving one or more 15g
weights, we can always replace each of the 15g weights with three 5g
weights to get a different solution.  The effect of this is that we
only need to consider the 50g, 25g, and 15g weights to find the

We use the greedy algorithm to start our search--we use as many of the
50g weights as possible.  We can only use at most one; two 50g weights
is more than the 85g total we want.  So the number of 50g weights is
either 1 or 0; according to the greedy algorithm, we examine the cases
with one 50g weight first.

With one 50g weight, we need another 35g to make our target of 85g.
Using an analysis similar to the preceding analysis, if we have one
50g weight then the number of 25g weights we can have is either 1 or
0.

Again, using the greedy algorithm, we consider the case of one 50g
and one 25g weight first.  With this combination, we have 75g, so we
need 10g more.  That means we can't use any 15g weights; the remaining
weight must be made using 5g weights.

We begin a table summarizing our results....

column A: numbers of 50g and 25g weights
column B: possible numbers of 15g weights with this combination
of 50g and 25g weights
column C: number of different solutions with this combination
of 50g and 25g weights

A        B    C
---------------------
(1;1)      0    1

We have completed the analysis for the case where we have one each of
the 50g and 25g weights; according to our greedy algorithm, we next
analyze the case with one 50g weight and no 25g weights.

With one 50g weight and no 25g weights, we need 35g more.  We can use
as many as two 15g weights.  According to (2) above, that means we can
use either 2, 1, or 0 15g weights, with whatever remains being made up
of 5g weights.

So now our summary table looks like this:

A        B    C
---------------------
(1;1)      0    1
(1;0)     0-2   3

According to our greedy algorithm, we have determined all the ways of
making the 85g total using at least one 50g weight, so now we begin
considering cases where the largest weights we use are the 25g
weights.  With a desired total of 85g, we can use up to three 25g
weights; so we are going to consider cases where we have 3, 2, 1, or
0 25g weights.  This analysis will finish our problem.

-- no 50g weights; three 25g weights

We have only 10g left; the number of 15g weights must be 0

-- no 50g weights; two 25g weights

We have 35g left; the number of 15g weights can be 2, 1, or 0

-- no 50g weights; one 25g weight

We have 60g left; the number of 15g weights can be 4, 3, 2, 1, or 0

-- no 50g weights; no 25g weights

We have the entire 85g left; the number of 15g weights can be 5, 4,
3, 2, 1, or 0

And we can now finish our table and find the final answer to the
problem:

A        B    C
--------------------
(1;1)      0    1
(1;0)     0-2   3
(0;3)      0    1
(0,2)     0-2   3
(0;1)     0-4   5
(0;0)     0-5   6
--------------------
total # of ways: 19

I hope this helps.  Please write back if you have any further

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 10/08/2004 at 10:59:43
From: Sean
Subject: Thank you (Number of possible combinations of weights)

Thanks Dr. Greenie!!  You rock :)  We finally did go through all the
combinations, and wound up with 19 as well.  Interestingly enough, if
we divide each weight size by 5, the smallest weight, and add the
resultants, they equal 19.  Coincidental to be sure, but still quirky.
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search