Hacker News Reader

Comment by TrinaryWorksToo | Hacker News Reader

Is it not a binary search problem?

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)

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.

"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.

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.

No, it is a ternary search problem.

EDIT: According to

> https://en.wikipedia.org/w/index.php?title=Balance_puzzle&ol...

if you know that one coin is different from the others, with 3 weighings, you can even detect it among 13 coins (not just 12).

I don't want to give too much away but consider that if you start by weighing 6 coins against the other 6, you already know what's going to happen.

Wrong. You don't know which side will be heavier

Nope. It's ternary in nature. The subproblem of "You have 3 coins, one of which is lighter than the others. On a balanced scale, figure out which one is lighter in one weighing." is a good place to start. Just enumerate all 3 possible weighings and you should be able to see the correct approach.

How do you solve this?

ABC, one of them is different weight than the other two (either more or less)

Possible ways to weigh them:

  A v B
  A not enough information
  E C is odd one out
  B not enough information

  A v C
  A not enough information
  E B is odd one out
  C not enough information

  B v C
  B not enough information
  E A is odd one out
  C not enough information

  AB v C
  AB not enough information
  E C is odd one out
  C C is odd one out

  AC v B
  AC not enough information
  E B is odd one out
  B B is odd one out

  BC v A
  BC not enough information
  E A is odd one out
  A A is odd one out

In all possible ways to weight 3 coins, all have uncertainty which means you cannot deduce which is the odd one out.

Your OP stated one is lighter, not one is different.

It's easier than the 12-coin one different puzzle, but introduces the ternary concept well enough to get you started on the harder problem (there are some other complications to it as well).

Weigh 2 coins. If the scales move you've found the lighter coin. If the scales balance, it's the third coin you didn't weigh.

Ah I got the original (12 coins, one is lighter or heavier) mixed up with 3 coins (one is lighter).

Label each coin, divide in three stacks each time, and shuffle meaningfully each time the subsets, to remove uncertainty.

Pretend you only had 3 coins. The idea is -- when you use the scale to measure 2 coins against each other -- you actually gain "information" about all three coins.

This is because there are 3 possible scenarios:

1. the biased coin is on the right side of the scale,

2. the biased coin is on the left side of the scale,

3. or the biased coin is the coin not measured (since the scale is balanced).

In essence, even though this scale only has 2 sides, you gain information proportional to having 3 sides.

Hence if we were to extend this to a scenario where you had n coins, of which one was biased and others fair, you would only need log_3 n measurements total to find the biased coin.

This idea has pretty neat applications. For example, if you wanted to prove that merge sort has a O(n log n) computational complexity, you can use this scale idea.

Traditionally binary search involves recursively dividing the options into two roughly equal sized groups and then using a measurement to rule out every member of one of the groups (and thus half of the search space) with every step. The solution to this problem differs from that approach in certain key ways.

It is a kind of search problem, but the steps aren't recursive and you have to use several tricks to maximize the information you get out of each measurement.

Reply on news.ycombinator.com