| From: ROLL::USENET "USENET Newsgroup Distributor" 2-JUN-1984 04:46
To: HARE::STAN
Subj: USENET net.puzzle newsgroup articles
Newsgroups: net.puzzle
Path: decwrl!decvax!harpo!floyd!vax135!houxz!houxm!ihnp4!ihuxe!rainbow
Subject: revised solution to 12 coin puzzle
Posted: Wed May 30 15:46:46 1984
problem:12 coins, one counterfeit. Determine which it is and if its heavier
or lighter. One balance is at your disposal to be used three times.
solution:weigh four vs four, two possibilities.
A:balance, meaning there are now four coins one of which is counterfeit.
1)weigh three of them vs 3 good coins(from other pile of 8)
a.if they balance the odd coin can easily be tested with the last weighing.
b.otherwise weigh one of the three against another. Since we know whether
the counterfeit coin is light or heavy, it can be isolated.
B:imbalance, leaving a pile of 4 light coins and 4 heavy coins.
1)take two light coins,two heavy coins and weigh them against 2 good coins
and 1 light coin and 1 heavy coin.
a.Left side heavy means the counterfeit coin is among the two heavy on
the left or the light one on the right. Weigh the two heavy ones to
isolate counterfeit coin.
b.Right side heavy means the counterfeit coin is among the two light on
the left or the heavy one on the right. Weigh the two light ones to
isolate counterfeit coin.
c.Balance means the counterfeit coin is among the third pile. One heavy
or one light. Weigh either one vs a good one to isolate.
|
| From: ROLL::USENET "USENET Newsgroup Distributor" 3-JUN-1984 03:15
To: HARE::STAN
Subj: USENET net.puzzle newsgroup articles
Newsgroups: net.puzzle
Path: decwrl!dec-rhea!dec-tonto!luong
Subject: Extension and Generalization to the 12 pennies puzzle.
Posted: Fri Jun 1 10:58:57 1984
>> 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.
|
| From: ROLL::USENET "USENET Newsgroup Distributor" 7-JUN-1984 04:44
To: HARE::STAN
Subj: USENET net.puzzle newsgroup articles
Newsgroups: net.puzzle
Path: decwrl!dec-rhea!dec-tonto!luong
Subject: Thoughts on those so-called "toughest" coin weighing puzzles...
Posted: Tue Jun 5 09:08:00 1984
Those so-called "toughest" (!?) coin weighing puzzles recently proposed on this
newsgroup (eg. solve 7 coins in 2 steps, 26 coins in 3 steps, 80 coins in 4
steps) can be MATHEMATICALLY PROVEN to have NO solution!
PROOF:
Given X coins, there are (2X + 1) possibilities any weighing algorithm has to
distinguish among. [These possibilities are explicitly: .All coins true
.Coin 1 heavy
.Coin 1 light
.Coin 2 heavy
.Coin 2 light
.......
.Coin X light ]
In 1 weighing, there are 3 possible outcomes: Equal, Left group heavy, Left
group light. In N weighings, there are (3**N) [3 to the Nth power] possible
different outcomes. For each of these outcomes to be mapped to a SINGLE
UNIQUE case in the (2X + 1) possibilities above, we must have:
(2X + 1) <= (3**N)
or: X <= ((3**N)-1)/2
Thus using N weighings, the maximum X for which a solution is *theoretically*
possible is ((3**N)-1)/2 :
N=number of steps X=maximum number of coins
2 4
3 13
4 40
etc...
In practice, the "artificial" restriction of having to use a *balance* as a
tool, reduces the solvable maximum to one less than the theoretical maximum,
eg. 3 coins in 2 steps, 12 in 3 steps, 39 in 4 steps ..., unless an extra
KNOWN-to-be-good coin is given. (I have recently posted to this newgroup the
general method to find the solution for ((3**N)-3)/2 coins in N steps.)
CHALLENGE:
I am sure readers of this newsgroup are most interested to have the proposer of
these "toughest" puzzles publish his "solutions". To add spice to all this, I
undertake to eat my hat in a public ceremony (-: :^) if a correct and flawless
solution to any of his three puzzles (7 coins in 2 steps, 26 in 3, 80 in 4)
could be published.
(My guess is that the proposer of the "toughest" puzzles has overlooked in his
"solutions" the fact that we do NOT know to start with whether the false coin
is heavier OR lighter than normal.)
Skeptically Yours,
Van Luong Nguyen.
|