5 ms·

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 accord

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]
- SideQuark 4y ago
  You might be right. I didn't check as carefully as when I did it decades ago. This is all from memory, and the matrix above I sketched out over dinner by hand :) The idea works. When I solved it before I cider it up to test
- thaumasiotes 4y ago
  I don't understand how SideQuark is distinguishing negative results from positive results. But using the representation he suggested to me sidethread, it isn't possible to have the result be positive whenever the misweighted ball is heavy and negative whenever it's light.
garfieldnate 4y ago
Why do the balls have to be numbered starting at 7?
- thaumasiotes 4y ago
  I'm a different person, but I can provide some commentary about that. 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.

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]
SideQuark 4y ago
You might be right. I didn't check as carefully as when I did it decades ago. This is all from memory, and the matrix above I sketched out over dinner by hand :) The idea works. When I solved it before I cider it up to test
thaumasiotes 4y ago
I don't understand how SideQuark is distinguishing negative results from positive results. But using the representation he suggested to me sidethread, it isn't possible to have the result be positive whenever the misweighted ball is heavy and negative whenever it's light.

garfieldnate 4y ago

Why do the balls have to be numbered starting at 7?

thaumasiotes 4y ago
I'm a different person, but I can provide some commentary about that. 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.