At Nails, Inc., there is a wide selection of nails. The nails are indistinguishable except for their weights.
This afternoon, you received 4 boxes full of nails. They were labeled A, B, C, and D. You were told that two of the labels were switched on accident and that you must find out which ones.
You have several scales with which you can weigh nails against each other. The people here are picky about efficiency, and you'd like to do all the weighings at once, using as few scales as possible. This means you can't change your weighing strategy according to the results of the first weighing.
What is the smallest number of scales needed to figure out which nails were switched if:
- You know that the order from lightest to heaviest is A, B, C, then D, or
- You know that an A nail is 1.9 g, B is 2.0 g, C is 2.1 g, D is 2.2 g.
Prove that it is the fewest number of scales needed.
There are C(4,2)=6 possible pairs that could have been switched.
In case 1, where you don't know if the weights are evenly spaced, there's no way to expect an equal balance on any given scale, so each scale provides at most one bit of information (left side heavy or right side heavy). Two such scales would allow for only four possibilities, while three scales allow 2^3=8 possibilities--enough to cover the 6 possible results we might find.
If on one scale we weigh a nail from box A against one from box B, and on a second scale one from box C vs one from box D and on a third scale, one from box B against one from box C, we can get the following table of results (the columns representing which boxes were switched):
A-B A-C A-D B-C B-D C-D
A v B / / / \ \ \
C v D \ \ / \ / \
B v C \ / \ / / \
where / indicates the left side is heavy and indicates the right side is heavy. Each switched pair has a unique combination of results on the three scales.
In case 2, since the weights are evenly spaced we can arrange that in some instances there could be an equal weighing between two sides of a scale with different items on them. So each scale has three possible results, and two scales give us nine possible sets of results, so that should be enough if we set them out right.
Trying various possibilities, this time representing an equal balanced scale as -, we get the following table (not that we'll use all the rows):
A-B A-C A-D B-C B-D C-D
A+C v B+B / \ / \ \ /
B v D \ \ / \ / \
A+C v B+D - \ / \ \ -
A+D v B+C / / - - \ \
The bottom row, combined with either the top row or the third row, will uniquely identify which pair of boxes has been switched.
So weigh A+D against B+C, and weigh A+C against two B's. That will work.
Or weigh A+D against B+C, and weigh A+C against B+D. That would also work.
Either way for case 2 it's two scales.
Edited on July 6, 2004, 1:47 pm
|
|
Posted by Charlie
on 2004-07-06 13:42:00 |
solution
