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/ and converting to word problems.
If you like cool problems, here is one I have not found a simple solution for, but I once saw it in a place where a simple solution should exist.
You have an odd number >=3 of items with the property that any time you remove one, there is a way to split the remaining items into two piles of equal weight. Show all items have the same weight.
It's easy for 3 items, A,B,C. Remove C, A balances B, then do A,C, now all equal.
It's easy to check by hand for a few small cases.
I proved it using more advanced stuff from lin alg. But I've never found a simple solution yet.
For number 5, I can use items of weights 3 1 1 1 1 and they are not equal. If you remove 3, you get 1+1=1+1 and in case you remove only of 1s, you can split 3 = 1+1+1.
But no such proof can exist because the claim is not true. When you posted your comment, Fetiorin had already given a counterexample.
The puzzle is related to the game 20 questions. If you can ask only 20 yes/no questions, you can differentiate 2^20 items. For example, with 20 yes/no questions, you can determine an integer in 1 to 1,000,000 (technically, up to 2^20).
Now consider you need to figure out what integer between 1 and 1,000,000 I am think of, but I am allowed to lie at most once. Now how many questions will you need to ensure you get the answer?
Doing this by hand and creating more and more convoluted tricks is possible, but in reality this is another error correction problem: The original problem is a binary message of length 20 bits, from which you get the 20 bit message.
With at most one lie, there is a 20 bit message, me (the noisy channel) can add at most one error, so you need the minimal length binary code that takes a message of length 20 and a max error of 1 bit.
To find the number needed, use a coding table like http://www.codetables.de/.
So you need to find how many more bits you need. To fix d bits, you need 2d+1 'distance' in your code to make sure d errors do not move one valid point within Hamming distance d of another answer, so we need d = 3.
So you need a binary code, d = 3, and encoding a message of length k=20. Click on Linear Codes, then the GF2 button, and you see the big table of best codes. Find the column with k = 20 (our message length), scroll down over increasing n (number of questions needed), until the first d=3 entry. There n = 25, so 25 questions will do it. This is the result http://www.codetables.de/BKLC/BKLC.php?q=2&n=25&k=20
This is provably best, otherwise the table would have a range if there were not proof (look around the table, notice some are ranges).
To design the questions, most places with tables have code constructions. So click the entry, and they describe the construction (unfortunately in error correction code terms), but that can be reversed into English and actual questions to get your answer.
This technique would let you answer any problem along the line of "How many questions, each with b options, would it take to determine between N items, if there are at most d lies told?"
This type of solution requires choices and branching. Mine was nicer I think since it requires no branches, and the weighings themselves spit out the bad coin number in base 3.
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.
What is XY? What's WLOG?
Can you dumb this down a bit more please?
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
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.
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.
The idea works. When I solved it before I cider it up to test
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.
Use base 3 with 'digits' -1,0,1.
It's useful and interesting to note you can uniquely encode and decode any integer in any base with 'shifted' digits. If you allow some digits to be positive and some negative, you get both positive and negative integers encoded for free without needing sign extraction, using standard algorithms. You can also change base per slot and go into mixed-radix tricks for encoding (useful for turning things with varying choices per slot into unique encodings).
Things look like
Encode(int val, int base, int shift)
while (val != 0)
d = ((val%b)+b)%b; // get positive mod 'digit'
if (d + shift >= b) d = d-b; // shift digits
val -= d; // kill off low digit - often not done in positive only case
val /= d;
output(d)
Decode (list of digits, int base, int shift)
val = 0
reverse digits
foreach digit d
val = val * b + d
return val
digits -1,0,1 also makes a unique base 3 representation of any integer using the same encoding and decoding algorithms. In fact, you can shift digits in any base like this and still get unique encoding and decoding, with the benefit that they handle positive and negative numbers for free.
Shifting the digits is exactly equivalent to biasing the number; in this case, changing the interpretation of the graphical symbols "0", "1" and "2" to be the numeric values -1, 0, and 1 just means we subtract trinary 111 = decimal 13 from our three-digit value. So we could represent the value -4 as "0--" (in "shifted trinary") or we could represent it as "100" (in biased trinary, since 9-13 = -4) and those representations are glyph-to-glyph isomorphic. Since the representable range of three digits of ordinary trinary is 0-26, the representable range using three of these shifted digits is -13 to +13.
Using this -/0/+ representation, it is easy to state a weighing schedule in which the absolute value of the three trinary digits you get as output from the scale represent equals the label (1-12) of the misweighted ball.[1]
But it appears to be impossible for the representation to be positive whenever the ball is heavy and negative whenever the ball is light.
Let's assume that we record a - when the scale tips right and a + when the scale tips left.
The problem is that every time we do a weighing, there will be at least one ball on each side of the scale. (Or else the weighing would generate zero information.) So without loss of generality, there is a ball L on the left of the weighing which gives us our most significant digit, and a different ball R on the right of the same weighing.
Since we record a - when the scale tips right, our most significant digit will be -, and therefore our overall result will be negative, whenever ball R is heavy. This conflicts with your stated goal of having the result be positive whenever any ball is heavy.
This will make it difficult to design an algorithm to identify the ball that doesn't involve any branches - we can branchlessly determine which ball is misweighted, but we need a branch (or a lookup table) to determine whether it's light or heavy.
[1] This will do the job:
6 8 10 11 vs 5 7 9 12
3 5 7 11 vs 2 4 6 12
1 2 5 10 vs 4 7 8 11
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.
Here I picked the above since it is a valid sequence, but fails for the reason elsewhere on this page - you also need to not have negative paired columns. And that too turns out to not be enough, so write a simple program and crunch to check each case that does work, and there's (I think) 304. I should stop poking at this as I have real work I should be doing :)
If you really want to clean it up, you could then map the answer 3-vector of scrambled -1,0,1 values into another decoder matrix to map into values you like. Or use a look up table.
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/then cases to juggle items around to find the mis-weighted ball.
My solution numbered the balls in base 3, then did four weighings with no if/thens,. The weightings each gave a base 3 result: left, balance, right. This formed the digits of the mis-weighted ball.
The idea is to make an error correcting code in base 3, and use the "weighings" as the correction matrix to isolate the bad "bit".
This idea generalizes to solve a massive range of find the odd item(s) problems.