Question

В строку записаны числа 1, 2, …, 10 (обязательно в таком порядке). Разрешается выбрать 2 числа, такие, что левое меньше правого и поменять их местами. Какое наибольшее число операций может быть гарантировано сделано?

Answer 1

Ответ:

9

Пошаговое объяснение:

1; 2; 3; 4; 5; 6; 7; 8; 9; 10

1. 2; 1; 3; 4; 5; 6; 7; 8; 9; 10
2. 1; 3; 2; 4; 5; 6; 7; 8; 9; 10
3. 1; 2; 4; 3; 5; 6; 7; 8; 9; 10
4. 1; 2; 3; 5; 4; 6; 7; 8; 9; 10
5. 1; 2; 3; 4; 6; 5; 7; 8; 9; 10
6. 1; 2; 3; 4; 5; 7; 6; 8; 9; 10
7. 1; 2; 3; 4; 5; 6; 8; 7; 9; 10
8. 1; 2; 3; 4; 5; 6; 7; 9; 8; 10
9. 1; 2; 3; 4; 5; 6; 7; 8; 10; 9

Answer 2

Для решения этой задачи давайте рассмотрим начальный порядок чисел от 1 до 10:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Далее, давайте разместим числа в следующем порядке:

10, 9, 8, 7, 6, 5, 4, 3, 2, 1

Теперь, чтобы максимизировать количество операций обмена, давайте выполним первую операцию, поменяв 10 и 9 местами:

9, 10, 8, 7, 6, 5, 4, 3, 2, 1

Затем выполним вторую операцию, поменяв 10 и 8:

9, 8, 10, 7, 6, 5, 4, 3, 2, 1

И так далее. Мы видим, что после каждой операции обмена максимальное число уменьшается на 1, и оно будет двигаться к началу списка. Таким образом, мы можем гарантировать максимальное количество операций обмена, равное (10 - 1) + (10 - 2) + (10 - 3) + ... + 1.

Чтобы вычислить это значение, мы можем воспользоваться суммой арифметической прогрессии:

(10 - 1) + (10 - 2) + (10 - 3) + ... + 1 = 10*(10 + 1)/2 - (1 + 2 + 3 + ... + 10) = 55

Итак, наибольшее количество гарантированных операций обмена равно 55.