Misleading picture
When I weighed the kitten above I used a pan balance. I remember that the kitten weighed 2009 grams. I had an unlimited supply of 1 gram weights, 10 gram weights, 100 gram weights, and 1000 gram weights. What I don’t remember is in how many ways I selected the weights to balance the kitten. I tried every possibility, but I don’t remember how many there were.
Problem source: Mathematical problems, University of British Columbia.
June 23rd, 2009 at 10:30 am
First, it doesn’t matter if it is 2000 or 2009. They have an equal number of solutions; one can get the 2009 solutions by adding 9 1 gram weights to the 2000 solutions and vice versa.
To find the number of ways to balance a 2000g cat, I’ll first assume that we have only 1000g and 100g weights. One can use 2 1000g weights, 1 1000g weight and 10 100g weights, or 20 100g weights. Let me abbreviate those as (2,0), (1,10), and (0,20)
Now, lets add the 10g weights. We have the above 3 ways, plus an additional 30 ways derived by replacing 100g weights with 10 10g weights each. There are 33 ways to weigh a 2000g cat with 10g, 100g, and 1000g weights;
3 have no 10g weights (2,0,0), (1,10,0), (0,20,0)
2 have 10 10g weights (1,9,10), (0,19,10)
2 have 20 10g weights (1,8,20), (0,18,20)
2 have 30 10g weights (1,7,30), (0,17,30)
…
2 have 100 10g weights (1,0,100), (0,10,100)
1 has 110 10g weights (0,9,110)
1 has 120 10g weights (0,9,110)
…
1 has 190 10g weights (0,1,190)
1 has 200 10g weights (0,0,200)
When we add the 1g weights, we add 10 unique ways to balance the cat for each 10g weight in the above listing; or
10 * sum (1+2+…20) +
10 * sum (1+2+…10)
= 550 + 2100
So there are 2683 total ways to balance a 2009 g cat with 1g, 10g, 100g, and 1000g weights.
There must be a slick formula for this in the form of ax**3 + bx**2 + cx + d.