6 ms·

Is it not a binary search problem?

cecilpl2 8y ago
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.
- deleted 8y ago
  [deleted]
- wvlia5 8y ago
  Wrong. You don't know which side will be heavier
wolfgke 8y ago
No, it is a ternary search problem. EDIT: According to > https://en.wikipedia.org/w/index.php?title=Balance_puzzle&oldid=846801179 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).
phamilton 8y ago
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.
- emilfihlman 8y ago
  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.
  - scrooched_moose 8y ago
    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.
    - emilfihlman 8y ago
      Ah I got the original (12 coins, one is lighter or heavier) mixed up with 3 coins (one is lighter).
  - deleted 8y ago
    [deleted]
  - grive 8y ago
    Label each coin, divide in three stacks each time, and shuffle meaningfully each time the subsets, to remove uncertainty.
philbarr 8y ago
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 8y ago
  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 8y ago
  "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 8y ago
    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.
catpolice 8y ago
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.
deleted 8y ago
[deleted]
QML 8y ago
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.

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.

deleted 8y ago
[deleted]
wvlia5 8y ago
Wrong. You don't know which side will be heavier

wolfgke 8y ago

No, it is a ternary search problem. EDIT: According to > https://en.wikipedia.org/w/index.php?title=Balance_puzzle&oldid=846801179 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).

phamilton 8y ago

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.

emilfihlman 8y ago
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.
- scrooched_moose 8y ago
  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.
  - emilfihlman 8y ago
    Ah I got the original (12 coins, one is lighter or heavier) mixed up with 3 coins (one is lighter).
- deleted 8y ago
  [deleted]
- grive 8y ago
  Label each coin, divide in three stacks each time, and shuffle meaningfully each time the subsets, to remove uncertainty.

philbarr 8y ago

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 8y ago
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 8y ago
"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 8y ago
  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.

catpolice 8y ago

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.

deleted 8y ago

[deleted]

QML 8y ago

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.