В числе разрешается переставить любые две соседние цифры местами, если число от этого...

Question

В числе разрешается переставить любые две соседние цифры местами, если число от этого увеличится. Например, в числе 917 можно переставить цифры "1" и "7", так как получится число 971, а цифры 1 и 9 поменять местами нельзя, так как получится число 179. Какое наибольшее количество таких последовательных операций удастся сделать с числом 54678?

Answer 1

Посмотрим, сколько операций мы можем сделать с цифрой 8: логично, что её нельзя двигать вправо, иначе число станет меньше, так как все остальные цифры были меньше, значит, 4 операции продвижения влево.

Посмотрим, сколько операций мы можем сделать с цифрой 7: логично, что её нельзя двигать вправо (кроме обмена с 8), значит, 3 "влево" и 1 "вправо" после обмена с 8.

Посмотрим, сколько операций мы можем сделать с цифрой 6: её можно сдвинуть дважды вправо (7 и 8) и дважды влево.

Посмотрим, сколько операций мы можем сделать с цифрой 5: её нельзя менять с 4, а со всеми остальными можно. Исключение - ситуация, когда 4 стоит перед 5, но тогда какая-то цифра не поменялась с 4 и сделать этого не сможет. (3 операции)

Посмотрим, сколько операций мы можем сделать с цифрой 5: её можно двигать только вправо. (3 операции)

Заметим теперь, что каждую записанную операцию мы посчитали дважды, значит, максимальное число операций - ((4 + 4 + 3 + 3) : 2 = 9).

Пример:

54678 - 54687 - 54867 - 58467 - 85467 - 85476 - 85746 - 87546 - 87564 - 87654.

Ответ: 9 операций.