3 ms·
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
by 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 agoAs stated, it's not a solution at all - it uses four out of three possible weighings.
- SideQuark 4y agoNo, 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 agoAh, 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 agoAll 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.