Задание №176919: Турнир городов
6. В ряд слева направо стоят N коробок, занумерованных подряд числами 1, 2, ..., N. В некоторые коробки, стоящие подряд, положат по шарику, оставив остальные пустыми. Инструкция состоит из последовательно выполняемых команд вида «поменять местами содержимое коробок № i и № j», где i и j — числа. Для каждого ли N существует инструкция, в которой не больше 100N команд, со свойством: для любой начальной раскладки указанного вида можно будет, вычеркнув из инструкции некоторые команды, получить инструкцию, после выполнения которой все коробки с шариками будут левее коробок без шариков? И.Митрофанов
Что проверяет это задание
Задание относится к теме «Турнир городов». Для решения понадобятся:
- анализ условия
- выбор формулы
- проверка вычислений
Источник: Международный математический Турнир городов — официальный архив
Качество материала
Показываем, из чего состоит страница и можно ли проверить материал по первоисточнику.
Последняя проверка решения:
Происхождение задания
- Банк заданий
- Международный математический Турнир городов — официальный архив
- Организатор
- Редакция «Я сам решу»
- Материалы
- 1 файл
Связанные понятия
План самостоятельного решения
- Перепишите известные данные и отдельно сформулируйте, что требуется найти или доказать.
- Свяжите условие с темой «Турнир городов» и выберите подходящее правило, формулу или способ рассуждения.
- Запишите промежуточные шаги: это помогает заметить потерянный знак, случай или логический переход.
- Сверьте результат со всеми ограничениями условия и только затем откройте подробный разбор.
Ориентировочное время: 15 минут.
Закрепить тему
После разбора попробуйте решить ещё десять заданий по предмету «Математика». Вариант формируется заново, а ответы можно сразу проверить.
Решение по шагам
6. В ряд слева направо стоят N коробок, занумерованных подряд числами 1, 2, ..., N.
В некоторые коробки, стоящие подряд, положат по шарику, оставив остальные пустыми.
4
Инструкция состоит из последовательно выполняемых команд вида «поменять местами со-
держимое коробок № i и № j», где i и j — числа. Для каждого ли N существует инструкция,
в которой не больше 100N команд, со свойством: для любой начальной раскладки указанного
вида можно будет, вычеркнув из инструкции некоторые команды, получить инструкцию, по-
сле выполнения которой все коробки с шариками будут левее коробок без шариков?
И.Митрофанов
Ответ: да.
Давайте считать, что все шарики синие. В пустые коробки положим по красному шарику.
Теперь пустых коробок нет. Покажем даже более сильное утверждение: что для любого N есть
инструкция не длиннее чем 3N со следующим свойством.
Пусть в N коробочках, стоящих в ряд, лежат красные и синие шарики, причём для хотя бы
одного из цветов шарики этого цвета лежат подряд (такие конфигурации назовём непрерывны-
ми). Тогда можно вычеркнуть часть строк и получить инструкцию, после выполнения которой
все синие шарики будут левее всех красных шариков, а также можно получить инструкцию,
после которой все красные шарики левее всех синих (нумерация коробок слева направо).
Понятно, что для N = 1 такая инструкция есть. Покажем, как из инструкции для k (cid:62) 1
сделать инструкцию для 2k и для 2k − 1, этого будет достаточно. Обозначим N = 2k или 2k − 1.
Инструкция для N будет выглядеть так:
I группа: сначала все пары вида (i,k + i) в любом порядке
Если N нечетно, сюда приходится добавить все пары вида (i + 1,i + k) при i (cid:62) 1 (назовём
эти команды дополнительными).
II группа: инструкция для k первых коробочек из индукционного предположения
III группа: все пары различных чисел вида (i,N + 1 − i) в любом порядке
При N = 2k длина этой инструкции не превышает k + 3k + k = 5k (cid:54) 3N.
При N = 2k−1 длина этой инструкции не превышает 2(k−1)+3k+(k−1) = 6k−3 = 3N. Теперь
почему она работает. Есть тот цвет, которого не больше k, назовём его основным. Покажем, что
можно выполнить часть инструкций I группы так, чтобы все камни основного цвета лежали
среди первых k коробочек, и при этом конфигурация среди первых k коробочек будет тоже
непрерывной.
Есть четыре варианта того, как могут располагаться камни основного цвета.
Используемые формулы
Понятно, что для N = 1 такая инструкция есть.Обозначим N = 2k или 2k − 1.При N = 2k длина этой инструкции не превышает k + 3k + k = 5k (cid:54) 3N.При N = 2k−1 длина этой инструкции не превышает 2(k−1)+3k+(k−1) = 6k−3 = 3N.
Самопроверка после решения
- Я использовал все данные из условия и не добавил неподтверждённых предположений.
- Каждый переход в рассуждении объяснён правилом, формулой или ранее доказанным фактом.
- Ответ соответствует вопросу, а обозначения и единицы измерения записаны однозначно.
- Я сравнил свой ход решения с разбором и понял причину каждого отличия.
Типичные ошибки
- Не проверить область допустимых значений.
- Потерять знак при переносе или раскрытии скобок.
- Не выполнить обратную подстановку.