Someone noticed that the letters of the old

COUNTY SAVINGS BANK R. T.

sign can be rearranged to form the following sentence:

TATAR CHILD ASKS FOR MONEY.

We want to perform the rearrangement using swaps in the following two ways:

I. method: only adjacent letters can be swapped.

II. method: any distant letters can be swapped.

How many swaps are needed for each rearrangement method? (After a swap, both letters must take the other's place, and a new swap can only occur after this.)





Translate the above text into English, please keep the line breaks and format of the source text, and output the translation result directly.
I. Solution. I. In the case of the first exchange method, it is obviously more efficient to perform fewer exchanges if we keep the relative order of the letters that occur multiple times, for example, the first $E_{E} E_{1}$ letter of the old text is moved to the first É of the new text, and the TAKARÉK word is moved to the PÉNZT word - thus, the $E_{2}$ of the PÉNZTÁR word is moved to the $K E ́ R I$ word - in this way, we avoid the unnecessary exchange of $E_{1}$ and $E_{2}$. According to this, the new position of each letter is uniquely determined. In the table, the movements of the letters are illustrated by arrows, and the letters that remain in place (e.g., $P$) are marked with an ×. Each letter participates in at least as many exchanges as the number of vertical lines representing the spaces between letters that its arrow crosses. The total number of these steps can also be determined by summing the number of arrows crossing each line in one direction, which is why we wrote the number of arrows crossing each line in one direction below it, for example, 5 on the line between the 5th and 6th positions (this number is obviously the same in both directions). The sum of these numbers is 63.

![](https://cdn.mathpix.com/cropped/2024_05_02_5733cf4a75adbd6f29eag-1.jpg?height=711&width=1266&top_left_y=539&top_left_x=413)

This many exchanges would be sufficient if in every exchange both letters moved towards their final positions, as in the exchange of $I$ and $T_{1}$ in the original order. However, in some exchanges, only one letter moves towards its final position. For example, $M$ and $E_{1}$ will exchange at some point during the rearrangement because $M$ must precede the $E_{1}$ that is also moving to the right, which means $E_{1}$'s path is extended by one step to the left and one to the right (the exchange occurs either in sequence or over a space between letters, 3 times or between the 1st and 2nd positions, 2 times), and the number of exchanges increases by 1. Similarly, the ×-marked letters must also exchange due to the letters passing through their positions, for example, $R_{3}$ is passed by $I$ and $T_{3}$, and the first passage creates a new arrow for $R_{3}$.

$G$ and $Y$ are preceded by 2 letters each in their rightward movement: $M$ and $E_{1}$ (intuitively, because the latter's arrow covers the former's and the arrows have the same direction), which we marked with a 2 next to the starting point of the $G$ and $Y$ arrows. Similarly, $R_{1}$ is preceded by 2 letters to the left, and $E_{1}, K_{1}, A_{2}, E_{1}, K_{2}$, and $E_{2}$ are each preceded by 1 letter, so the number of additional exchanges due to precedents is 12. The number of exchanges increases by 10 due to the 3, 3, 3, and 1 pairs of letters passing through the ×-marked letters (3, or 1 arrow in one direction covers the 0-length arrow of these four letters). Combining all this, the number of necessary exchanges is $63+12+10=85$.

In executing the rearrangement, only perform exchanges that move at least one of the exchanged letters towards its new position.

II. In the case of the second rearrangement method, it is obviously more efficient to leave $\hat{E}_{2}$ and $T_{2}$ in place (since they are already in the correct position) and move $E_{1}$ to the position of $R_{2}$ and $T_{3}$ to the position of $G$ (see the bottom row of the table), thus we need to move 16 letters to their designated positions using allowed exchanges.

Here, there is a beneficial exchange for both letters in the exchanges between $A_{1}$ and $E_{1}$, as well as $R_{1}$ and $E_{2}$, but in every other exchange, at most one letter moves to its target position, for example, $G$ aims for the position of $I$, but $I$ does not need to move to the position of $G$. Nevertheless, the exchange of $G$ and $I$ is advantageous because after it, the exchange of $I$ and $T_{3}$ places both letters in their correct positions; thus, $G, I, T_{3}$ cyclically (in a circle) move to each other's positions in 2 paired exchanges. Similarly, the 3-element $K_{1}, E_{1}, R_{2}$ and the 6-element $M, A_{2}, K_{2}$, $\bar{A}, Y, T_{1}$ cycles can be arranged, the latter with 5 allowed exchanges, for example, $M$ sequentially passes its current position to $T_{1}, Y, A^{\prime}, K_{2}, A_{2}$, and finally, in the fifth exchange, it reaches its intended position (which is why the number of exchanges is 1 less than the number of elements in the cycle).

Thus, the rearrangement (considering the first two mentioned exchanges as 2-element cycles) is executed in 5 cycles with $1+1+2+2+5=11$ exchanges.

Remark. We show that in the second exchange method, the goal cannot be achieved with fewer than 11 exchanges. We rely on the fact that in the plan of the rearrangement, we wrote down cycles of more or fewer letters from the 