- #1
wubie
Hello,
I have encountered a question in my discrete mathematics class and I was wondering if I have solved it correctly. I can't remember the question to the word but I will try my best to state it correctly
You have 15 coins. One is counterfeit. You also have a three pan balance (like a three leaf clover without the stem and balanced where the three leaves meet). If one of the three pans is heavier, then the balance will tip to the heavier pan.
Given that you must pay $100 per weighing , how much must you pay to determine the counterfiet coin? That is, determine the counterfiet coin in as few weighings as possible.
If you can, find a nonadaptive solution.
An adaptive solution is a solution in which the action at each step is adapted to the outcome from the previous action.
A nonadaptive solution is a solution in which all the actions are fully predetermined.
Now I think I have come up with a NONADAPTIVE solution. And I believe that the counterfeit coin can be identified in two weighings.
First, label each coin 1 to 15. Then construct a table with a row from 1 to 15 (the number of each coin):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Under each numbered coin put a one if it is in the heavier pan. If not, put a zero.
First weighing:
Divide the fifteen coins into four groups; three groups of four, and one group of three.
Group one: 1,2,3,4
Group two: 5,6,7,8
Group three: 9,10,11,12
Group four: 13,14,15.
Weigh groups one to three against each other. Leave group four alone.
Record a one underneath the coins which are part of the heavy pan.
Second weighing:
Group one: 1,5,9,13
Group two: 2,6,10,14
Group three: 3,7,11,15
Group four: 4,8,12.
Once again weigh groups one to three against each other and leave group four alone.
Record a one underneath the coins which are part of the heavy pan for the second weighing.
Now look at the table. The coin with two ones underneath should be the counterfeit coin.
EXAMPLE: Let's say that 11 is the heavy coin. But we don't know it yet. Now execute the above algorithm.
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 | Numbered Coins
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 | First weighing
0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 | Second weighing
As you can see, there are two ones underneath the coin numbered 11. Which is exactly what we want.
Does this seem like a solid, nonadaptive solution?
Any thoughts on the subject are appreciated. Thankyou.
I have encountered a question in my discrete mathematics class and I was wondering if I have solved it correctly. I can't remember the question to the word but I will try my best to state it correctly
You have 15 coins. One is counterfeit. You also have a three pan balance (like a three leaf clover without the stem and balanced where the three leaves meet). If one of the three pans is heavier, then the balance will tip to the heavier pan.
Given that you must pay $100 per weighing , how much must you pay to determine the counterfiet coin? That is, determine the counterfiet coin in as few weighings as possible.
If you can, find a nonadaptive solution.
An adaptive solution is a solution in which the action at each step is adapted to the outcome from the previous action.
A nonadaptive solution is a solution in which all the actions are fully predetermined.
Now I think I have come up with a NONADAPTIVE solution. And I believe that the counterfeit coin can be identified in two weighings.
First, label each coin 1 to 15. Then construct a table with a row from 1 to 15 (the number of each coin):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Under each numbered coin put a one if it is in the heavier pan. If not, put a zero.
First weighing:
Divide the fifteen coins into four groups; three groups of four, and one group of three.
Group one: 1,2,3,4
Group two: 5,6,7,8
Group three: 9,10,11,12
Group four: 13,14,15.
Weigh groups one to three against each other. Leave group four alone.
Record a one underneath the coins which are part of the heavy pan.
Second weighing:
Group one: 1,5,9,13
Group two: 2,6,10,14
Group three: 3,7,11,15
Group four: 4,8,12.
Once again weigh groups one to three against each other and leave group four alone.
Record a one underneath the coins which are part of the heavy pan for the second weighing.
Now look at the table. The coin with two ones underneath should be the counterfeit coin.
EXAMPLE: Let's say that 11 is the heavy coin. But we don't know it yet. Now execute the above algorithm.
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 | Numbered Coins
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 | First weighing
0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 | Second weighing
As you can see, there are two ones underneath the coin numbered 11. Which is exactly what we want.
Does this seem like a solid, nonadaptive solution?
Any thoughts on the subject are appreciated. Thankyou.
Last edited by a moderator: