Difference between revisions of "4.53"
(Created page with "If we are allowed to maintain a second stack on the side, this should be possible. The main stack is a regular stack that can be implemented using an array and an index to the...") |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | + | 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) | ||
| − | Back to [[ | + | 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. | ||
| + | |||
| + | |||
| + | |||
| + | Back to [[Chapter 4]] | ||
Latest revision as of 18:37, 20 September 2020
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.
Back to Chapter 4
