3. On the table, there are 100 identical-looking coins, of which 85 are counterfeit and 15 are genuine. You have a miracle tester, into which you can place two coins and get one of three results - "both coins are genuine," "both coins are counterfeit," and "the coins are different." Can you find all the counterfeit coins in 64 such tests? (K. Knop)
Answer. Yes. Solution. We will present one of the possible ways to define the fake coins. Divide the coins into 50 pairs and check all pairs except one. We will learn the number of fake coins in each pair. Since the total number of fake coins is known, we will also learn how many are fake in the remaining pair. We need to determine which coin is fake in each of the pairs consisting of different coins. For this, note that there is a pair where both coins are fake, because there are more than 50 fake coins. Take a coin from such a pair and test it with one coin from each pair where both coins are different. There are no more than 15 such pairs, since we have only 15 genuine coins. Therefore, we used no more than 49+15=64 tests.

Criteria. 1. Only the answer "yes" - 0 points. 2. The solution has two key ideas. The first: divide 100 into 50 pairs, perform 49 pairwise weighings, and show that this is enough to place each pair (including the unweighed 50th) into one of three classes - "2F", "2G", "FG". The second: show how all genuine coins can be found in no more than 15 operations, if the coins are already divided into 50 pairs, and it is known for each pair how many genuine coins it contains. If the solution contains exactly one of these two ideas, it is rated 1 point (even if the answer 64 is given as 65). 3. The fact that among 50 pairs of coins there will definitely be a pair of two fakes, and that the "worst case" when finding genuine coins is when all of them are in different pairs, is considered obvious, and we do not reduce the score for the lack of justification for these statements. The exception is the situation where the "worst case" is considered using the specifics of the number 15, and the reasoning does not transfer without changes to the case of 14 and 13 pairs: in such a case, 1 point is deducted. If the solution involves weighing coins from pairs FG arranged in a cycle, and the solution does not work for the case of one pair FG - no more than 4 points.