Friday, June 6, 2008

A few weighing puzzles

Here are three related puzzles. I'll post answers next week and discuss how it is related to certain notions in computer science.

1) Suppose I have ten stacks of ten gold coins each. Each coin weighs 1 ounce, but there is one set of counterfeit coins. The coins in that stack weigh only .5 ounces. You have a scale. What is the minimum number of weighings to determine which stack is counterfeit?

2) Suppose instead of a scale, you only have a balance and you don't know how light the counterfeit coins are but they are too light. Then how many weighings can you do it in? What if we instead have n stacks with one counterfeit? How many weighings does it take? Can you prove that you can't do it in fewer?

3) This last generalization is due to Elissa. Suppose we again have n stacks with one set counterfeit but instead of a balance we have a k-balance which compares k different objects simultaneously and returns their mass order. So for example, if on a 4-balance I had two two ounce objects (object a and object b respectively), one ounce object (c) and one three ounce object (d), I'd be told that
c < a = b < d. The normal balance is thus a 2-balance. In general for a k-balance with n stacks what is the minimum number of weighings?


Important PointAfter I put up this issue Etienne pointed a issue I had not anticipated. In the original phrasing of 2 and 3 there was only a single counterfeit coin and one no longer had stacks. In my phrasing above I assumed that this wouldn't make a difference for the general solution. It turns out that in fact it does. So instead for 2 and 3 assume that one just has n coins with 1 counterfeit rather than n stacks. Etienne has not yet worked out the general solution with stacks nor have I, so bonus points if you can do that.

Feel free to either post or email me solutions.

No comments: