Maths Olympiad Prep

Library / /163 of 520

Combinatorics Difficulty 5.0 AIME, harder Find the answer

5. Given 2023 identical-looking coins, among which there are two counterfeit coins of the same weight, and the remaining 2021 coins are genuine and of the same weight. The counterfeit coins weigh differently from the genuine coins. Now, you only want to know whether a counterfeit coin is heavier or lighter than a genuine coin (without distinguishing which is the counterfeit), using a balance scale to solve this problem. Then, the minimum number of weighings required is:

Pick one

Solution

5. B.

Take out a coin and place it elsewhere, then divide the remaining coins into two groups AA and BB (each group has 1011 coins), and let W(N)W(N) represent the total weight of the coins in group NN.

For the first weighing, compare W(A)W(A) with W(B)W(B). Assume W(A)W(B)W(A) \geqslant W(B), then divide group AA into three subgroups CC, DD, and EE (each subgroup has 337 coins), and perform two more weighings to compare W(C)W(C) with W(D)W(D), and W(D)W(D) with W(E)W(E). The following discussion is divided into two cases.
(1) When W(A)=W(B)W(A)=W(B), group AA and group BB each contain one counterfeit coin. Among the three subgroups CC, DD, and EE, there is one subgroup that has a different weight from the other two. This subgroup is heavier, so the counterfeit coin is heavier. Otherwise, the counterfeit coin is lighter.
(2) When W(A)>W(B)W(A)>W(B), then only one of the groups AA or BB contains a counterfeit coin.
(i) If W(C)=W(D)=W(E)W(C)=W(D)=W(E), then group AA does not contain a counterfeit coin, and group BB contains one or two counterfeit coins. Therefore, the counterfeit coin is lighter.
(ii) If W(C)W(C), W(D)W(D), and W(E)W(E) are not all equal, then group AA contains at least one counterfeit coin, and group BB does not contain a counterfeit coin. Therefore, the counterfeit coin is heavier.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.