1||0|72|2|
0|0|0|||||Error in 12 Coins%2C 3 Weighings problem%3F|H.Gabryjelski|1|17:57:29|12/30/2009|This is in reference to the generally good description of %5Ba href%3D%22http%3A%2F%2Fwww.cut-the-knot.org%2Fblue%2FOddballProblem1.shtml%22%5D the 12 Coin%2C 3 Weighings%5B%2Fa%5D problem.%0D%0A%0D%0A%5Bu%5DGiven the following%3A%5B%2Fu%5D%0D%0AThe website indicates a generic algorithm of X %3D 3%5EN - 3.%0D%0A%5Blist%5D%0D%0A%5Bli%5DX is the number of possibilities.%0D%0A%5Bli%5DN is the number of weighing allowed%0D%0A%5Bli%5DThe base number 3 represents the outcomes of the weighing %28H%2C E%2C L%29 for a given coin.%0D%0A%5Bli%5DThe represents three disallowed results of all H%2C all E%2C and all L.%0D%0A%5B%2Flist%5D%0D%0A%0D%0A%0D%0A%0D%0A%5Bu%5DQuestion %231%3A%5B%2Fu%5D%0D%0AMy question is on the correctness of this equation.%0D%0A%0D%0AThe removal of a column of all-E is correct.  Since the problem requires determination of whether the coin is heavy or light%2C and an all-E column fails to provide this information%2C it cannot be allowed.%0D%0A%0D%0AHowever%2C 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%2C and the other column started with all H%2C the final results would not indicate which of the two items was the counterfeit.  As a result%2C the person over-generalized to reject both all-L and all-H in the top half of the column.  However%2C because there is no inherent problem with an all-H column%2C I am wondering why the restriction was not simply against an all-H %5Bb%5D%5Bu%5DOR%5B%2Fu%5D%5B%2Fb%5D all-L column.%0D%0A%0D%0ACan you help me understand how allowing %5Bb%5D%5Bu%5DEITHER%5B%2Fu%5D%5B%2Fb%5D an all-H %5Bb%5D%5Bu%5DOR%5B%2Fu%5D%5B%2Fb%5D an all-L would be problematic%3F%0D%0A%0D%0AIf no such problem exists%2C then the algorithm would be slightly modified to be%3A%0D%0A%5Bb%5DX %3D 3%5EN - 2%5B%2Fb%5D%2C for N %3E%3D 2.  %28NOTE%3A this is closer%2C but still wrong... see below...%29%0D%0A%0D%0ALet%27s consider the smallest two values%3A%0D%0A%0D%0A2. For two weighings%2C the site indicates only six possible outcomes.  However%2C there seem to be eight valid outcomes.  The six listed are HE%2C LE%3B LH%2C HL%3B and EL%2C EH.  I ask now about HH%2C LL.%0D%0A%0D%0AHH would indicate the fake coin is heavy%2C L would indicate it is light.  Thus%2C the problem is not inherent in the specific column result of HH or LL.  What is the problem%3F%0D%0A%0D%0A  HLE H%0D%0A  EHL H%0D%0A  123 4%0D%0A  ELH L%0D%0A  LHE L%0D%0A%0D%0AThe problem is%3A how do you equally split HLEH on the scale for weighing%3F  There are two H%2C one L%2C and one E.  Thus%2C to allow the fourth item would require an additional %22known good%22 ball%2Fcoin.%0D%0A%0D%0ASo%2C what is really needed%2C rather than subtracting by a fixed amount%2C is to fix the possibilities to a multiple of three.%0D%0A%0D%0A%5Bb%5DX %3D %283%5EN - 1%29 - %28%283%5EN-1%29 MODULO 3%29%5B%2Fb%5D%2C for N %3E%3D 1%0D%0A%0D%0ANow%2C I realize that%2C because the 3%5EN is always a multiple of 3%2C and because we%27re subtracting a fixed number %281%29 that is less than 3%2C the result of %28%283%5EN-1%29 MODULO 3%29 will always be 2.  But%2C that simply hides the purpose or reasoning of the WHY of the equation%2C and keeps it looking like magic.%0D%0A%0D%0AThe exclusion of the columns indicated happens to be a nice way to get a set of weighings that always works%2C but there%27s really no derivation provided.%0D%0A%0D%0A%0D%0A%5Bu%5DQuestion %232%3A%5B%2Fu%5D%0D%0ACan you note the variation in the problem%2C where the determination of the counterfeit coin%2Fball is required%2C but the information as to whether it is heavier%2Flighter is not a required result%3F  In 3 weighings%2C one can pick the counterfeit from 13 such coins%2Fballs.%0D%0A%0D%0AHowever%2C the algorithm is not as clean.
1|1|0|||||RE%3A Error in 12 Coins%2C 3 Weighings problem%3F|alexb||18:11:36|01/01/2010|Have you considered the author%27s stipulation that no ball appears three times on the same side%3F If it is possible to satisfy this requirement then surely neither HHH or LLL is possible. So the correct question should be whether or not the stipulation is enforceable. As the specific distribution of the balls that follows the two arrays shows%2C the answer is in affirmative.