Problem A. 542. (October 2011)

A. 542. We have 1000 coins, but 100 of them are counterfeit. We know the weight of the real coins and it is known that the counterfeit coins are lighter than the real coins, but they may have different weights. Using a scale we want to find a counterfeit coin. Every time we can measure the total weight of a subset of the coins; the result indicates whether that set contains a counterfeit coin or not. How many measures are needed to find a counterfeit coin for sure?

(Suggested by Dömötör Pálvölgyi, Budapest)

(5 pont)

Deadline expired on November 10, 2011.

Solution (outline). Using the usual halving method, 10 tests are sufficient to find a counterfeit coin. We show that 9 is not enough.

Suppose that we have an algorithm which, after at most 9 tests, selects one of the coins. If this algorithm uses random choices then we can prescribe these choices; so we can assume that our algorithm is deterministic.

Every possible "run" of the procedure can be encoded by a yes-no sequence of length at most 9. If the algorithm finishes earlier, add extra "yes"s. Then all possible run and all results are encoded by 9-long yes-no sequences.

Since there are only 2⁹=512 yes-no sequences, our algorithm can select only 512 coins. If the counterfeit cons are among the other 488 coins, the algorithm cannot give a correct answer.

Statistics:

15 students sent a solution.
5 points:	Ágoston Tamás, Janzer Olivér, Mester Márton, Omer Cerrahoglu, Strenner Péter.
4 points:	Bodnár Levente, Gyarmati Máté.
2 points:	3 students.
1 point:	2 students.
0 point:	3 students.

Problems in Mathematics of KöMaL, October 2011