“I have made the most important discovery of my career, the most important discovery of my life: It is only in the mysterious equations of love that any logic or reason can be found.” -John Forbes Nash, Jr.
Yet logic and reason -- when applied correctly -- can get us incredibly far. Have a listen to Supertramp singing their unique hit,
while you consider the islander problem from TV's Brooklyn Nine-Nine.
Image credit: E. Siegel.
“There are 12 men on an island. 11 weigh exactly the same amount, but one of them is slightly lighter or heavier. You must figure out which. The island has no escapes, but there is a see-saw. The exciting catch? You can only use it three times.”
This is possible to solve, although no one got it on the show.
Image credit: Fox / Fremulon.
What's the solution? How about all possible solutions, worked out for your consideration this weekend at Starts With A Bang!
- Log in to post comments
More like this
6 vs 6 gets you the group of 6 where the heavier person is in.
weighing that group into 3 vs 3 gets you the group of three where the heavier person is.
from those 3, you weigh one vs one, if they are equal in weight the last remaining one is the heavier of the 12.
three times weighing, and no silly 4 v 4 weighings.
4+4 gives you a chance to find out in the first test.
The logic is a little sideways, but it IS the most efficient method. Yours you have to do at least two weighings.
Oh, and isn't the problem with this one that you don't know whether the odd one out is heavier or lighter?
So you need another weighing to sort out if the odd one out is in the lighter group or the heavier one in your scheme.
What I like about this problem is that it parallels, in an accessible way, the kind of thought processes needed to design a particle physics experiment.
You have known particles (the 11 people) and an unknown particle (the lighter/heavier person). You know some things about the 'known' particles (observed branching fractions, masses, etc.) and you have theory(ies) about the unknown particle.
You have a see-saw (particle detectors) capable of measuring some properties of groups of particles and you have a limit on how often you can use the see-saw (accelerator luminosity and time).
Only instead of one variable to measure, you have many and you can't observe the outcome of any single test (particle interaction) alone, only the outcome of a series of tests (a particle decay cascade). What's more, the outcome of a give test is random, only following a certain probability distribution and not a definite result.
Now that is a puzzle to solve.
Here's my answer:
Split into 3 groups A, B, C of 4 each.
First weigh A vs B.
If A=B, weigh C1, C2 vs A1, A2.
If C1, C2 = A1, A2, then C3 or C4 is odd one.
In general, if you know the odd one is one of two people, you can find which is the odd one by weighing one of the two people vs. a person you know isn't the odd one.
If C1, C2 > A1, A2, then C1 or C2 is odd one.
Suppose A > B.
Weigh A1, A2, B1, B2 vs C1, C2, A3, B3.
If A1, A2, B1, B2 = C1, C2, A3, B3, then A4 or B4 is odd one.
If A1, A2, B1, B2 > C1, C2, A3, B3, then A1 or A2 is odd heavy one, or B3 is odd light one.
Weigh A1, B3 vs C1, C2. If A1, B3 = C1, C2, then A2 is odd one.
If A1, B3 > C1, C2, then A1 is odd one.
If A1, B3 < C1, C2, then B3 is odd one.
Similarly if A1, A2, B1, B2 < C1, C2, A3, B3.
Bpteh,
One problem with your solution is that the problem specifies that you must determine whether the odd one is heavier or lighter than the others. In your first case, group C contains the odd member. You are weighing two members of group C against two non-odd individuals. If C1 or C2 is the odd one, there's no problem. Either C1+C2>A1+A2 or C1+C2<A1+A2, so you know whether the odd one is heavy or light. However, if C3 or C4 is the odd one, you have no way of knowing if they are heavy or light. If C3 is odd, and you weigh him against a normal, no problem. However, if C4 is odd, and you weighed C3 vs a normal on your last weighing, you know that C4 is odd, but you don't know if he's light or heavy. C4 has never been on the scale on any of the three weighings, so you have no information about his weight.
Your weighings:
1. Group A vs Group B
2. C1 + C2 vs A1 + A2
3. C3 vs A3
If C4 is the odd one, all of these would be in balance.
Sorry Bpeth, apparently I'm having a bit of dyslexia with your name, which I spelled incorrectly above. :)
Bassos,
Yes, Wow is right. Your solution is invalid. If you weigh 6 vs. 6, one side will indeed be heavier, but you have no way of knowing if the person with the different weight is on that side or on the light side. Your remaining two weights could well balance and therefore indicate that the odd person was lighter than the others and was in the group of 6 on the light side of the original weighing.
@Sean T,
The problem didn't ask you to determine if the odd one is heavy or light.
It only asks you to determine which one is odd.
It depends on how you interpret the question.
But I looked at Ethan's solution, and it did determine whether the odd one is heavy or light.
"There are 12 men on an island. 11 weigh exactly the same amount, but one of them is slightly lighter or heavier. You must figure out which. The island has no escapes, but there is a see-saw. The exciting catch? You can only use it three times."
I can see your point. From the quoted problem above, it seems that we are only to determine the identity of the odd person, not whether he's heavy or light. I was assuming that a valid solution must make this determination because Ethan's solution does indeed do so. However, upon reading this statement of the problem, I think your solution is indeed valid.
Note that the solution Bassos gives above with an initial 6 vs 6 weighing is still invalid. It assumes that the odd person lies in the heavy group of 6, but that need not be true. The odd person could be light, so that solution could fail to correctly determine the odd person.
Ah, not necessarily.
"which" which do they say?
Certainly which man is different fits.
But so does the more complete "which man is which state". It isn't wrong to get either of those as what is being asked.
Or, "which" could mean, is the odd one heavy or light?
Looking online, I found one person who did interpret it that way.
That's the easy interpretation - you only have to differentiate between 2 possibilities with 3 weighings - actually, only 2 weighings are needed.
The medium interpretation is the one I had - differentiate between 12 possibilities with 3 weighings.
The hard interpretation is Ethan's - differentiate between 24 possibilities with 3 weighings.
I got the puzzle by looking at the page source, figuring Ethan had mistakenly hidden the puzzle with the image. I didn't want to look at his answer.
But maybe he wanted people to click on his link and read his interpretation of the puzzle.
Same question, except with 90 instead of 12:
You have 90 coins, and they are all the same weight except for one of them, which is either lighter or heavier than the rest.
You have a balance scale, the kind with two dishes hanging from either end of a rod that is supported in the middle.
Using just the balance scale and the 90 coins, what is the smallest number of weighings in which you can be sure to figure out which is the odd coin, and whether it's lighter or heavier?
One thing I like about this puzzle is that you can have a bit of information shared between two "particles", e.g. a weighing might tell you that either A is heavy or B is light.
It's like quantum entanglement.
I realized that for k weighings, k >2, the max number of coins for which you can answer the question "which coin is the odd one and is it light or heavy" is (3^k -3) / 2.
Thus for k = 2, 3 coins;
For k = 3, 12 coins;
For k = 4, 39 coins;
For k = 5, 120 coins.
And the maximum can actually be achieved with an algorithm where the weighings are predetermined.