14 ms·

Always cool to see unexpected applications of information theory, especially outside of probabilistic contexts. A related toy example that comes to mind is the

Always cool to see unexpected applications of information theory, especially outside of probabilistic contexts. A related toy example that comes to mind is the puzzle where you're given 12 metal balls and told that one of them is either heavier or lighter than the rest. You're then given a balance/scale and instructed to figure out which ball is different and whether it is heavier or lighter using the balance a maximum of three times to weigh different combinations of balls. Part of the reason this is solvable is because there are 12x2=24 different possibilities (or log2(24) = 4.58 bits) for the ball ID/weight and 27=3x3x3 possible outcomes (or log2(27) = 4.75 bits) for the weighing process (left heavier, right heavier, or equal in each use). Thus, there's a chance the weighing sequence could convey the ball ID/weight. If there were 14 balls, however, then you would require log(28) = 4.81 bits of information to specify the ball ID/weight, so the puzzle would be unsolvable, since there wouldn't be enough information available in the weighing sequence to specify the ball ID/weight.

geenew 4y ago
There's an episode of Columbo with a similar problem, expressed as: there are a number of bags. Each bag contains many gold coins. The gold coins weigh 1 ounce each. However, one bag contains fake coins, which appear the same as the real coins, but have a slightly different weight - 1.1 ounces per coin. You have a scale, which you can only use once, and you must find the bag with the fake coins. The solution is: Take one coin from the first bag, two coins from the second bag, three coins from the third bag, etc. Weigh all of the selected coins at the same time to get a total weight. Subtract from the total weight the triangular number of the number of bags[1], in ounces. The remainder, divided by 0.1, will be the number of the bag with the fake coins. [1] eg, for three bags, 1 + 2 + 3 = 6
- recursive 4y ago
  I'm amazed that there was an episode of a popular TV drama aired that had such a detailed puzzle in it.
  - hgsgm 4y ago
    Columbo episodes were unusually long. Each was the length of a short movie: ~1 to ~1.5hrs. One of the Die Hard movies had the "extract 1 gallon from a 3 gallon and a 5 gallon jug" puzzle in it.
- terminal_d 4y ago
  Isn't that overcomplicating the solution? The only requirement is to have a unique number of coins from the fake coin pouch. Since we don't know which one that is, every pouch gets a different number of coins, and not necessarily a sequence starting from 1. Then, you weigh them all assuming they're all real, but wait, they're not! So you take the excess weight, divide it by the excess weight per fake coin, and the bag from which you took out that many coins is the bag with the fake coins.
fizzynut 4y ago
I'm not sure why you say it won't work with 14 balls, this is solvable with up to 27 balls in 3 weighs. Weigh 1: 9 vs 9 (18 on balance), 9 off Weigh 2: 3 vs 3 (6 on balance ), 3 off Weigh 3: 1 vs 1 (2 on balance ), 1 off
- hello_hny 4y ago
  You don't know if the unique ball is heavier or lighter, how would this work?
  - fizzynut 4y ago
    Ah, if you need to know that for certain then you'd be restricted to 18 balls (6,6,6), (2,2,2), (1,1). Otherwise I guess you would "only" know in 26/27 cases if it was heavier or lighter (off the balance in all 3 conditions). ....and now I understand, you would only initially know there is a difference in weight, not which side had the heavier or lighter ball.
    - hgsgm 4y ago
      No, you can't solve the harder version with 18 balls, as you just proved. 18 balls have 36>27 states.
deleted 4y ago
[deleted]
koolba 4y ago
The 12-ball problem is a fun one and IMO the key revelation is that you do not need to determine whether the ball is lighter or heavier (which isn’t possible anyway). Just which ball is different than the rest. It’s a great exercise in decision trees as you change your strategy based on total information, not just the most recent step. It’s also fun to scale the problem from 3 balls up to see how the solution evolves.
- thaumasiotes 4y ago
  >> you're given 12 metal balls and told that one of them is either heavier or lighter than the rest. You're then given a balance/scale and instructed to figure out which ball is different and whether it is heavier or lighter using the balance a maximum of three times > The 12-ball problem is a fun one and IMO the key revelation is that you do not need to determine whether the ball is lighter or heavier (which isn’t possible anyway). Huh?
  - vgb2k18 4y ago
    If I'm reading this [0] right, the heavier/lighter factor can be determined within 3 weightings... [0] https://suresolv.com/brain-teaser/find-fake-ball-among-12-identical-balls-3-weighing-hard-puzzle-solution https://suresolv.com/brain-teaser/find-fake-ball-among-12-id...
    - thaumasiotes 4y ago
      Of course it can. There are 24 possible states and you get enough information to uniquely identify one of 27 states. This was already stated in the root comment. I'm confused how the response to "you must identify whether the odd ball is heavier or lighter" can be "the key to this is realizing you don't need to know whether the odd ball is heavier or lighter, which is good because that's impossible anyway".
      - vgb2k18 4y ago
        Sorry, yes I saw your confusion. If you read back to your Huh comment you might forgive me for reading it as that you were unsure of the truth yourself. The one word 'huh?', spoke to me as "which one of these is true?". Whereas a person who was sure of the true answer, I would expect to say "Hey that's incorrect", if they encountered an obviously mistaken quote.
SideQuark 4y ago
I once made a cool solution to this problem using information theory, in particular coding theory. The usual solution uses the fact there are 3 places to put items: left scale, off scale, and right scale. Then those solutions do if/then cases to juggle items around to find the mis-weighted ball. My solution numbered the balls in base 3, then did four weighings with no if/thens,. The weightings each gave a base 3 result: left, balance, right. This formed the digits of the mis-weighted ball. The idea is to make an error correcting code in base 3, and use the "weighings" as the correction matrix to isolate the bad "bit". This idea generalizes to solve a massive range of find the odd item(s) problems.
- polishdude20 4y ago
  Can you explain how you weigh the balls? How many do you weigh at a time and how do you decide which ones to weigh? I'm trying to follow your solution but I'm confused about this one thingn
  - SideQuark 4y ago
    The traditional solutions do things like: 1) split into 4 piles A,B,C. compare A,B on the balance. 2) If they balance, bad coin in 4 in pile C can easily be found. 3) If they don't balance, you know the 4 in C are good. At this point you have to fiddle by mixing coins among piles cleverly to get more weighings. But you can do it in three total. If I recall, seomthing like one from A, three from C, versus three from B, one from C, or something like that, is the next weighing. This type of solution requires choices and branching. Mine was nicer I think since it requires no branches, and the weighings themselves spit out the bad coin number in base 3.
    - hgsgm 4y ago
      There's a slightly simpler solution if you don't care whether the odd ball is lighter or heavier: It's: X. AAAA vs BBBB If X was balanced, XX: C1 vs C2, then XXX: C2 vs C3 (general way to distinguish 2 unknowns: weigh one unknown against one known) If X was unbalanced, WLOG assume A was heavier. XY: A1 A2 B1 vs A3 A4 B2 Then if XY balanced, use the general method to distinguish B3 or B4 as answer. If XY unbalanced, WLOG assume A1 or A2 is heavy, or B2 is light, so XYY A1 vs A2 finds the heavy one or implies B2 is light.

geenew 4y ago

There's an episode of Columbo with a similar problem, expressed as: there are a number of bags. Each bag contains many gold coins. The gold coins weigh 1 ounce each. However, one bag contains fake coins, which appear the same as the real coins, but have a slightly different weight - 1.1 ounces per coin. You have a scale, which you can only use once, and you must find the bag with the fake coins. The solution is: Take one coin from the first bag, two coins from the second bag, three coins from the third bag, etc. Weigh all of the selected coins at the same time to get a total weight. Subtract from the total weight the triangular number of the number of bags[1], in ounces. The remainder, divided by 0.1, will be the number of the bag with the fake coins. [1] eg, for three bags, 1 + 2 + 3 = 6

recursive 4y ago
I'm amazed that there was an episode of a popular TV drama aired that had such a detailed puzzle in it.
- hgsgm 4y ago
  Columbo episodes were unusually long. Each was the length of a short movie: ~1 to ~1.5hrs. One of the Die Hard movies had the "extract 1 gallon from a 3 gallon and a 5 gallon jug" puzzle in it.
terminal_d 4y ago
Isn't that overcomplicating the solution? The only requirement is to have a unique number of coins from the fake coin pouch. Since we don't know which one that is, every pouch gets a different number of coins, and not necessarily a sequence starting from 1. Then, you weigh them all assuming they're all real, but wait, they're not! So you take the excess weight, divide it by the excess weight per fake coin, and the bag from which you took out that many coins is the bag with the fake coins.

fizzynut 4y ago

I'm not sure why you say it won't work with 14 balls, this is solvable with up to 27 balls in 3 weighs. Weigh 1: 9 vs 9 (18 on balance), 9 off Weigh 2: 3 vs 3 (6 on balance ), 3 off Weigh 3: 1 vs 1 (2 on balance ), 1 off

hello_hny 4y ago
You don't know if the unique ball is heavier or lighter, how would this work?
- fizzynut 4y ago
  Ah, if you need to know that for certain then you'd be restricted to 18 balls (6,6,6), (2,2,2), (1,1). Otherwise I guess you would "only" know in 26/27 cases if it was heavier or lighter (off the balance in all 3 conditions). ....and now I understand, you would only initially know there is a difference in weight, not which side had the heavier or lighter ball.
  - hgsgm 4y ago
    No, you can't solve the harder version with 18 balls, as you just proved. 18 balls have 36>27 states.

deleted 4y ago

[deleted]

koolba 4y ago

The 12-ball problem is a fun one and IMO the key revelation is that you do not need to determine whether the ball is lighter or heavier (which isn’t possible anyway). Just which ball is different than the rest. It’s a great exercise in decision trees as you change your strategy based on total information, not just the most recent step. It’s also fun to scale the problem from 3 balls up to see how the solution evolves.

thaumasiotes 4y ago
>> you're given 12 metal balls and told that one of them is either heavier or lighter than the rest. You're then given a balance/scale and instructed to figure out which ball is different and whether it is heavier or lighter using the balance a maximum of three times > The 12-ball problem is a fun one and IMO the key revelation is that you do not need to determine whether the ball is lighter or heavier (which isn’t possible anyway). Huh?
- vgb2k18 4y ago
  If I'm reading this [0] right, the heavier/lighter factor can be determined within 3 weightings... [0] https://suresolv.com/brain-teaser/find-fake-ball-among-12-identical-balls-3-weighing-hard-puzzle-solution https://suresolv.com/brain-teaser/find-fake-ball-among-12-id...
  - thaumasiotes 4y ago
    Of course it can. There are 24 possible states and you get enough information to uniquely identify one of 27 states. This was already stated in the root comment. I'm confused how the response to "you must identify whether the odd ball is heavier or lighter" can be "the key to this is realizing you don't need to know whether the odd ball is heavier or lighter, which is good because that's impossible anyway".
    - vgb2k18 4y ago
      Sorry, yes I saw your confusion. If you read back to your Huh comment you might forgive me for reading it as that you were unsure of the truth yourself. The one word 'huh?', spoke to me as "which one of these is true?". Whereas a person who was sure of the true answer, I would expect to say "Hey that's incorrect", if they encountered an obviously mistaken quote.

SideQuark 4y ago

I once made a cool solution to this problem using information theory, in particular coding theory. The usual solution uses the fact there are 3 places to put items: left scale, off scale, and right scale. Then those solutions do if/then cases to juggle items around to find the mis-weighted ball. My solution numbered the balls in base 3, then did four weighings with no if/thens,. The weightings each gave a base 3 result: left, balance, right. This formed the digits of the mis-weighted ball. The idea is to make an error correcting code in base 3, and use the "weighings" as the correction matrix to isolate the bad "bit". This idea generalizes to solve a massive range of find the odd item(s) problems.

polishdude20 4y ago
Can you explain how you weigh the balls? How many do you weigh at a time and how do you decide which ones to weigh? I'm trying to follow your solution but I'm confused about this one thingn
- SideQuark 4y ago
  The traditional solutions do things like: 1) split into 4 piles A,B,C. compare A,B on the balance. 2) If they balance, bad coin in 4 in pile C can easily be found. 3) If they don't balance, you know the 4 in C are good. At this point you have to fiddle by mixing coins among piles cleverly to get more weighings. But you can do it in three total. If I recall, seomthing like one from A, three from C, versus three from B, one from C, or something like that, is the next weighing. This type of solution requires choices and branching. Mine was nicer I think since it requires no branches, and the weighings themselves spit out the bad coin number in base 3.
  - hgsgm 4y ago
    There's a slightly simpler solution if you don't care whether the odd ball is lighter or heavier: It's: X. AAAA vs BBBB If X was balanced, XX: C1 vs C2, then XXX: C2 vs C3 (general way to distinguish 2 unknowns: weigh one unknown against one known) If X was unbalanced, WLOG assume A was heavier. XY: A1 A2 B1 vs A3 A4 B2 Then if XY balanced, use the general method to distinguish B3 or B4 as answer. If XY unbalanced, WLOG assume A1 or A2 is heavy, or B2 is light, so XYY A1 vs A2 finds the heavy one or implies B2 is light.