|
В ряд в порядке возрастания лежат карточки с числами от $%1$% до $%500$%. За одну операцию можно поменять местами две соседние карточки. За какое наименьшее число операций мы сможем добиться того, чтобы никакие две карточки, числа на которых отличаются на $%1$%, не были бы соседними? задан 4 Янв '18 11:37 
voevodin |
|
У меня получился ответ 300. Разбиваем все числа на 100 пятёрок. В каждой пятёрке с последними четырьмя числами проделываем три преобразования. На примере первой: 2345 -> 3245 -> 3254 -> 3524. Аналогично с остальными пятёрками. Получается 1 3 5 2 4 6 8 10 7 9 11 ... 496 498 500 497 499. Сделано 300 преобразований; все пары вида n n+1 и n+1 n исчезли. Теперь покажем, что меньше 300 преобразований не хватает. При каждой перестановке мы либо переставляем числа из одной пятёрки, и тогда этой пятёрке сопоставляем число 2, или переставляются два числа из соседних пятёрок, и тогда каждой из них сопоставляем число 1. Если преобразований меньше 300, то сумма будет меньше 600, и на одну из 100 пятёрок приходится меньше 6, то есть не больше 5. Непосредственным перебором вариантов можно проверить, что этого количества не хватает. Внутри пятёрки происходит не более двух преобразований, и к ним добавляется максимум одно "крайнее" -- слева или справа. Остаётся рассмотреть небольшое число вариантов (с учётом симметрии), и убедиться, что все "запрещённые" пары исчезнуть при этом не могут. отвечен 6 Янв '18 1:48 
falcao |
Не могу понять, как доказать оценку. Прошу, пожалуйста, помочь с этим.
@voevodin: за какое число операций у Вас это получилось? Задача сама по себе не самая простая, как мне кажется.