XXIX Rioplatense Mathematical Olympiad

The answer is $k=21$. First we show a strategy that allows us to identify the two fake coins using the scale $21$ times. We label the coins with the numbers $1,2,3,\dots ,2022$ written in binary. Since $2^{11}=2048>2022$, every coin corresponds to an $11$-digit binary number. The first $11$ weighings are as follows: for each $k=1,2,\dots ,11$, in the $k$-th weighing we put on the scale those coins whose $k$-th digit is a $1$. The total weight will be even if and only if either both or none of the fake coins are on the scale, i.e., if their $k$-th digits are equal. Since the two fake coins are assigned different binary numbers, there is at least one position where one coin has a $1$ and the other has a $0$. Therefore, we can guarantee that in at least one of these $11$ weighings the total weight is odd. Suppose this happens in weighing number $a$. Then one of the fake coins, $F_1$, has a $1$ in the $a$-th digit, whereas the other fake coin, $F_2$, has a $0$ in the $a$-th digit. Furthermore, notice that with these first $11$ weighings we already know for each $k$ if the $k$-th digits of $F_1$ and $F_2$ are equal or different. Therefore, if we are able to identify $F_1$, then we can identify $F_2$ as well without any additional weighings. Now we make $10$ more weighings, which are as follows: for each $b=1,2,\dots ,11$, $b\ne a$, we put on the scale those coins whose $a$-th digit and $b$-th digit are both equal to $1$. Clearly, $F_2$ is not involved in any of these weighings, so the total weight is odd if and only if $F_1$ is on the scale, and this happens if and only if the $b$-th digit of $F_1$ is a $1$. So, by observing these $10$ weighings we can identify $F_1$ (because we already knew the $a$-th digit, and now we know all the other digits). By our previous observation, this allows us to identify both fake coins. To complete the solution we must prove that $20$ or fewer weighings may not be enough to find the fake coins. We say that a pair of coins is a candidate if, given the information that we have at a certain point, it is possible that those two are the fake coins. For each $k$, $k=0,1,2,\dots ,20$, let $S_k$ be the set of all candidates after $k$ weighings. A strategy will be successful if $S_{20}$ contains only one pair of coins, i.e., the fake coins are determined after $20$ weighings. Initially we have $S_0$, which is the set of all pairs of coins, whose cardinality is equal to $\left(\genfrac{}{}{0ex}{}{2022}{2}\right)$, which is greater than $2^{20}$. Now, the key observation is the following. After the first weighing, the set $S_0$ is partitioned into two subsets, one containing all possible pairs of fake coins for which the first weighing would be odd, and the other containing all possible pairs of fake coins for which the first weighing would be even. The largest of these two subsets has at least half the cardinality of $S_0$, and it is of course possible, no matter what the first weighing was, that $S_1$ is the largest of the two subsets. Now we keep going in the same way: in every weighing, it is always possible that the cardinality of $S_{k+1}$ is at least half the cardinality of $S_k$. Hence, there is at least one configuration where the cardinality of $S_{20}$ is greater or equal to $\frac{\left(\genfrac{}{}{0ex}{}{2022}{2}\right)}{2^{20}}>1$. This means that no strategy that uses the scale only $20$ times can be always successful. This completes the proof.