Coin weighting. Suppose one has n coins, among which there may or may one counte

Question

Coin weighting. Suppose one has n coins, among which there may or may one counterfeit coin. If there is a counterfeit coin, it may be either or lighter than the other coins. The coins are to be weighted by a balance. Find an upper bound on the number of coins n so that k weighings will find the counterfeit coin (if any) and correctly declare it to be heavier or lighter. What is the nonadaptive coin weighing strategy for k = 3 weighings and coins. (nonadaptive strategy determines groups of coins for all weighings before the weighing starts)

Explanation / Answer

a) each weighing has 3 possible outcomes: equal, left pan heavier and left pan lighter.

Hence with k weighing there are 3k outcomes. Hence we can diffrentiate between 3k different states.

Hence 2n+1 < 3k

i.e

n < 3k-1/2

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---