Google researcher, long out of math, cracks devilish problem about sets

A. There are many ways to identify the misweighted ball in three deterministic weighings. The simple approach is to label the possible states 1 to 24, or alpha to omega, or what have you, and then to assign an outcome code to each state.

SideQuark wants to entwine the outcome codes with the state labels, so that the label for each state is the value represented by its outcome code when that code is interpreted as a trinary number. This sets up feedback between things that would otherwise be independent of each other; it's sort of like writing a quine.

B. Therefore, it's possible that the odd choice to start numbering the balls at 7 (and skip 13) represents a compromise with what outcome codes our system can generate.

(For example, you can identify and diagnose the misweighted ball in these three deterministic weighings: 1,2,3,4 vs 5,6,7,8; 1,5,9,10 vs 2,6,7,11; 2,4,6,9 vs 3,7,10,12. If an outcome of 0 represents the right side of the scale being heavier, and 1 represents the left side being heavier, then the outcome code 121 uniquely identifies the 4 ball as being too heavy. But 121 interpreted as a trinary number is 16, not 4.

In fact, in this weighing scheme, the outcome code "4" (= 011) cannot occur, and 9 and 26 are also impossible.)

C. SideQuark appears to be cheating in that his balls are labeled from 7 to 19 (skipping 13), but his column indices range from 1 to 12. This means he's given up on getting a real correspondence between label and outcome code (the balls have different labels depending on whether you're reading the specification of the test [1-12 in full] or the interpretation of the result [7-19 with a hole]), but it looks like he is still aiming to have a meaningful correspondence between the code that specifies a particular ball is heavy and the code that specifies the same ball is light.

D. We're going to record a trinary number between 000 and 222, a range from 0 to +26. It is not clear to me how we would get a negative number. We could interpret the number we get as a three-trit three's complement value, but in that case we'd really want the balls to be labeled from 1 to 12, so that a single value uniquely identifies and diagnoses a ball - for an example of the problem we're about to run into, the outcome 101 represents the value 10, and should tell us that the 10 ball is too heavy, but if we're using three's complement then 101 is also the value -17, which tells us that the 17 ball is too light. This is a bad outcome when the 10 ball and the 17 ball both exist.

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.

18 balls have 36>27 states.

By choosing 7-19, omit 13, you finding the center values of the range 0-26. This is important because when you write the values in ternary each column has the same number of 0 and 2 digits.

This would not hold if you simply used the values 0-12, for example. Then the first column has eight 0’s and four 1’s, so it does not correspond to a valid weighting.

It’s important to note that this method doesn’t work for the problem described - it only works if you know that the odd ball out is heavier. You can see my other comment for a description of why, and a working solution.