Suppose you have a set of 13 coins, one of which is counterfeit (lighter). Draw a tree to show how you can figure out the counterfeit coin using an unlabelled balance using the fewest number of comparisons.
I'd appreciate any help with this..
2007-04-28 16:23:36 · 5 answers · asked by ymcabookwormcat 3 in Science & Mathematics ➔ Mathematics
Compare any 6 coins with any other set of 6. If they weigh the same, then the 13th coin is counterfeit. You are done in one step!
Otherwise take the lighter set of 6 and split into 2 groups of 3.
Take the lighter of those two sets.
Now you have 3 coins. Compare two of those. If they are the same, then the 3rd one is the bad one, otherwise the lighter of the two is the bad one!
This is 3 compares to find the counterfeit in 13 coins.
2007-04-28 16:30:43 · answer #1 · answered by ZeroCarbonImpact 3 · 0⤊ 0⤋
I'm lousy on these type problems. Try this routine"
1) select 6 coins. place 3 on each side. If they balance, all are good. If they don't:
select 4 of the 6 coins, put 2 on each side. If they balance, they are all good. If they don't:
select 2 coins from ONE side from the previous weighting. If they balance, they are good. If not, take one of the coins and a previous "good"
coin and weight them. If they balance, the other coin is counterfeit. If they dont balance, the coin selected from the last balance is counterfeit
2) if the first 6 coins balanced, select another 6 coins and try it again. Follow the routine above to track down the counterfeit coin. However, if the 6 coins balance, the unweighted coin is counterfeit.
2007-04-28 23:36:42 · answer #2 · answered by cattbarf 7 · 0⤊ 1⤋
First you should take out one coin and split the rest into 2 which makes a group of 1 coin 6 coins and 6 coins. weight the 6 coins first and then weight the other one. Split the lighter group in 2 and weight again take the lighter side and split it into two groups of 2 coins and 1 coin, weight them and then switch one coin to the other side and make a 1 coin to 2 coin, then weight. take the side with the less combined weight and weight each of them seperately. The one with less weight is the one. Or if you start off with an equal balance with the 6 and 6 coins, the 1 coin you pulled out is already the lighter one.
2007-04-28 23:32:28 · answer #3 · answered by UnknownD 6 · 0⤊ 0⤋
I don't know how to draw a decision tree but I can tell you how to do it. Start by weighing four coins on either side of the balance with five left out. If they balance, the odd coin is in the five you left out. Weigh two of them on either side. If they balance, the odd coin is the one you haven't weighed yet. If they don't balance, weigh one of the two on the light side against a good coin. If it balances, it's good and the other is counterfeit. If it doesn't balance, it's counterfeit.
If the first weighing doesn't balance, then you know the counterfeit coin is in the four on the light side. Weigh two of these on either side of the balance, then weigh one of the light ones against a good one, just as you did before (except you don't have a fifth coin to leave out).
You can figure it out in only three weighings. If you get lucky (a 1-in-13 chance) you may get it in just two.
2007-04-28 23:30:39 · answer #4 · answered by Amy F 5 · 0⤊ 1⤋
dunno about the tree thing, but here's how I'd do it:
1. divide into 3 groups of 4, leaving 1 out
2. weigh one group against another
if they weigh the same, neither contains the fake
if one is lighter, then separate into groups of two and weigh them against each other, and take the lighter group of coins and weigh them against each other
3. If they weighed the same, take the next group and divide it up into two
if they weigh the same, then logically the one by itself is the fake
if one is lighter, then weigh the coins against each other
I think 3 or 4 would be the max. number of weighings
2007-04-28 23:31:40 · answer #5 · answered by musics_my_world 2 · 0⤊ 1⤋