5 ms·

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 i

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.
    - polishdude20 4y ago
      What is C1 and C2 and C3? What is XY? What's WLOG? Can you dumb this down a bit more please?
SideQuark 4y ago
Just took a stab at recreating my older solution. It goes something like this Number the balls 7 8 9 10 11 12 14 15 16 17 18 19 Then do three weighings according to rows like this: 0 1 -1 0 1 -1 1 -1 0 1 -1 0 1 1 -1 -1 -1 0 0 1 1 1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 1 1 Where -1 means index on left side of of balance, 0 means not on balance, 1 means on right side of balance. Note each row has the same number of -1 and 1. If left is heavy, record 0, else if balanced, record 1, else if right heavy, record 2. Then the base 3 value gives the coin label above (in absolute value) and is >0 if heavier, else is -1 if lighter. Also note there is no if/then. You simply follow these three and record the numbers which spit out the answer. The idea is the matrix represents an error correction code in base 3. You need each column distinct, and coin j being out of whack selects column j from the matrix.
- 11101010001100 4y ago
  Does this still work if I mislabel the balls to begin with?
- expensive_news 4y ago
  I like how simple the deciding process becomes but I’m afraid there might be a problem. This solution works when the odd ball is always heavier, but it could either be heavier or lighter, and you don’t know which. For example, say ball 7 is heavier. From top to bottom, the weightings would result in: 120. However, if ball 19 was lighter you would obtain the same weighing sequence 120. I believe that there is another condition that must be imposed on the matrix - namely, the column must be unique, but also -1*column must not be another column. I created the following matrix, which can identify the ball and if it is heavier or lighter. However, this does not line up neatly, and would require a table to decode the output of the weighings. -1 -1 -1 -1 1 1 1 1 0 0 0 0 -1 -1 0 1 0 -1 -1 0 1 1 0 1 0 1 -1 0 -1 1 -1 0 1 0 1 -1 For example, the sequence 001 means the first ball is heavier. The sequence 221 means the first ball is lighter. Etc.
  - deleted 4y ago
    [deleted]
SilasX 4y ago
That's called IIRC an "unconditional" solution (in that later weighings don't depend on earlier weighings). David MacKay poses that a problem in his Information theory book on p. 85, and gives the solution on the next page. http://www.inference.org.uk/itprnn/book.pdf http://www.inference.org.uk/itprnn/book.pdf
hgsgm 4y ago
That's clever! If you get an "equal" result from the scale, then you can put those balls on the scale with the unknown ones, so you can maintain symmetry in the weighings.
jacquesm 4y ago
That is a beautiful solution, wow. I'm just floored by you coming up with that, it is so utterly out of the box.
- actually_a_dog 4y ago
  It is a beautiful solution, but it's not terribly out of the box. It's similar to generating all subsets of a set of N items by iterating through the integers 0..2^N - 1 and checking to see which bits are set.
  - thaumasiotes 4y ago
    As stated, it's not a solution at all - it uses four out of three possible weighings.
    - SideQuark 4y ago
      No, it does three. The "four" is a typing mistake. And it's provably optimal from the theory behind construction of minimal error correcting codes.
      - tmoertel 4y ago
        Ah, it looks like there's a typo in your earlier post. It currently reads: "My solution numbered the balls in base 3, then did four weighings with no if/thens..." (Emphasis mine.)
  - SideQuark 4y ago
    All subsets requires 2^12 weighings. The beautiful thing about error correcting codes is finding a minimal set of spanning items. And in this case, binary will not suffice, since you can only distinguish 2^3 = 8 items. The third position, one most people don't think if, is the "off balance" set, which gives three choies. Then 3 weighings, 3 choices per, gives 27 possible outcomes, which is enough to distinguish which of 12 items is off, as well as whether or not it's higher or lower in weight (another factor of 2), for 24 choices. So there is a little extra in the 3=27-24 information theoretical bounds. Using this idea, you can generate all sorts of hard coin problems, vastly harder than this one :), by mining error correction tables like http://www.codetables.de/ http://www.codetables.de/ and converting to word 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.
  - polishdude20 4y ago
    What is C1 and C2 and C3? What is XY? What's WLOG? Can you dumb this down a bit more please?

SideQuark 4y ago

Just took a stab at recreating my older solution. It goes something like this Number the balls 7 8 9 10 11 12 14 15 16 17 18 19 Then do three weighings according to rows like this: 0 1 -1 0 1 -1 1 -1 0 1 -1 0 1 1 -1 -1 -1 0 0 1 1 1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 1 1 Where -1 means index on left side of of balance, 0 means not on balance, 1 means on right side of balance. Note each row has the same number of -1 and 1. If left is heavy, record 0, else if balanced, record 1, else if right heavy, record 2. Then the base 3 value gives the coin label above (in absolute value) and is >0 if heavier, else is -1 if lighter. Also note there is no if/then. You simply follow these three and record the numbers which spit out the answer. The idea is the matrix represents an error correction code in base 3. You need each column distinct, and coin j being out of whack selects column j from the matrix.

11101010001100 4y ago
Does this still work if I mislabel the balls to begin with?
expensive_news 4y ago
I like how simple the deciding process becomes but I’m afraid there might be a problem. This solution works when the odd ball is always heavier, but it could either be heavier or lighter, and you don’t know which. For example, say ball 7 is heavier. From top to bottom, the weightings would result in: 120. However, if ball 19 was lighter you would obtain the same weighing sequence 120. I believe that there is another condition that must be imposed on the matrix - namely, the column must be unique, but also -1*column must not be another column. I created the following matrix, which can identify the ball and if it is heavier or lighter. However, this does not line up neatly, and would require a table to decode the output of the weighings. -1 -1 -1 -1 1 1 1 1 0 0 0 0 -1 -1 0 1 0 -1 -1 0 1 1 0 1 0 1 -1 0 -1 1 -1 0 1 0 1 -1 For example, the sequence 001 means the first ball is heavier. The sequence 221 means the first ball is lighter. Etc.
- deleted 4y ago
  [deleted]

SilasX 4y ago

That's called IIRC an "unconditional" solution (in that later weighings don't depend on earlier weighings). David MacKay poses that a problem in his Information theory book on p. 85, and gives the solution on the next page. http://www.inference.org.uk/itprnn/book.pdf http://www.inference.org.uk/itprnn/book.pdf

hgsgm 4y ago

That's clever! If you get an "equal" result from the scale, then you can put those balls on the scale with the unknown ones, so you can maintain symmetry in the weighings.

jacquesm 4y ago

That is a beautiful solution, wow. I'm just floored by you coming up with that, it is so utterly out of the box.

actually_a_dog 4y ago
It is a beautiful solution, but it's not terribly out of the box. It's similar to generating all subsets of a set of N items by iterating through the integers 0..2^N - 1 and checking to see which bits are set.
- thaumasiotes 4y ago
  As stated, it's not a solution at all - it uses four out of three possible weighings.
  - SideQuark 4y ago
    No, it does three. The "four" is a typing mistake. And it's provably optimal from the theory behind construction of minimal error correcting codes.
    - tmoertel 4y ago
      Ah, it looks like there's a typo in your earlier post. It currently reads: "My solution numbered the balls in base 3, then did four weighings with no if/thens..." (Emphasis mine.)
- SideQuark 4y ago
  All subsets requires 2^12 weighings. The beautiful thing about error correcting codes is finding a minimal set of spanning items. And in this case, binary will not suffice, since you can only distinguish 2^3 = 8 items. The third position, one most people don't think if, is the "off balance" set, which gives three choies. Then 3 weighings, 3 choices per, gives 27 possible outcomes, which is enough to distinguish which of 12 items is off, as well as whether or not it's higher or lower in weight (another factor of 2), for 24 choices. So there is a little extra in the 3=27-24 information theoretical bounds. Using this idea, you can generate all sorts of hard coin problems, vastly harder than this one :), by mining error correction tables like http://www.codetables.de/ http://www.codetables.de/ and converting to word problems.