В ряд в порядке возрастания лежат карточки с числами от $%1$% до $%500$%. За одну операцию можно поменять местами две соседние карточки. За какое наименьшее число операций мы сможем добиться того, чтобы никакие две карточки, числа на которых отличаются на $%1$%, не были бы соседними?

задан 4 Янв '18 11:37

изменен 5 Янв '18 7:29

Не могу понять, как доказать оценку. Прошу, пожалуйста, помочь с этим.

(5 Янв '18 19:30) voevodin

@voevodin: за какое число операций у Вас это получилось? Задача сама по себе не самая простая, как мне кажется.

(5 Янв '18 23:01) falcao
10|600 символов нужно символов осталось
1

У меня получился ответ 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

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×99

задан
4 Янв '18 11:37

показан
770 раз

обновлен
6 Янв '18 1:48

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru