[philbarr]

Not really - you can reduce it to one but you don't quite have enough information.

So I think it goes like this:

- you have 12 coins, and each one has an equal chance of being heavier or lighter than the others - so that's 24 possiblities

- you have 3 moves, and the result of each move could be one side of the beam goes down, one side goes up, or it balances. That means you can create a system that identifies 3^3 = 27 outcomes. So far so good.

- you need each of your outcomes to provide real information. if it was a binary problem that means you're not really getting any information if the beam balances

(bit sketchy on that last point, maybe someone can help with that)

[catpolice]

Yeah, the reason I suspect it tends to thwart programmers (if I recall correctly) is that there's a solution that looks a lot like binary search that _almost_ works, but the actual solution looks very different from it at every step. So the programmer will start with the one that looks like binary search, realize that it provides almost enough information, and try to squeeze a little more out of it by modifying it in little ways, when they sort of need to go back to the drawing board instead.

[wvlia5]

"that means you're not really getting any information if the beam balances"

Wrong. If it was true, that would imply that the probability of it balancing is 1, since the information you get is -log2(probability). Obviously the probability of it balancing is lower than 1, so you do get information.

[catpolice]

You don't get any information if the probability of the beam balancing is either 1 or 0. If you put everyone on the scale, the probability that it will be balanced is 0 - you don't learn anything. So the trick is to exclude some of the sample group in every measurement. You can use a binary search strategy where you divide the coins into "on the scale" and "not on the scale" groups, until you have a set of two that definitely contains the one you're searching for (and then one more measurement will tell you which one of those two it is) - but that strategy requires too many measurements, so you need to use more information at each stage, and you can't throw out coins you've determined to be non-counterfeit.