Anzhans A.

There are 100 silver coins, ordered by weight, and 101 gold coins, also ordered by weight. It is known that all coins have different weights. We have a two-pan balance that allows us to determine which of any two coins is heavier. How can we find the coin that ranks 101st in weight among all the coins with the fewest number of weighings?
Let's prove that if from $n$ silver and $n$ gold coins, the $n$-th by weight coin can be found in $k$ weighings, then the $2n$-th by weight coin can be found in $k+1$ weighings from $2n$ silver and $2n$ gold coins.

Indeed, suppose the $n$-th silver coin is heavier than the $n$-th gold coin. Then the $n$ first silver coins occupy places by weight above the $2n$-th, as they are heavier than

$n$ silver and $n+1$ gold coins. On the other hand, the $n$ last gold coins must occupy places below the $2n$-th, as they are lighter than $n$ gold and $n$ silver coins. Therefore, the sought coin is among the remaining $n$ lighter silver and $n$ heavier gold coins and occupies the $n$-th place among them; it can be found in the remaining $k$ weighings.

Example. One weighing can find the heavier coin from two, so in 8 weighings, the 128-th coin can be found from 128 silver and 128 gold coins.

Let's add 27 gold coins (14 very heavy and 13 very light) and 28 silver coins (14 heavy and 14 light) to our coins and apply the described algorithm to them. The 128-th coin from these 256 coins will be the 101-st from the original ones.

Estimate. Suppose the required coin can be determined in 7 weighings. Consider the flowchart of the algorithm that allows this to be done. This flowchart has the form of a tree, with a check [which of the two specified coins is lighter?] in each vertex (then from this vertex, there is a branch to two subsequent vertices); or an answer [such-and-such a coin is the 101-st by weight] (then this vertex is a terminal one). There are no more than seven branches on each path, so there are no more than $2^7 = 128$ terminal vertices. But a priori, any of the given coins can be in the 101-st place, so there should be no fewer than 201 terminal vertices. Contradiction.

## Answer

8 weighings.