0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Label each coin with numbers from $0$ to $3^n-1$. Write the labels in base $3$. In round $k$, weight the coins with $0$ in the $k$th digit against the coins with $1$ in the $k$th digit. $\endgroup$ – Thomas Andrews Feb 18 '18 at 2:10
  • 1
    $\begingroup$ With 80: You should leave out 26 coins and split the remains 27-27. (Do you see the pattern?) $\endgroup$ – Alex Zorn Feb 18 '18 at 2:27
1
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

For n=2 you have 8 coins. Divide the coins in 3 groups of 2, 3, 3. compare the two sets of 3 coins.

If they are equal in weight then compare the two remaining ones and pick the heavier. Otherwise, if one set of three coins is heavier, then pick two out of 3 and compare them. If they weigh equal then the third one is the heavy coin, otherwise one of the two was heavier.

For n=3 you have 26 coins. Divide them in three sets of 8,9,9, and proceed as above. Compare the two sets of 9 coins and if one set is heavier divide that set in three sets. Otherwise work with the set of 8 coins.

For n=4 you have 80 coins. Divide them into three groups of 26, 27, 27 and compare the two sets of 27 and go from there.

For larger values of n, the same process works. First divide them into three groups of $3^{n-1}-1$, $3^{n-1}$, $3^{n-1}$ and proceed as above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.