Finding a faulty coin among 9 with a balance scale in 3 weighings

[geniusprahar_21]

you have 9 coins. one of these coins is faulty, that is it is either heavier or lighter than the rest. you have a weighing balance. in thre weighings you have to find
1. which is the faulty coin and
2. is it heavier or lighter.

 

[quark]

Make into three groups. Compare 1,2 and 1,3 groups and you will come to know which group has the wrong coin and whether it is lighter or heavier. After identifying the group take two coins out of it and weigh. If they are equal then third coin is fualty. If unequal, you will come to know it based on our first and second weighings

 

[NateTG]

OK, this worked for the poison bottles question, so let's try it here:
What happens if we have one coin that is light, and another that is heavy?

 

[geniusprahar_21]

we can work that out to... maybe in 4 tries

 

[TenaliRaman]

we can work that out to... maybe in 4 tries

Procedure?

-- AI

 

[ArielGenesis]

quark, can you explain the last bit
If unequal, you will come to know it based on our first and second weighings

 

[quark]

If a,b and c are the three groups then weighing a agianst b first and then with c(in each pan of the balance) will tell us whether weight of one coin is more or less. If group a and b are equal in weight then if c goes down the weight is more and vice versa. If a and b are different then you will come to know it when you weigh c against a or b. Suppose the weight is more then in the third round, which side goes down has the wrong coin.

 

[xJuggleboy]

If a,b and c are the three groups then weighing a agianst b first and then with c(in each pan of the balance) will tell us whether weight of one coin is more or less. If group a and b are equal in weight then if c goes down the weight is more and vice versa. If a and b are different then you will come to know it when you weigh c against a or b. Suppose the weight is more then in the third round, which side goes down has the wrong coin.

Even if this did work you still have not identified which is the wrong coin... Only which pile it is in...

 

[NateTG]

Finding both the heavy and the light coin takes at least 5 tests. (Finding either individually *may* be possible in 3.)

 

[Greg825]

Based on the responce of juggle I don't know whether the original puzzle has already been solved but here's my shot at it. don't read further if you're still solving it.

in short you take three groups of three to start with, then end up reducing one group into three single coins:

take three groups of three, a, b and c.

weigh a and b

if a==b
- divide group c into three groups of one, aa bb cc
- weigh aa and bb
- if aa==bb
--cc is the faulty coin, compare with any coin , to determine whether it is heavier or lighter. done.
- if aa!=bb
-- cc is a legit coin, weigh cc and aa.
-- if cc==aa, bb is the faulty coin, the result from measurment two will tell if it's heavier or lighter. done.
-- if cc!=aa, aa is the faulty coin, and this measurement also tells whether it is heavier or lighter. done.

if a!=b
- weigh a and c
- if a == c
-- b contains faulty coin, divide it into three single coins and measure any two to determine the faulty coin. the first measurement will detremine whether it is heavier or lighter. done.
- if a!=c
-- "a" contains faulty coin, divide it into three single coins and measure any two to determine the faulty coin. the first measurement will detremine whether it is heavier or lighter. done.

 

[quark]

xjuggleboy,

You might not have read my first post.

Say, you weigh a and b first and got equal weight. Weigh a and c and if c goes down then the coin is heavy. If a and b are unequal, weigh a and c. Either a and c or b and c should be equal and tend to move in the same direction. So you can alwasy find out which group has the wrong coin and whether it is of more weight or less. Say, we got the group a with a heavy coin.

Now take any two coins of a and put them in the two pans of the balance. If they are equal then the third coin is faulty and weighs more. If they are unequal then one pan should go down.

Similar solution is given above.

 

[geniusprahar_21]

Finding both the heavy and the light coin takes at least 5 tests. (Finding either individually *may* be possible in 3.)

Procedure?...

 

[TenaliRaman]

Hmm,
Divide the coin set into 5 groups,
2+2+2+2+1
Label these group as A,B,C,D and E.

Step 1. Compare A and B
Step 2. Compare C and D

Case 1 : A==B, C==D
implies both heavy and light coins have ended up in the same group
interchange one coin from A with one coin in B &
interchange one coin from C with one coin in D

Step 3. Compare A and B
Step 4. Compare C and D
The heavy and light coins would have been identified by now

Case 2 : A==B, C!=D (WLOG, A!=B and C==D is symmetric to this case)
implication
Case 2.1 Both C and D have one bad coin each
Case 2.2 One of either C or D has a bad coin and the other bad coin is E
Step 3. Take one coin from A and compare with E
This should identify which of the case 2.1 or 2.2 we are handling.
For case 2.1,
First of all, we know which of C and D is heavier or lighter.
Step 4. Compare coins of C against each other
Step 5. Compare coins of D against each other
The heavy and light coin will have been identified by now

For case 2.2,
From Step 3 we know whether E is heavier or lighter and since C!=D, the tilt during this comparison would tell us which is the bad group. If X is the bad group then,
Step 4. Compare coins of X against each other

Case 3 : A!=B and C!=D
Implications,
One of A and B is bad
One of C and D is bad
Step 3. Compare A against C
Step 4. Compare A against D
If A is good (in which case one of A==C or A==D will be true), then we would come to know from these steps which groups are bad and which are heavier or lighter. If A is bad (in which case both A!=C and A!=D will be true), then we would come to know whether A is heavier or lighter and we also would find the other group and also would find out whether it is heavier or lighter.
If X and Y group are found to be bad and we know which of X and Y is heavier or lighter then,
Step 5. Compare coins of X against each other
Step 6. Compare coins of Y against each other
The heavier and lighter coins would have been known by now.

So at the most it seems, we will take 6 comparisons and at the best it can work out in 3 comparisons.

-- AI

 

[NateTG]

Procedure?...

No idea. Those are lower bounds.