More Barrels and More Pellets - Solution

by
Erik Oosterwal



In the first part of the problem we only had to find the one barrel with the heavier pellets, but this time there can be anywhere from 0 to 10 barrels with pellets of the wrong size; to solve it we have to rely on binary arithmetic.

In 'normal' arithmetic, or decimal arithmetic each digit represents some value in a power of 10.  The rightmost digit represents values of 1-9, the next digit represents values from 10-90, the next one over represents values from 100-900, and so on.  In binary arithmetic each digit represents some value in a power of 2, so the first, rightmost digit represents 0 or 1, the next one over to the left represents 2 or 3, the third one represents numbers from 4-7, the next one over represents numbers from 8-15, then 16-31, and so on.  Use the table below as a handy reference:

Barrel number:     1     2     3     4     5     6     7      8      9     10
Power of 2:    20    21    22    23    24    25    26     27     28     29
Decimal equivalent:     1     2     4     8    16    32    64    128    256    512


Now we can solve the problem:  Take 1 pellet out of barrel 1, take 2 pellets out of barrel 2, take 4 pellets out of barrel 3, take 8 pellets out of barrel 4, and so on until you take 512 pellets out of barrel 10, and place them all on the scale.  At this point you have 1023 pellets in a pile on the scale.  If all the pellets weighed exactly 1 gram the scale would show the expected value of 1.023Kg--in this case you could claim that no barrels contained pellets that weighed 2 grams.

If the first barrel contained 2 gram pellets, the resulting weight would be 1 gram more than expected and we would subtract the expected weight of 1023g from the actual weight of 1024g leaving just 1g and we could say that barrel number 1 had the 2g pellets.  If barrel number 9 had the 2 gram pellets, the total weight would be 1279g.  After we subtract the expected 1023g from our result we end up with 256g and we conclude that barrel number 9 had the 2g pellets.

If there were multiple barrels with 2g pellets, after we subtract our expected 1023g from the total we would end up with some number that doesn't show up on the chart above.  In that case we would have to repeatedly subtract one of the numbers from the bottom line of the chart until we find every barrel with 2g pellets.  For instance, if our total weight was 1169g, then after subtracting the 1023g expected weight we end up with 146g.  !46 doesn't show up on the bottom line of the chart, so we find the largest number on the chart that is less than or equal to our number.  In this case 128 is the largest number that is still less than 146, so we mark barrel number 8 as having 2g pellets, subtract 128 from our 146 and find we're still 18g over our expected.  Again we find the largest number on the bottom line that is less than or equal to our result, in this case 16, mark that barrel (#5) as having 2g pellets and subtract 16g from our 18g weight which leaves us with 2g over weight.  One last time we look at the chart to find the largest number that is less than or equal to our resulting 2 and find that the number 2 is associated with barrel number 2.  We mark barrel number 2 as having 2g pellets and subtract 22 from the 2g over weight and end up with 0.  When we end up with 0 we know we've marked all the barrels with 2g pellets.

Phew, that's a lot of work!  I think it would have been easier just to weigh 1 pellet from each barrel when nobody was looking...

All original puzzles and solutions are © Erik Oosterwal 1993-2008

See all the brain teasers on The Puzzle Page.

Get daily puzzles in your RSS reader at The Puzzle Page Blog Site.

Looking for answers to computer programming problems?
Read what's going on in the Computer Science 101 classroom.