KöMaL - Középiskolai Matematikai és Fizikai Lapok
A lap

Rendelje meg a KöMaL-t!


VersenyVizsga portál


Matematika oktatási portál

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 points)

Deadline expired on 10 November 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 29=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 on problem A. 542.
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

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley