The Soda Machine Puzzle

by on July 23, 2009 at 7:30 am in Uncategorized | Permalink

Here is a favorite puzzle that I learned from my father many years ago:

There are 10 machines that fill bottles of soda.  One of the machines is either always putting one ounce (of mass) too much or one ounce too little in the bottles that it produces.  You have a digital scale.  In one weighing figure out which of the 10 machines is off.

The puzzle does not involve any tricks. The bottles are opaque etc. Note you can assume that you know what the correct weight is, say 10 oz.  I will post an answer in the extension to this post tomorrow for those of you who want to sleep on this.  You can also find the answer in the comments but no peeking. 

Many excellent comments in this thread.  Nick Rowe was the first to post a correct solution.  Take one bottle from the first machine, two bottles from the second, three from the third and so forth.  If the weight on the scale is off from the expected total by say 6 oz then you know machine 6 is the culprit.  Note that this procedure will work whether the machine is putting in 1 oz too much or 1 oz too little – but not, of course, if it randomizes.  (I tried to make clear the machine was always doing one or the other but perhaps this could be worded even better.)  

In one of his books on lateral thinking, de Bono talks about the student who when asked how would you use a barometer to measure the height of a building said he would take it to the top of the building, drop it off, time it till it hit the bottom and then use Newton's laws to calculate the height.  The student's teacher was not amused but de Bono thought this was great.  In anycase, Alex J offers a similarly clever and lateral solution this puzzle which I believe also works. 

1 stephen July 23, 2009 at 7:45 am

I’ve seen this one before in a math class, should I say the answer?

2 anon July 23, 2009 at 7:48 am

Not sure what you mean by “one weighing”.

Put all the bottles on the scale one at a time and note the difference each additional bottle makes.

Alex, you need to post more.

3 Travis July 23, 2009 at 8:08 am

I heard this in terms of “chests of gold coins” where one contained coins weighing 10% more than the others. The question was can you discover which chest contains the heavier coins in the least amount of scale uses.

Of course the answer is the same, and at the time I was unable to come up with the answer.

4 Nick Rowe July 23, 2009 at 8:53 am

I thought I had the right answer. Then I realised I need to know the weight of the empty bottles, to figure out how much it all ought to weigh. Perhaps we can assume we know how much a properly-filled bottle ought to weigh. I can’t see any way around it if we don’t.

5 Lee July 23, 2009 at 9:15 am

I didn’t get it, but now that I see Nick’s answer, that looks right.

If *multiple* machines might be putting in an extra (mass) ounce of soda, I think there is a way to find the broken subset using one weighing.

Wouldn’t successive powers of two (or any number) do the trick? So take 2^(n-1) bottles from the nth machine: 1 from the 1st, 2 from the 2nd, 4 from the 3rd, 8 from the 4th, … 512 from the 10th.

In the fortunate case, none of the machines are broken and your scale says that there are 1023 times the weight of a correctly filled bottle.

In other cases, the scale registers some number of ounces in excess of that ideal weight. There may be 100 ounces more than their should be, say. In that case type 100 into your calculator, switch to binary mode, and see that it’s represented as 1100100. That means machines #3, #6, and #7 are adding in an extra ounce.

6 Milton Rhodes July 23, 2009 at 9:25 am

To limit the number of bottles on the scale, you only need to weigh one of the first, two of the second, three of the third and so on all the way to nine.

7 Rick July 23, 2009 at 9:36 am

The last answer wouldn’t quite work, but I think you’re on the right track. Because machines can be off by +1 or -1, you won’t be able to tell if machine N is -1 or if machine N is +1 and machine (N+1) is -1.

If they are supposed to fill 10 oz., and you have 2 from Machine A, 4 from B, 8 from C and 16 from D, suppose machine C only gives 9 oz. So your scale will be 8 oz. light.

But if C puts in an extra ounce, and D puts in 9 oz, then you have +8 oz. from C, but -16 oz. from D. A net result of -8, which is the same as before.

I was thinking of using primes, but that doesn’t quite work as if the 2 and 3 machine were light, and 5 was heavy, it would cancel out.

8 Tom July 23, 2009 at 9:42 am

I think we’re all making an unnecessary assumption, which is that you can only fill one bottle from each machine. It’s not about filling each bottle with a different amount of soda, but about filling a different number of bottles.

Say that you (try to ) fill all the bottles with the same amount–5 ounces. If you fill up one bottle from the first machine, two from the second, three from the third, and so forth, you’ll be able to tell by the final mass which machine was off.

9 Lee July 23, 2009 at 9:47 am

A follow-up thought on my solution for multiple broken machines: it only works if we know that broken machines *add* an extra ounce. What if some are possibly adding and others are possibly subtracting an ounce, as in Alex’s puzzle? There’s an ugly solution. You just use every other power of two, or something like that.

But that will mean weighing around a million bottles.

10 C July 23, 2009 at 9:56 am

Cool solution, Alex J.

11 Joshua Miller July 23, 2009 at 9:58 am

Actually, my answer is bollocks. Ignore it.

12 Lee July 23, 2009 at 10:17 am

Alex J.’s solution is best. And if you place the bottles carefully you could even tell if multiple machines are broken, I think. So I withdraw my million-bottle solution.

13 AS July 23, 2009 at 10:36 am

Let me try and explain my solution a little more. According to my setup(taking 1 from 1st machine, 2 from 2nd, upto 10 from 10th, but skipping the 5th bottle). Now there are are fifty bottles on the scale, therefore ideally the solution should be 50*(weight of filled bottle). Note that the deviation from the ideal weight can range from -10 to +10.

And by observing the numerical answer, we can completely determine which machine is faulty. Say the total weight is 444. Now 444= 50*9 -6, this means the 6th machine is faulty and it is underfilling the bottles. If the scale shows 507=50*10+7, then the 7th machine is faulty and is overfilling the bottle.

This way, we do not need to know the weight of empty bottle.

14 CD611 July 23, 2009 at 10:45 am

Can’t you just look at the filled bottles and see which one has more or less fluid in it?

15 Lee July 23, 2009 at 11:02 am

@Joshua Miller, I agree that in the randomized case, only Alex J’s solution will work. But if each broken machine is consistent in its under- or over-filling, then there’s gotta be a sequence you can use. I can’t intuit what the simplest sequence (powers of three?), but its easy to concoct extravagent solutions: 1 bottle from #1, 1000 from #2, A million from #3, and so on, just keep increasing the number in some crazy-giant way. Then the mapping will be one-to-one, or whatever the appropriate word is.

16 Andy July 23, 2009 at 11:15 am

You still need that the weight is integer, however. Otherwise the weight could be exactly 444/50 and all the machines could be correct (or any other possibility). So really you need to know the weight.

If you use successive powers of 3, you can tell exactly which combination of machines is broken, and whether high or low. Of course you’ll need to weigh > 60k bottles.

Example with 4 machines. Say #2 is high and #4 is low. So you stack 1 bottle from #1, 3 bottles from #2, 9 bottles from #3, and 27 bottles from #4. So 40 total. Assume each weighs 3 oz (you know the weight). So 120 oz total. Since #2 is actually 4 oz and #4 is actually 2 oz, the weight you measure is 96. In base 3 that is 10120. 120 in base 3 is 11110. So you can see that machine #2 is measuring high (because there is a 2 in the second position) and machine #4 is measuring low (because there is a 0 in the fourth position), and the others are correct.

17 Rebunga July 23, 2009 at 11:33 am

Put one bottle from each machine on the scale (10 bottles). Then take them off one at a time. The one that changes teh weight by a non-uniform amount is the bad one.

18 speaker2animals July 23, 2009 at 12:12 pm

Of course, my previous answer assumes that the faulty machine is either underfilling or overfilling all the time (not doing both randomly).

19 Yancey Ward July 23, 2009 at 1:06 pm

What isn’t clear is that the faulty machine is always over- or underfilling. If it is always one or the other, then taking 1 from 1, 2 from 2, 3 from 3, etc., and weighing the collection will show the faulty machine by a whole number discrepancy. The weight will either be x ounces low, or x ounces high. I first saw this puzzle on an old episode of Columbo in which the items were gold coins/fake coins in bags.

I have an even better puzzle. You have an old balance scale and you sell flour in whole number increments in pounds. What is the minimum number of counterweights needed to measure flour between 1 and 40 pounds?

20 Matthew July 23, 2009 at 1:18 pm

I’m with Joshua Miller’s first post on the ambiguity of the disjunct. I’m convinced that you mean that the faulty machine always overfills or always underfills. I suggest you amend that proviso and just say it always overfills by some nominal amount.

If the same faulty machine is indeed randomly under- or overfilling, there is no guaranteed solution. One could only make a good statistical guess at it at a particular confidence level, putting huge numbers from each machine, several orders of magnitude apart from machine to machine (i.e. 1 from #1, 1 million from #2, 1 trillion from #3, …). And even that approach seems limited in effectiveness if the overfill/underfill distribution is 50/50.

Is my analysis wrong on the randomly over/underfilling assumption?

21 Seth July 23, 2009 at 1:58 pm

I fail to see why the scarce resource has to be how many times you can use the scale.

22 jrp July 23, 2009 at 3:07 pm

How about this “single weighing” procedure if there’s randomized over and under filling. Place a plank with one end on the scale and the other end on a fixed point, (2) set the scale at zero (I assume this doesn’t count as a weighing), and (3) place a single bottle from each machine at evenly spaced intervals between the ends of the planks. If all bottles weighed the correct amount the scale would show 0.5 * 10 * correct bottle weight. The actual weight will be some fraction of an ounce off. If it’s 10/11 off, the closest bottle is the source of the error; 9/11 for the 2nd bottle, etc.

23 Andrew July 23, 2009 at 3:21 pm

Comments page seems broken! Thats fine I suppose

24 Wayne July 23, 2009 at 3:36 pm

Test. I can’t see any comments.

25 Mark July 23, 2009 at 3:40 pm

Unless I’m missing something, your post should be clarified to eliminate the possibility that the errant machine, while always “off,” is sometimes over and sometimes under — surely it is either always over or always underfilling its bottles.
If that assumption is correct, load the scale with a different number of bottles that were filled by each of the machines, i.e., put one bottle from machine #1, two from machine #2, etc. The rest is (I hope) obvious.

26 FRITZ July 23, 2009 at 4:15 pm

CORRECTED– Put all ten bottles (one from each machine) onto the scale at the same time. Note the weight. Take one bottle off and check the weight of the remaining nine. That gives you the weight of that bottle. Repeat this process until the change in the total weight is different from the weight of the last bottle taken off the scale. Then you can identify the bottle.

27 Walt French July 23, 2009 at 5:17 pm

Ahh, it looks like a fairly simple math problem, but in fact requires some flexibility with English and a better knowledge of math to solve.

If “[o]ne of the machines is either always putting one ounce too much or always putting one ounce too little…” then the answer is easy as above.

But what if it’s “always either putting one ounce too much or too little?” Then there can be no solution, which takes a bit more thinking to prove out. But it is claimed there IS a solution. The problem as given cannot be solved, so we take it that MR meant it to be solvable, and decide that the English was mis-written to stretch our intellects. And, you say, “no tricks,” yet another way to throw us off.

Thanks for the brain teaser!

28 Steko July 23, 2009 at 6:02 pm

If you have odd bottles (base 3 solution above) there is no problem of offsets that people keep claiming. The wrong machine is always wrong in total with odd bottles even if it sometimes over and underfills and the scale involved means there is no ambiguity between which machine is off.

Personally I would get a symmetrical plate and line up 9 bottles equly spaced at the edge. Put a marble in the middle, balance the plate on center and the marble will roll toward underfilled or away from overfilled (odd number again so no ambiguiity). If you’ve seen those old Chinese earthquake detectors you have an idea.

29 John Dewey July 23, 2009 at 6:28 pm

Yancey Ward: “I first saw this puzzle on an old episode of Columbo in which the items were gold coins/fake coins in bags.”

Same here, in the episode “The Bye-Bye Sky High-IQ Murder Case”…”. The murderer had one of the world’s highest IQ’s, and headed the Mensa-like SIGMA organization for genuises. He challenged Columbo with the gold coin puzzle. (Trivia note: A very young Jamie Lee Curtis played a waitress in that Columbo episode, which aired a year before she starred in “Halloween”.)

Columbo’s solution was the same one offerred by Nick Rove early this morning:

Nick Rove at at Jul 23, 2009 7:47:41 AM: “Take 1 bottle from the 1st machine, 2 bottles from the second, 3 bottles from the 3rd,…plus 10 bottles from the 10th machine, and weigh them all together in one batch? If it weighs 7 ounces too much (or too little), it’s machine #7.”

30 Rob July 23, 2009 at 8:04 pm

Something is wrong with this post.

If Nick’s answer is correct, then the answer is WAY TOO EASY for this audience and doesn’t warrant the “for those of you who want to sleep on this”.

Alex J.’s answer involves a trick. The post says the puzzle does not involve any tricks. Particularly if you consider the scale is said to be digital, the use of levers does not seem to be in the spirit of the “no tricks”.

Mike, I was starting to think along your lines but it doesn’t work: If machine 2 gets 3 bottles, then if 2 of those bottles are over and 1 is under you have the same weight as if machine 3 had 3 bottles over and 2 bottles under, etc. I believe there is no way to solve this problem if you assume the broken machine can be over or under at random.

31 The Incidental Economist July 23, 2009 at 8:15 pm

OK, here’s my 12 ball version from my notes: http://theincidentaleconomist.com/the-twelve-balls-problem/

32 Bob D July 24, 2009 at 12:50 am

As a follower of the Austrian School I would line up the first or last bottle produced by each machine side by side and you could clearly see without any external device or formula which machine needs to be calibrated. For people who like charts, it could be a candle or bar like!

33 Alex Tabarrok July 24, 2009 at 9:49 am

Changed to either always.

34 digitaleopard July 25, 2009 at 1:54 pm

Weigh each machine. Even if the machine is randomizing, this technique will work unless the distribution of over- and under-filling is exactly 50/50.

35 mehdi August 30, 2010 at 4:10 am

katalog for machinepuzzle

Comments on this entry are closed.

Previous post:

Next post: