The number 123456789 is written on the board. From the written number, two adjacent digits are chosen, provided that neither of them is 0, 1 is subtracted from each digit, and the chosen digits are swapped (for example, from 123456789, one can get 123436789 in one operation). What is the smallest number that can be obtained as a result of such operations?

#
When performing each operation, the parity of each digit does not change.

## Solution

Notice that when performing each operation, the parity of the digit in each position does not change. Indeed, initially, we had the number 123456789, which is a number of the form OEOEOEOEO (O stands for an odd digit, and E stands for an even digit). If we take a pair of adjacent digits, say O and E, then by decreasing these digits by 1, we get the pair E and O, and by swapping their positions, we again get the pair O and E. Thus, during the execution of the operations, the number will always have the form OEOEOEOEO. The smallest number of this form is 101010101. It remains to show that the number 101010101 can be obtained. For this, it is sufficient to apply our operation twice to the pair of adjacent digits 2 and 3 in the initial number 123456789, four times to the pair 4 and 5, six times to the pair 6 and 7, and finally eight times to the pair 8 and 9.

## Answer

101010101.

Submit a comment