luong@tonto.DEC (Van Luong Nguyen UHO DTN 264-6560) (06/01/84)
>> Given 12 pennies one of which is different in weight, use a balance exactly >> 3 times (comparing the weight of two groups of coins) to determine the odd >> penny, and tell whether it is heavy or light. A good solution to this puzzle has been posted on the net. However, this solution is *SEQUENTIAL* in nature, ie. how the second weighing is done depends on the outcome of the first weighing etc... 1. Puzzle Extension : find a *COMBINATORIAL* (non-sequential) solution, ie. specify the three weighings up front, and determine the answer when given the results of the weighings. 2. Generalized Puzzle: For how many pennies can the problem be solved , by using N weighings? (Answer: (3**N - 3)/2 ) . What is the general solution? SOLUTION. Mathematicians familiar with the theory of Cyclic Redundancy Codes (CRC) will recognize that the 12 pennies problem is a "single bit" error correcting code in the *ternary* field (each "bit" can have 3 values: 0, 1, -1) with 12 data "bits" and N=3 check "bits". 1. COMBINATORIAL SOLUTION FOR 12 PENNIES (N=3): Weighing # left right | Notation for weighing result: 1 (5+6+7+8) (9+10+11+12) | 0 Right & left groups equal 2 (8+10+11+12) (2+3+4+9) | +1 Right group heavier 3 (4+6+9+12) (1+3+7+11) | -1 Right group lighter A result of (0 -1 0) means R & L groups are equal in weighings #1 and #3, and R group is lighter in weighing #2. Answer determined from results table below: 0 0 0 All coins true, ie. No false coin. 0 0 1 Coin 1 Heavy 0 0 -1 Coin 1 Light 0 1 0 2 H 0 -1 0 2 L 0 1 1 3 H 0 -1 -1 3 L 0 1 -1 4 H 0 -1 1 4 L -1 0 0 5 H 1 0 0 5 L -1 0 -1 6 H 1 0 1 6 L -1 0 1 7 H 1 0 -1 7 L -1 -1 0 8 H 1 1 0 8 L 1 1 -1 9 H -1 -1 1 9 L 1 -1 0 10 H -1 1 0 10 L 1 -1 1 11 H -1 1 -1 11 L 1 -1 -1 12 H -1 1 1 12 L (Results ( 1 1 1 ) and ( -1 -1 -1 ) CANNOT happen - see sections 2 & 3 below). 2. Generalized Puzzle: The algorithm to obtain the solution for the general case of ((3**N - 3)/2) pennies in N weighings, is shown using the case of N=3, and ((3**3 - 3)/2) = 12, as an illustration. (Mathematical "pseudo-proof" is included). Step 1: Write down in a matrix all possible columns of N=3 digits, each digit having 0 or 1 or -1 as possible values: 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 1 1 1 0 0 0 1 1 1 -1 -1 -1 0 -1 -1 -1 0 0 0 -1 -1 -1 1 1 1 0 1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 -1 0 -1 1 0 -1 1 0 -1 1 0 -1 1 Step 2: Eliminate .the all_zeros column .the all_ones column .all columns with -1 as the first non-zero digit. We are left with a 3x12 matrix, with columns all *DIFFERENT* from each other: 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 -1 -1 -1 1 0 1 -1 0 1 -1 0 -1 0 1 -1 Step 3: Reverse the sign of all digits in the MIDDLE third of the matrix, ie. columns 5,6,7 8: 1 2 3 4 5 6 7 8 9 10 11 12 0 0 0 0 -1 -1 -1 -1 1 1 1 1 0 1 1 1 0 0 0 -1 1 -1 -1 -1 1 0 1 -1 0 -1 1 0 -1 0 1 -1 > Each row, now with exactly four 1's and four -1's, represent a >weighing: -1 means the corresponding penny is included in the Left group, >1 means Right group. Thus, row 2 specifies a comparison of (8+10+11+12) on >the Left, and (2+3+4+9) on the Right. If we describe the 12 pennies by a (12x1) vector, with 0=good coin, 1=heavy coin, -1=light coin, then the (12x1) vector will either be all zeroes (no false coin) or have AT MOST *one* non-zero element (one false coin). For example if coin 5 is light, then the vector is: ( 0 ) ( 0 ) ( 0 ) ( 0 ) (-1 ) ( 0 ) ( 0 ) ( 0 ) ( 0 ) ( 0 ) ( 0 ) ( 0 ) Doing the 3 weighings is equivalent to multiplying the (3x12) matrix by this (12x1) "error" vector, resulting in a (3x1) result vector. The result vector will either be all zeroes (no false coin), or be identical to one column of the 3x12 matrix if exactly one coin is heavy, or identical to the negative of the column is the coin is light. In the example of coin 5 being light, the 3 weighings should result in: ( 0 0 0 0 -1 -1 -1 -1 1 1 1 1 ) X ( 0 ) = ( 1 ) Right Heavy ( 0 1 1 1 0 0 0 -1 1 -1 -1 -1 ) ( 0 ) ( 0 ) Equal ( 1 0 1 -1 0 -1 1 0 -1 0 1 -1 ) ( 0 ) ( 0 ) Equal ( 0 ) (-1 ) ( 0 ) ( 0 ) ( 0 ) ( 0 ) ( 0 ) ( 0 ) ( 0 ) Comparing the result vector with the columns of the matrix shows that it is the negative of column 5, therefore the "error" vector has a -1 as its 5th element, thus coin 5 is the odd one, and it is lighter than normal. This explains the result table given earlier in Part 1 of the solution. 3. Given an extra coin KNOWN to be true, we can solve for [((3**N - 3)/2) + 1] coins. For example, in the N=3 case, do all weighings as above but with the 13th coin added to the Right groups, and the KNOWN good coin added to the Left groups. Then if the result is (1 1 1) the 13th coin is heavy, (-1 -1 -1) means the 13th coin is light, other results interpreted normally. Van Luong Nguyen, Network Systems Group (Computer Special Systems), Digital Equipment Corporation.