Question

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

Answer 1

Ответ:

5

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

сначала поменять 1 и 10, затем 2 и 9, 3 и 8, 4 и 7, 5 и 6.

Больше ходов сделать нельзя

Answer 2

Чтобы максимизировать количество операций, нужно придумать стратегию, которая позволит максимально увеличивать количество пар чисел, подходящих для обмена, на каждом шаге. Для этого давайте рассмотрим начальную последовательность чисел от 1 до 12:

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

И попробуем выполнить обмены, чтобы увеличивать количество инверсий (пар чисел, где левое число меньше правого).

1. Поменяем местами 12 и 11:

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

Теперь у нас есть 1 инверсия (11 и 12).

2. Поменяем местами 10 и 9:

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

Теперь у нас есть 3 инверсии (9 и 10, 10 и 12, 11 и 12).

3. Поменяем местами 8 и 7:

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

Теперь у нас есть 5 инверсий (7 и 8, 8 и 10, 9 и 10, 10 и 12, 11 и 12).

4. Поменяем местами 6 и 5:

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

Теперь у нас есть 7 инверсий (5 и 6, 6 и 8, 7 и 8, 8 и 10, 9 и 10, 10 и 12, 11 и 12).

5. Поменяем местами 4 и 3:

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

Теперь у нас есть 9 инверсий (3 и 4, 4 и 6, 5 и 6, 6 и 8, 7 и 8, 8 и 10, 9 и 10, 10 и 12, 11 и 12).

6. Поменяем местами 2 и 1:

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

Теперь у нас есть 11 инверсий (1 и 2, 3 и 4, 4 и 6, 5 и 6, 6 и 8, 7 и 8, 8 и 10, 9 и 10, 10 и 12, 11 и 12).

Таким образом, максимальное количество инверсий, которое можно гарантированно создать, равно 11.