Reply
Sat 6 Dec, 2003 11:15 am
You must all know the problem of the twelve objects, all but one of which are the same weight. It is unknown which is the odd one and whether it is light or heavy. You are allowed three weighings. Well . . .
My boss gives me a box containing a number of packages. He says, "One of the packages in this box is the wrong weight. Go over to the balances and measure them against this good one. I need to know which one is wrong and whether it is too light or too heavy"
So I go over to the balances and the guy there says. "We have folks waiting to use these so I can only allow you three weighings".
"Corny. Everyone knows that one" I think, and empty the box onto the table.
But there are THIRTEEN packages in the box, not twelve. Obviously my boss has not read the script!
So how do I still find out what the boss wants given three weighings?
1 to 13 are the unknowns. 14 is the one you know is right.
1,2,3,4,9 vs 5,6,7,8,14
1,2,5,6,9 vs 3,10,11,13,14
1,6,7,13,14 vs 2,5,8,11,12
I "think" that's the only way to get 9,9,9 options.
Adrian
Interesting and impressive! Not the solution I had in mind so clearly there are at least two. (I'm not too sure what you mean by a '9,9,9' solution so mayber my solution is not one of those, but it is none-the-less a solution) Do you want me to tell you my solution or do you want to work on it?
It is transparent that with five on each side of the balance at the first weighing, if it balances then this is no different from the 'twelve' puzzle and that outcome can be taken as solved.
Mungo
What I mean by 9,9,9 is that after the first weighing you need to have the 27 overall possibilties grouped into 3 groups of 9. I can't work another solution out just yet. It must still involve grouping into 5's each time, no?
It looks like you need to switch out a 2 for a 12 there...I think.
Adrian
I see what you mean by '9,9,9,' now. My solution does require that the first two weighings have five on each side but the third requires one on each side.
I agree that there are twenty-seven discriminations possible with three weighings but there are two unknowns for every object so the number of unknowns must be ther number of objects times two. (Well, three unknowns per object to be correct - too heavy, too light, or correct weight - but only one of these can be true for any object so two per object must be false)
It was this that told me there had to be a solution for thirteen objects somewhere - thirteen times two being less than three to the power of three!
By the same token, no solution should be possible for fourteen objects.
Zex
I don't think so, you can have 2 = LLR and 14 = RRL because you know that 14 is good. I'm not a fan of maths so I might be wrong though.
Mungo
Your right, 13 balls is the limit and even then you can only tell whether it's heavier or lighter by having the 14th ball you know is good. If your last weighing is only 1 ball on each side then you must have calculated which balls to weigh each time based on the previous weighing. I can't work out a way of doing that yet. I just made a chart up of all the possibilities then stuffed around filling in the blanks until it looked right. (As I said above I'm not real hot on maths.)
Adrian
You said, "I haven't worked out a way of doing that yet!"
I take it from the "yet" that you haven't given up on it so I'm saying nothing, but any queries, just ask.
I doubt whether this can still be done in 3 weighings except by relaxing the condition of knowing whether the odd one was light or heavy.
If you proceed as for 12 with a 4-4 split, then an imbalance is handled in the traditional way, but a balance leaves the problem of identifying 1 from 5 with only 2 weighings. This can be done as far as eliminating 4 using the standard , however, this identifies the last one as the target, but unweighed.
Fresco
The key is that the boss said, "measure them against this good one" which clearly iimplies that you do have a fourteenth that is known to be good.
Only if the first weighing has the good one and four 'unknowns' in one pan and five unknowns in the other, with four not being weighed, can the required answer be found. Adrian (above) did precisely this.
The 'catch' is that with twelve you can put four to one side and divide the remaining eight evenly between the pans. With thirteen, the one known to be good allows us to divide nine between two pans.
Mungo
OK, Take me through it from a
1 2 3 4 5 vs 6 7 8 9 14 imbalance (14=good)
If the 14 pan goes down I know either 12345 is light or 6789 is heavy. Now what ?
EDIT
Ah I may have it.
1 2 7 vs 6 3 4 gives 3 "changed pans", 3 "same pan" and 3 "removed", each 3 consisting of a pair from a H/L side plus 1 from the other side.
and depending on the swing the last weighing is to split the particular pair one vs one ?
fresco
Just like the 'twelve' problem there is more than one answer, but that first move is invariable.
If the second weighing leaves you with three and you know that one of the three is, say, light, then weighing one of the three against another of the three gives you the answer. Or if it left you, as the first solution that I found did, knowing that one of two was light or a third was heavy, weighing the two light ones against the other would give you it.
It seems that the items of 'false information' have to be reduced to nine or less by the first weighing and three or less by the second. - but you don't really need me to tell you all of this, right? :-)
Error.
That should have read, "Weighing the two light ones ONE against the other"
Stumble It!
Tweet This
Bookmark on Delicious
Share on Facebook
Share on MySpace