Determine counterfeit in a collection of $3^n -1$ coins in n weighings Given a collection of $3^n -1$ coins, where up to one coin is counterfeit (meaning it weighs more than the rest), prove it is always possible to identify which coin is counterfeit using at most $n$ weighings. Here's what I've been trying: I know that when $n = 2$, i.e. in a collection of $8$ coins, it is possible to use $n$ weighings to determine the counterfeit using the intuition that we may exclude two coins and partition the remaining $6$ coins into two groups. We may first weigh these two groups, and weigh two coins in the appropriate group based on the result of this weighing. Unfortunately, however, this approach does not seem to work in the case of determining a counterfeit in a collection of 80 coins, i.e., $\dfrac{78}{2} = 39$, for which if the process is repeated, we will be attempting to split $37$ coins into two equal groups. Any ideas?

**Lemma 1:** Given a colection of $3^n$ coins, where **exactly** one coin is counterfeit (meaning it weighs more than the rest), prove it is always possible to identify which coin is counterfeit using at most $n$ weighings.

**Proof:** Induction by $n$, split the coins into three equal groups.

**Lemma 2:** Given a colection of $3^n-1$ coins, where at most one coin is counterfeit (meaning it weighs more than the rest), prove it is always possible to identify which coin is counterfeit using at most $n$ weighings.

**Proof:** Induction by $n$. To prove $P(n+1)$ split the coins into three groups of $3^n, 3^n$ and $3^{n}-1$ coins.

Weight the two equal groups. If the scale tips, thenyou know that there is an heavier coin on the heavier side, and you can apply Lemma 1.

If the scale doesn't tip, then can eliminate the two groups on the scale and apply $P(n)$.