There are n >= 3 coins that are numbered from 1 to n, but are identical in appea

Question

There are n >= 3 coins that are numbered from 1 to n, but are identical
in appearance otherwise; either all are genuine or exactly one of them is fake. The
fake coin does not have the same weight as the genuine ones, but it is unknown
whether it is lighter or heavier. You also have a balance scale with which you can
compare any two sets of coins. That is, by tipping to the left, to the right, or staying
even, the balance scale will tell you whether the sets weigh the same or which of the
sets is heavier than the other, but not by how much. You wish to find whether all
the coins are genuine and, if not, to find the fake coin and establish whether it is
lighter or heavier than the genuine ones.
This can be represented in a ternary decision tree. What would the decision tree look like?

Explanation / Answer

if n is even then divide the two into two equal parts of size n/2 and n/2. and weigh on the balance. if n is odd divide into two parts of n/2 and n/2 and keep the third coin aside. in any of the above cases, if the scale does not balance, recurse seperately on contents of both the pans. if it balances, reject both the pan contents. Do not forget that you also have a third smaller pile getting built up from the odd pile cases. perform the same operation on this too. in each case when you have two coins on the pan and they do not balance the beam, weigh each against any third random coin and check which of the two still does not balance. This one must be the culprit!

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.