You can split the coins into 3 groups, each of them has 3 coins. Weigh group 1 vs group 2, if one is lighter, that group has the fake coin. If both groups weigh the same, then group 3 has the fake coin.

Continue to split the group that has the fake coin into 3 groups, each group has 1 coin. Now apply the same procedure and we can identify the fake coin.

Total of scale usage is 2

b) if you have $3^n$ coins then you can apply the same approach and find the fake coin with just n steps. By splitting up to 3 groups each step, after each step you should be able to narrow down your suspected coin by 3 times.

Step 1: you narrow down to group of $\frac{3^n}{3} = 3^{n-1}$ coins

Step 2: you narrow down to group of $\frac{3^{n-1}}{3} = 3^{n-2}$ coins

Step 3: you narrow down to group of $\frac{3^{n-2}}{3} = 3^{n-3}$ coins

...

Step n: Step 1: you narrow down to group of $3^{n-n} = 3^0 = 1$ coin

8 0

3 years ago