It can be done, I think, with fourteen provided you also bring in a fifteenth whose weight is the same as the thirteen others.
I have seen the puzzle presented as coins on a scale, and the counterfeit coin among fourteen can be determined in three weighings provided you sneak in a fifteenth good coin.
You use the seesaw as a makeshift catapult to throw any food off of the island. Then you wait for them to starve. If 11 of them die, then the 12th was the other weight, and weighs more. If only one dies, he was the other weight, and he weighed less.
One should always properly cite one’s sources.
You make a small weighing scale, 12 coins that weigh the same and 1 that has a different weight. Then you tell the people on the island that you will not let them off, until they figure out how to identify the different one with at most three uses of the scale.
Perhaps you can find the odd-coin-out that way, but if so, you certainly won’t be able to tell whether it’s heavy or light in all cases. Three weighings gives you three trits of information, enough to distinguish between 27 different cases. Fourteen unknown coins, one of which is either heavy or light, gives you 28 different cases to distinguish between.
13 unknown coins with one either heavier or lighter is only 26 cases, so the simple count-of-information argument doesn’t exclude it, but it does turn out to be excluded by a more sophisticated analysis, at least if you don’t have any other known coins. Adding a known coin might be enough there, though: I haven’t worked through that one.
It seems to me that if you add a known coin with 13 unknowns, you can not only determine the counterfeit coin in three weighings, but you can also always determine for certain whether that false coin is heavier or lighter than normal. With 14 coins (and a known good coin), it can only be guaranteed that the false coin will be found in three weighings. It may not be possible to always determine whether that false coin is actually heavier or lighter.
However, knowing whether the false coin is heavier or lighter is not usually part of the puzzle. Just identifying it is all that matters.
The show gave an official answer which was the same as those given here.
The problem with heavier or lighter is you do not know which side of the imbalance you want. Do you want the side that goes farther down? Or the side that goes farther up?
Yes, and usually you’ll end up learning that as well. But there are situations where you can find the odd coin out without knowing whether it’s heavy or light. For example, if you have thirteen coins and weigh 1-6 vs. 7-12 and they balance, then you know that coin 13 is the odd one out.
There’s also a solution if you have to determine in advance what the weighings will be. Most solutions let you base the second weighing on the results of the first, and the third on the results of the second.
If the persons are identified as A through L:
First, weigh A,B,K,L against C,D,I,J
Second, weigh A,D,H,L against C,E,F,K
Third, weigh C,F,H,L against B,G,I,K
Depending on the three results, you can determine which one is “off”, and whether he is heavier or lighter than the others
Also, most solutions also allow for the possibility that all 12 weigh the same, but that never seems to be a possibility in the stated problem.
The way I like to think of this is in terms of the solution space: you have 24 different possibilities; each of the 12 (men) could be heavy, or light.
Your test tool can give you three different responses (heavier on the left, heavier on the right, or balanced.) Since you can use it three times, you could theoretically sort out 3^3 or 27 different possibilities, so you have a little wiggle room.
For your first weighing, you need to make sure that you don’t have more than 9 possibilities out of each possible result. Weighing 4 against four does that; if 1-4 are heavier than 5-8, then you’re down to 1H, 2H, 3H, 4H, 5L, 6L, 7L, or 8L. If they balance, they you’re down to 9H, 9L, 10H, 10L, 11H, 11L, 12H, or 12L. And so on.
Seems to me that you can do it for 13. You start with a 4-4 balance. If they’re unequal, you use the algorithm that Bricker described.
If they’re balanced, then you compare 3 (of the remaining 5) against 3 of the “known good” people. If:
They balance: One of the remaining two is it. Test one of them against a reference. Either they balance and it’s the last unweighed guy, or they’re unbalanced and it’s him.
They’re heavier: Then the odd man is also heavier, and it’s one of those three. Test a pair of the remaining 3; either one is heavier and it’s him, or they balance and it must be the last guy.
They’re lighter: Same as above, swapping heavier for lighter.
It’s true that you don’t always find out whether the odd man is heavier or lighter.
It seems to me that if all you are trying to determine is whether the odd man out is heavier or lighter (which isn’t the question, but it’s still an interesting one) you only need two uses of the scale.
Weigh six v six. One side will be heavier. One will be lighter. Weigh the heavier side three v three. If they weigh the same, the odd man is on the side that was lighter (because all six of the heavier side are the same) which means that he is lighter than everyone else. If the heavier three v three does not weigh the same, you know that the odd man out was on the heavier side, because he’s still tipping the scale in the three v three. So he’s heavier than the rest.
That this is so easy tells me that the problem is about discovering the odd man out and not about just determining whether he’s lighter or heavier than the rest. That and all of the references to the coins y’all posted above.
The definitive solution to the whole class of problems of this sort, by Marcel Kołodziejczyk.
I had six on each end, then have them get off one each side. When the seesaw balances, one of those two is Mr Odd. Pick one of them and weigh against a normal, he’s either lighter or heavier. If he ain’t, it’s the other bloke.
Then, if the problem requires light or heavy not just oddity, you’ll have to weigh him against a normal too.