find the no. of minimum possible no. of weighings required to find a counterfeit coin out of 80 coins. explana

Question

i have received many gud answers( even the funny suggestions r appreciated here ) but the deal is the detail of counterfeit coin is unavailable. it is not known whether it is heavier or lighter. so now try this out and trust me...the no. of possible ways is 4 only.

Answer 1

[Edited after I found a way to do this in 5 weighings instead of 6]

If you know ahead of time whether the counterfeit coin is heavier or lighter than the good coins, you can find it in 4 weighings in the manner Eulercrosser described. However, if you don't know if the counterfeit is heavier or lighter, it will take 5 weighings to find it. Here's how:

Divide the 80 coins into four groups.
Group A: 26 coins,
Group B: 26 coins,
Group C: 26 coins, and
Group D, 2 coins.

For the first two weighings, weigh A versus B, then weigh A versus C.
If A = B and A = C, the counterfeit is in D and you can find it in one more weighing. Weigh one coin from D versus a known good coin. If they're the same, the counterfeit is the other coin in D. If they're different, then the counterfeit is the coin you chose from D.

In each of the other cases, you've narrowed down the counterfeit to one group of 26 and you'll know whether the counterfeit is heavier or lighter.
If A = B and A < C, the counterfeit is in C and is heavier than the rest.
If A = B and A > C, the counterfeit is in C and is lighter than the rest.
If A < B and A = C, the counterfeit is in B and is heavier than the rest.
If A < B and A < C, the counterfeit is in A and is lighter than the rest.
If A > B and A = C, the counterfeit is in B and is lighter than the rest.
If A > B and A > C, the counterfeit is in A and is heavier than the rest.

From here, you can find the counterfeit in 3 more weighings, in the manner Eulercrosser described:

Add a known good coin to the group of 26, making a group of 27 coins.
Weigh 9 versus 9... if they're the same, the counterfeit is in the other 9; if they're different (and you now already know whether the counterfeit is heavier or lighter), you'll know which group of 9 has the counterfeit.
Weigh 3 versus 3 from the bad 9 to find the bad 3.
Weigh 1 versus 1 from the bad 3 and you've got yourself a counterfeit.

Answer 2

80. If you only have a small amount of counterfeit coins, or in the extreme case, only one, then you will need to weigh them all. The methodology is this. As you are weighing the coins, you plot their values on a number line. All of the weights should be clustered around a particular value. In the end, if the counterfeit has a different weight, then you will see a point that is removed from the rest. Perform a Q-Test to determine whether or not the outlier can be removed. If it can, then that coin is almost certainly your counterfeit. The reason you would need to measure 80 is that if there is only one coin, then even if your sample size was 79, there still is a chance of missing it (it would be the 80th coin).

If you have a large number of counterfeits, then the number that you will need to weigh will depend. For argument's sake, weigh all of the coins. Then plot a histogram of the weights. Assuming that you are using a sufficiently sensitive scale, the results should be normally distributed. If the counterfeit coin is significantly heavier or lighter than the others (>3 sigma) then you should notice a second distribution. From this you should be able to find the weight of the counterfeit coins and then be able to remove them.

Answer 3

Assuming that you know that the counterfeit coin is heavier:

Break the coins into 3 groups (27, 27, and 26). Weigh the two groups of 27. If they are equal, then you know that all of the coins on the balance are real. Thus the counterfeit coin must be one of the 26. Add one of the real coins to the 26, so that you have a group of 27. If the two groups of 27 you put on the balance, do not balance, then you know it is in the heavier group. Either way, you will know that the counterfeit coin is in a group of 27 (either one of the original groups of 27 or in the group of 26+1).

Split the group of 27 (with the counterfeit) into three groups of 9. Balance two groups. If they balance, then the counterfeit is in the third group. If they don't balance, then the counterfeit is in the heavier group. Either way, you now know that the counterfeit is one of 9 coins.

Split the group of 9 coins into 3 groups of 3. Balance two of the groups. If they balance, you know the coin is in the third group, if they don't then it is in the heavier one. Either way, you now have the coin narrowed down to three coins.

Balance two of the three coins. If they balance, then the counterfeit coin is the third coin. If they don't balance, then the counterfeit coin is the heavier one.

You have found the coin in 4 balances.


If you don't know if the coin is heavier or lighter, then it will take more balances:

First start off by weighing two coins together. If they are not equal, then you know the counterfeit is one of those two coins. Choose another coin and weigh it with one of the two original coins. If they balance, then you know it is the original coin that was weighed only once. If they don't balance, then you know that it was the original coin that was weighed twice. Either way you found the coin in two balances.

If the original coins are equal, then you know that it is not one of those two coins (and have used one balance). Call these two coins X and X.

Again, split all of the coins (80) into 3 groups (27, 27, 26) placing one of the original coins in each group of 27 (and remembering it). Balance the two groups of 27 together. If they are equal then the group of 26 has the counterfeit coin. Now add one coin to the group of 26 and balance it to a group of 27. If the group of 26+1 weighs more, then the counterfeit coin weighs more, and you can follow the method above starting at 27 coins (for a total of 3+3=6 balances). If the group of 26+1 weighs less, then you can do the same (except now you know the counterfeit weighs less and not more), again 6 balances.

If the two groups of 27 don't balance, then one is heavier than the other. Leave the heavier group on the balance and add the group of 26 and the X that wasn't in the heavier group. We know that X is real and that the group of 26 are all real. If the heavier group of 27 and the group of 26+X balance, then you know that they are all real, and the counterfeit coin is in the lighter group of 27 (and therefore the counterfeit coin is lighter). Now you can apply the above procedure for a total of 3+3=6 balances.
If the heavier group of 27 and the group of 26+X don't balance, then you know the coin is in the heavier group, and is thus heavier. Again, you can apply the above procedure for a total of 6 balances.

Therefore the minimum (that I have found) number of balances REQUIRED (it can be done in less, but that depends on chance) is 6 balances if you don't know if the counterfeit is heavier or lighter and 4 balances if you do know.

If you have 80 real coins and 1 fake coin, you can actually find the fake coin in only 5 balances maximum. Weird that the more coins you have, sometimes the easier it is to find the fake.

Answer 4

Lets break this down:

Split the coins into equal groups. One will always be heavier (the one with the counterfeit coin). That group then gets halved, and that continues until you are down to two coins - one is real and the other is the counterfeit.

2x40
2x20
2x10
2x5
Now you have an odd number of coins. You can weigh 4 of the coins (2x2). If they come out even, you know the odd coin is the counterfeit. If one of the groups of 2 is heavier, continue to one more weighing
2x1

Hence, the minimum number of weighings needed to know without a doubt is 6. You could luck out and get it in 5, but that is only a 20% chance of that happening.

Hope that helps.

Answer 5

2

Answer 6

2
first take two coins weigh them against each other
if one weighs less take another coin and weigh it against one of the first two. The one that is different is the counterfeit.
This is the minimum if you get lucky and get the counterfeit coin in the first three coins. The number of total coins does not matter.
If on the other hand the number of coins matters. the answer is 5 or 6. divide the coins into stacks of 20. weigh them against each other(2). Take the one that is different( you now know if the counterfeit is lighter or heavier than the others) and split it in two stacks. weigh the resulting stacks against each other(3). Take the one with the counterfeit coin and divide again by two. weigh against each other(4). This leaves you with five coins. Take two coins and weigh against two others of the five(5). if same the remaining coin is counter feit. If different, divide the two coins into one each and weigh again(6).

Answer 7

you start out by with the weight of a legitimate coin. then you split the 80 coins into 2 groups of 40. the group that weighs 40 times the legitimate weight is eliminated. next you split into 2 groups of 20 and eliminate the odd weight
which leaves you 2 groups of 10. you repeat the operation which leaves you 2 groups of 5. at that time you divide them 2, 2 & 1. if the groups of 2 are equal it is the single coin. if they are not you need 1 more operation. so the absolute minimumis 5 but could be 6 depending on how the split comes out..

Answer 8

not enough information.
Do I know whether or not the counterfeit coin is heavier or lighter than the real ones?

Answer 9

To get the answer. Go to the nearest telephone and carry the reciever outside. Yell the problem into the sky and then swing and dance in circles with the reciever while clucking like a chicken.

Answer 10

I also have a feeling it fairly is the sq. root of N. can no longer clarify why, that's purely a droop....and a few thing to do with halfing. not sure the thank you to describe what's happening interior my head