The general
solution is as follows:
Let S(n)=3^0+3^1+3^2+ .... +3^n. It can be shown that 3*S(n) marbles take (n+2)
weighings. The procedure is the same for any value of n where you can demonstrate
that in two weighings the problem either reduces to the case of (n-1) after 1 weighing or
3^n marbles where you know whether the marble is lighter or heavier.
In this latter case it is simply a matter of balancing 3^(n-1) against 3^(n-1) to reduce
it to the case of 3^(n-1) in (n-1) weighings. Clearly the culprit can be found in n
weighings. In the first case you eventually reduce to the case of n=0 or 3 marbles
in 2 weighings. In this case balancing 1 against 1 gives a normal marble to check
against the unknown marble or marbles requiring one more weighing. For the general case
balance S(n) against S(n).
Case 1 - The groups balance :
The marble is in the S(n) not used. Take 3^n from this group and balance against 3^n
normal marbles. If they don't balance you have 3^n marbles where you know if the
coin is lighter or heavier. If they balance you have S(n-1) marbles containing the
coin. This is one of the possibilities after 1 weighing for the case of (n-1).
Case 2 - The groups do
not balance :
Put 3^n from the heavier group and S(n-1) from the lighter group on the LHS and balance
them against the remaining S(n-1) from the heavier side and 3^n from the normal coins in
the third group on the RHS. If the LHS is heavier then the coin is heavy in the 3^n
heavy group coins. If they balance then the coin is lighter in the remaining 3^n
lighter side coins. If the RHS is heavier then you have two unbalanced groups of
S(n-1) coins which is one of the possibilities after 1 weighing for the case of (n-1).
The solution for 12 (or n=1) is a follows: Balance 4 against 4.
Case 1 - They balance :
Take 3 from the third group and balance against 3 normal coins. If they balance the
other coin is the one and can be checked against a normal coin. If they don't
balance then you have 3 coins where you know if the coin is lighter or heavier. Balance 1
against 1; if they balance you the remaining coin is the one whilst if they don't balance
you know the odd coin since you know if it is lighter or heavier. If the groups of 3
balance then the remaining coin is the one and can be checked by balancing it against a
normal coin. Case 2
- They do not balance
Balance 3 heavier side and 1 lighter side on LHS against the other heavier side coin and 3
normal coins. If the LHS is heavier then the coin is heavier in the 3 heavier side marbles
(one weighing is required as in Case 1). If they balance then the coin is lighter in
the 3 remaining lighter side coins (again one weighing finds the coin). If the RHS
is heavier then either the lighter side coin on the LHS is lighter or the heavier side
coin on the RHS is heavier. Balance one of these against a normal coin to get the
culprit in one weighing."
|
|
Back