Hacker News Reader

Comment by macrael | Hacker News Reader

Wow I didn’t know there was a solution where you always weigh 4v4. I’ve only ever solved it with weighings that eliminate coins, never with a sum at the end

View on HN

Makes me wonder if there's an obvious way to see how it works. Technically you could just go from the table at the end of this article and keep swapping until you end up with a system that puts an equal number of coins at both ends.

Though the system uses 12 out of the 13 possible pairs (and never EEE, for obvious reasons) and I'm not sure if it matters which one you leave out. (for those keeping track LRL/RLR doesn't occur, but this could equivalently have been any of the 4 pairs without an E)

Personally I was quite happy to solve it by figuring out the sub-problem of finding a fake coin out of 4 possible fakes and one real coin, and then reducing the 12 coin problem to that.

This puzzle is used to inrto entropy in "Information Theory, Inference, and Learning Algorithms".

Basically there are log2(12) + 1 bits or log2(24) of information (which ball and heavier or lighter). Any solution must reveal all information.

For example, a first weighing with an initial (4,4,4) split has three possible outcomes with equal probability (left, even, right), so reveals log2(3) bits. 3 independent weighings with equal outcomes would reveal 3*log2(3) bits, or log2(27). Of course the weighings cannot be independent since 27 > 24.

The trick is to design a scheme which reveals all 24 bits. With the static solutions this is trickier since all bits need to be revealed in all 27 possible outcomes, but if you work through them it should reveal why the solution works.

To elaborate on a point of 0xfaded's comment, the "12 of 13 possible pairs" is the crux of the solution. And when I solved this as a budding math student, I found two solutions -- I first, laboriously, worked top-down and came up with an entire decision tree. It was manifestly beautiful but entirely inelegant. So I worked from the bottom up, and found this solution.

How do we work from the bottom up? We construct a "truth table" for the various results, note the symmetry,

    --- +++ A
    --0 ++0 B
    --+ ++- C
    -0- +0+ D
    -00 +00 E
    -0+ +0- F
    -+- +-+ G
    -+0 +-0 H
    -++ +-- I
    0-- 0++ J
    0-0 0+0 K
    0-+ 0+- L
    00- 00+ M
    000 000 X

When I read off this "truth table" I immediately see a parity issue: it's telling me to weigh (ABCDEFGHI) all at the same time. Nine balls? That's not gonna balance out. Also, all of those balls have the same apparent sign for the first weighing so I'll need to break parity somehow. What if I just alternate signs as I walk down the table?

    --- +++ A
    ++0 --0 B
    --+ ++- C
    +0+ -0- D
    -00 +00 E
    +0- -0+ F
    -+- +-+ G
    +-0 -+0 H
    -++ +-- I
    0++ 0-- J
    0-0 0+0 K
    0+- 0-+ L
    00- 00+ M
    000 000 X

Alright, this gives the weighings

  ACEGI BDFH
  ACHK  BGIJL
  AFGLM CDIJ

Now, we take a popularity contest: who only shows up in overloaded pans? Discard the G and we arrive at

  ACEI BDFH
  ACHK BIJL
  AFLM CDIJ

Reply on news.ycombinator.com