<story><title>Google researcher, long out of math, cracks devilish problem about sets</title><url>https://www.quantamagazine.org/long-out-of-math-an-ai-programmer-cracks-a-pure-math-problem-20230103/</url></story><parent_chain><item><author>SideQuark</author><text>I once made a cool solution to this problem using information theory, in particular coding theory.&lt;p&gt;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&amp;#x2F;then cases to juggle items around to find the mis-weighted ball.&lt;p&gt;My solution numbered the balls in base 3, then did four weighings with no if&amp;#x2F;thens,. The weightings each gave a base 3 result: left, balance, right. This formed the digits of the mis-weighted ball.&lt;p&gt;The idea is to make an error correcting code in base 3, and use the &amp;quot;weighings&amp;quot; as the correction matrix to isolate the bad &amp;quot;bit&amp;quot;.&lt;p&gt;This idea generalizes to solve a massive range of find the odd item(s) problems.</text></item><item><author>rkp8000</author><text>Always cool to see unexpected applications of information theory, especially outside of probabilistic contexts.&lt;p&gt;A related toy example that comes to mind is the puzzle where you&amp;#x27;re given 12 metal balls and told that one of them is either heavier or lighter than the rest. You&amp;#x27;re then given a balance&amp;#x2F;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.&lt;p&gt;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&amp;#x2F;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&amp;#x27;s a chance the weighing sequence could convey the ball ID&amp;#x2F;weight. If there were 14 balls, however, then you would require log(28) = 4.81 bits of information to specify the ball ID&amp;#x2F;weight, so the puzzle would be unsolvable, since there wouldn&amp;#x27;t be enough information available in the weighing sequence to specify the ball ID&amp;#x2F;weight.</text></item></parent_chain><comment><author>SideQuark</author><text>Just took a stab at recreating my older solution. It goes something like this&lt;p&gt;Number the balls 7 8 9 10 11 12 14 15 16 17 18 19&lt;p&gt;Then do three weighings according to rows like this:&lt;p&gt;&lt;pre&gt;&lt;code&gt;     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
&lt;/code&gt;&lt;/pre&gt;
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.&lt;p&gt;If left is heavy, record 0, else if balanced, record 1, else if right heavy, record 2.&lt;p&gt;Then the base 3 value gives the coin label above (in absolute value) and is &amp;gt;0 if heavier, else is -1 if lighter.&lt;p&gt;Also note there is no if&amp;#x2F;then. You simply follow these three and record the numbers which spit out the answer.&lt;p&gt;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.</text></comment>
<story><title>Google researcher, long out of math, cracks devilish problem about sets</title><url>https://www.quantamagazine.org/long-out-of-math-an-ai-programmer-cracks-a-pure-math-problem-20230103/</url></story><parent_chain><item><author>SideQuark</author><text>I once made a cool solution to this problem using information theory, in particular coding theory.&lt;p&gt;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&amp;#x2F;then cases to juggle items around to find the mis-weighted ball.&lt;p&gt;My solution numbered the balls in base 3, then did four weighings with no if&amp;#x2F;thens,. The weightings each gave a base 3 result: left, balance, right. This formed the digits of the mis-weighted ball.&lt;p&gt;The idea is to make an error correcting code in base 3, and use the &amp;quot;weighings&amp;quot; as the correction matrix to isolate the bad &amp;quot;bit&amp;quot;.&lt;p&gt;This idea generalizes to solve a massive range of find the odd item(s) problems.</text></item><item><author>rkp8000</author><text>Always cool to see unexpected applications of information theory, especially outside of probabilistic contexts.&lt;p&gt;A related toy example that comes to mind is the puzzle where you&amp;#x27;re given 12 metal balls and told that one of them is either heavier or lighter than the rest. You&amp;#x27;re then given a balance&amp;#x2F;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.&lt;p&gt;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&amp;#x2F;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&amp;#x27;s a chance the weighing sequence could convey the ball ID&amp;#x2F;weight. If there were 14 balls, however, then you would require log(28) = 4.81 bits of information to specify the ball ID&amp;#x2F;weight, so the puzzle would be unsolvable, since there wouldn&amp;#x27;t be enough information available in the weighing sequence to specify the ball ID&amp;#x2F;weight.</text></item></parent_chain><comment><author>hgsgm</author><text>That&amp;#x27;s clever! If you get an &amp;quot;equal&amp;quot; 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.</text></comment>