55 (978). There are 4 balls of different masses. Using a balance scale without weights, how many weighings are needed to arrange these balls in order of decreasing mass?
Solution. Let $m_{A}, m_{B}, m_{C}, m_{D}$ be the masses of four different balls. We will use a graph to show how the weighings are performed (the arrow points from the heavier ball to the lighter one).

Suppose, for example, after two weighings, we have $m_{A}>m_{B}$ and $m_{C}>m_{D}$ (Fig. $29, a$ ). Next, we will compare $m_{A}$ and $m_{C}$ (the two heavier balls) and $m_{B}$ and $m_{D}$ (the two lighter balls). In this case, there are two possible scenarios (Fig. $29, b, c$ ).

In the first case (when the smaller of $m_{A}$ and $m_{C}$ is greater than the larger of $m_{B}$ and $m_{D}$, Fig. 29, b), no further weighings are needed: if $m_{A}>m_{C}$, and $m_{C}>m_{D}$, then $m_{A}>m_{D}$; if $m_{C}>m_{D}$, and $m_{D}>m_{B}$, then $m_{C}>m_{B}$ (by the transitive property of inequalities). Therefore, $m_{A}>m_{C}>m_{D}>m_{B}$.

In the second case (when the smaller of $m_{A}$ and $m_{C}$ is greater than the smaller of $m_{D}$ and $m_{B}$, Fig. 29, c), one more weighing is needed to compare the masses of $m_{A}$ and $m_{D}$ ( $m_{C}$ and $m_{D}$ can be easily compared using the transitive property of inequalities). (On the diagram, dashed arrows show the relationships between the masses of the balls established without weighing, based on the transitive property of inequalities.)

Answer: no more than 5 weighings.