Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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, 
please!

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 
answer to the problem.

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 
questions about any of this.

- 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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/