Difference between revisions of "4.53"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
(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:
If we are allowed to maintain a second stack on the side, this should be possible.
+
Question: You are given 12 coins. One of them is heavier or lighter than the rest. Identify
The main stack is a regular stack that can be implemented using an array and an index to the top of the stack.
+
this coin in just three weighings
The second stack will stack each entry when it becomes the new minimum, only.
 
When an entry is popped from the main stack, it will be poped from the second stack only if identical.
 
The minimum item is the top of the second stack.
 
  
 +
Solution:
 +
Number the coins 1 through 12 and divide them coins into 4 sets of 3...
  
I think the actual question was about ability of building the stack that has push/pop/extract-min operations as in the queues - the extract removes element. This is impossible - that would give us an opportunity to sort in O(n) time (n O(1) pushes to the data structure, and then n extract-min's)
+
There are multiple comparison sets possible. This is an acceptable template to find a few of them.
--[[User:Kubek2k|Kubek2k]] 05:00, 6 November 2011 (EST)
+
(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 [[Chpater 4]]
+
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