# How many ways to iterate? [duplicate]

There are 9 coins, out of which one is odd, i.e. its weight is either less or more than that of the other 8 coins. How many iterations of weighing using a pan balance are required to find the odd coin and to find whether it is heavier or lighter?

We need

three weighings.

We are trying to distinguish between

9x2=18 possibilities, and a single weighing gives one of three results, so we certainly need at least three weighings.

Let's begin,

as n_palum does, by dividing our coins into three sets of three, and weighing one against another. Six possibilities remain in either case.

Now:

If our two sets balance exactly, then we have three coins A,B,C left, and one of them is the odd one out. Weigh A against B. Now we know either A heavy / B light, or C heavy/C light. In either case, weighing A against C will finish the job.

On the other hand:

If our two sets don't balance, we have six coins A-F and we know that either one of A,B,C is heavy or one of D,E,F is light. Weigh A+D against B+E. If A+D is heavier then either A is heavy or E is light; weigh A against, say, C and we're done. Similarly if B+E is heavier (this time we'll need to weigh, say, B against C). And if A+D balances B+E then either C is heavy or F is light; again, weighing A against C will finish the job.

It requires:

A maximum of 4 weighings. It could be found in 3 as Gareth pointed out.

Explanation:

Divide the 9 coins into sets of 3 each. Let them be Set 1, Set 2 and Set 3. Weigh Set 1 and Set 2 against each other. If they weigh equal, then Set 3 contains the odd coin. Otherwise, weigh Set 1 against Set 3. If they weigh equal, Set 2 contains the odd coin. If in both cases, they do not weigh equal, then Set 1 contains the odd coin.
Having identified the set with the defective coin in 2 weighings. Repeat this process on individual coins of the found set. This requires a max of 2 more weighings (but could be done in 1). Hence, the odd coin can be found in a maximum of 4 weighs at all times.

• why to divide in 3 sets?
– nrb
Commented Jun 19, 2017 at 13:22
• @nrb I'm sure there are other ways to get to this. This is one. Commented Jun 19, 2017 at 13:27
• There's a typo in this answer. Commented Jun 19, 2017 at 13:52

Divide the coins into three sets of three. Weigh the first and the second and weigh the second and the third. This will tell you in which set the coin is in and if its heavier or lighter.

From the odd set out take two coins and weigh them. If they are the same then third coin is odd. Else its the one heavier/lighter as per weighing the three sets.

Max weighting = 3.

• Welcome to Puzzling! (Take the Tour!) How does your answer add to the identical ones already given? You should always look at existing answers before providing one of your own, to ensure you are not just adding a duplicate. By the way. we generally put Spoiler tags around answers to avoid revealing the answers to someone who wants to try to solve the puzzle on their own.
– Rubio
Commented Jun 19, 2017 at 15:41

Maximum

4.

Strategy

Number the coins 1 to 9.
weigh 1,2,3,4 against 5,6,7,8. (weighing 1)
If they are balanced, then 9 is the culprit and we are done.
else :
Weigh 1,2,3 against 4,5,6. (2)
If they are balanced then 7 or 8 is fake.
Weight both of them against 9 and you find the answer. (3 and 4)
if 1,2,3 against 4,5,6 are not balanced
weigh 1 and 5 against 2 and 4. (3)
If they are balanced then 3 or 6 is fake.
swap 4 with 3 on the previous step (4th). If it's balanced then 6 is fake, if not then 3 is fake.
If 1 and 5 is not balanced with 2 and 4.
if the side that is heavier is the same as the heavier side in step 2 it means switching sides for 2 and 5 did nothing. so the coins are fair. If the heavy side is the other one it means 2 or 5 is fake.
now we have one more weighing to find one out of 2 coins.
weigh one coin in the "wrong" group with coin 9. (4th)
if they are balanced, it's the other one. If not, it's the one you chose.