This is in reference to the generally good Description of the 12 Coin, 3 Weighings problem.Given the following:
The website indicates a generic algorithm of X = 3^N - 3.
X is the number of possibilities.
N is the number of weighing allowed
The base number 3 represents the outcomes of the weighing (H, E, L) for a given coin.
The represents three disallowed results of all H, all E, and all L.
Question #1:
My question is on the correctness of this equation.
The removal of a column of all-E is correct. Since the problem requires determination of whether the coin is heavy or light, and an all-E column fails to provide this information, it cannot be allowed.
However, I am wondering about the removal of both the all-H and all-L options. My guess is that someone realized that if one column started with all L, and the other column started with all H, the final results would not indicate which of the two items was the counterfeit. As a result, the person over-generalized to reject both all-L and all-H in the top half of the column. However, because there is no inherent problem with an all-H column, I am wondering why the restriction was not simply against an all-H OR all-L column.
Can you help me understand how allowing EITHER an all-H OR an all-L would be problematic?
If no such problem exists, then the algorithm would be slightly modified to be:
X = 3^N - 2, for N >= 2. (NOTE: this is closer, but still wrong... see below...)
Let's consider the smallest two values:
2. For two weighings, the site indicates only six possible outcomes. However, there seem to be eight valid outcomes. The six listed are HE, LE; LH, HL; and EL, EH. I ask now about HH, LL.
HH would indicate the fake coin is heavy, L would indicate it is light. Thus, the problem is not inherent in the specific column result of HH or LL. What is the problem?
HLE H
EHL H
123 4
ELH L
LHE L
The problem is: how do you equally split HLEH on the scale for weighing? There are two H, one L, and one E. Thus, to allow the fourth item would require an additional "known good" ball/coin.
So, what is really needed, rather than subtracting by a fixed amount, is to fix the possibilities to a multiple of three.
X = (3^N - 1) - ((3^N-1) MODULO 3), for N >= 1
Now, I realize that, because the 3^N is always a multiple of 3, and because we're subtracting a fixed number (1) that is less than 3, the result of ((3^N-1) MODULO 3) will always be 2. But, that simply hides the purpose or reasoning of the WHY of the equation, and keeps it looking like magic.
The exclusion of the columns indicated happens to be a nice way to get a set of weighings that always works, but there's really no derivation provided.
Question #2:
Can you note the variation in the problem, where the determination of the counterfeit coin/ball is required, but the information as to whether it is heavier/lighter is not a required result? In 3 weighings, one can pick the counterfeit from 13 such coins/balls.
However, the algorithm is not as clean.