Difference between revisions of "TADM2E 4.46"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
The first solution was so wrong I was compelled to answer this question correctly.
 
The original poster needs to have his posting privileges SEVERELY limited for the sake of limiting stupid activites whenever possible.
 
 
 
Question: You are given 12 coins. One of them is heavier or lighter than the rest. Identify
 
Question: You are given 12 coins. One of them is heavier or lighter than the rest. Identify
 
this coin in just three weighings
 
this coin in just three weighings
Line 11: Line 8:
 
(This template is NOT definitive, there are other solutions that don't follow this template)  
 
(This template is NOT definitive, there are other solutions that don't follow this template)  
  
  Compare  (set 1 & 1st coin from set 4)  against  (set 2 + 2nd coin from set 4)
+
  Compare  (set 1 & 1st coin from set 4)  against  (set 2 + 2nd coin from set 4)
  Compare  (set 1 & 2nd coin from set 4)  against  (set 3 + 1st coin from set 4)
+
  Compare  (set 1 & 2nd coin from set 4)  against  (set 3 + 1st coin from set 4)
 
  Compare  (1st coin from each set)      against  (3rd coin from each set)
 
  Compare  (1st coin from each set)      against  (3rd coin from each set)
  
Line 53: Line 50:
  
 
There are multiple comparison set possibilities, each with their own comparison table solution.
 
There are multiple comparison set possibilities, each with their own comparison table solution.
 +
 +
----
 +
 +
A simpler solution #2:
 +
 +
* put 6 coins on each side of the scale, one side will be heavier.
 +
* use the heavier side from the first weighing and put 3 coins on each side of the scale.
 +
* using the heavier side from the 2nd weighing, pick 2 coins and put 1 on each side of the scale.
 +
 +
If the scale is balanced then the coin you didn't weigh is the heavier one.  Otherwise, the scale will show which one of the other 2 is the heavy coin.
 +
 +
----
 +
 +
Since we do not know if the faulty coin is heavier or lighter , the soluition #2 is not correct
 +
 +
The only solution is solution nr 1, for which we can also use a binary tree
 +
 +
----
 +
 +
I found the explanation at mathforum.org/library/drmath/view/55618.html to be helpful. The key is to build a truth table, but how that table was built is a little tricky because you can't just write out all possible combinations of results and use that. I tried writing a truth table and found that I had to swap some values around to make sure that each measurement step had exactly 4 on each side.

Latest revision as of 23:20, 13 June 2016

Question: You are given 12 coins. One of them is heavier or lighter than the rest. Identify this coin in just three weighings

Solution: Number the coins 1 through 12 and divide them coins into 4 sets of 3...

There are multiple comparison sets possible. This is an acceptable template to find a few of them. (This template is NOT definitive, there are other solutions that don't follow this template)

Compare   (set 1 & 1st coin from set 4)  against  (set 2 + 2nd coin from set 4)
Compare   (set 1 & 2nd coin from set 4)  against  (set 3 + 1st coin from set 4)
Compare   (1st coin from each set)       against  (3rd coin from each set)

A more concise example:

Compare   1 2 3 10  against  4 5 6 11
Compare   1 2 3 11  against  7 8 9 10
Compare   1 4 7 10  against  3 6 9 12

Each weighing can have 3 possible outcomes: Left Heavy, Right Heavy, or Balanced (L,R or B)

Build a truth table to interpret outcomes...many outcomes are not possible. Note: THE TABLE VALUES ARE DERIVED FROM THE CHOSEN COMPARISON SETS!

outcome:    fake coin:
l l l       1 is heavy
r r r       1 is light
l l b       2 is heavy
r r b       2 is light
l l r       3 is heavy
r r l       3 is light
r b l       4 is heavy
l b r       4 is light
r b b       5 is heavy
l b b       5 is light
r b r       6 is heavy
l b l       6 is light
b r l       7 is heavy
b l r       7 is light
b r b       8 is heavy
b l b       8 is light
b r r       9 is heavy 
b l l       9 is light
r l r       10 is heavy
l r l       10 is light
l r b       11 is heavy
r l b       11 is light
b b r       12 is heavy
b b l       12 is light 

There are multiple comparison set possibilities, each with their own comparison table solution.


A simpler solution #2:

  • put 6 coins on each side of the scale, one side will be heavier.
  • use the heavier side from the first weighing and put 3 coins on each side of the scale.
  • using the heavier side from the 2nd weighing, pick 2 coins and put 1 on each side of the scale.

If the scale is balanced then the coin you didn't weigh is the heavier one. Otherwise, the scale will show which one of the other 2 is the heavy coin.


Since we do not know if the faulty coin is heavier or lighter , the soluition #2 is not correct

The only solution is solution nr 1, for which we can also use a binary tree


I found the explanation at mathforum.org/library/drmath/view/55618.html to be helpful. The key is to build a truth table, but how that table was built is a little tricky because you can't just write out all possible combinations of results and use that. I tried writing a truth table and found that I had to swap some values around to make sure that each measurement step had exactly 4 on each side.