Конструктивы в алгебре
Ошибка.
Попробуйте повторить позже
В ряд слева направо стоят 
коробок, занумерованных подряд числами
. В некоторые коробки, стоящие подряд, положат по шарику, оставив остальные пустыми. Инструкция состоит из
последовательно выполняемых команд вида «поменять местами содержимое коробок № 
и № 
», где 
и 
— числа. Для каждого ли 
существует инструкция, в которой не больше 
команд, со свойством: для любой начальной раскладки указанного вида можно будет,
вычеркнув из инструкции некоторые команды, получить инструкцию, после выполнения которой все коробки с шариками будут левее
коробок без шариков?
Источники:
Подсказка 1
Сразу вот такое наблюдение: у нас всего N коробок, а длина инструкции может быть 100N...Да и еще шарики в коробках лежат не наугад, а подряд, т.е. еще меньше вариаций для расположения шаров в коробках... На какой ответ в задаче это намекает?
Подсказка 2
Как будто всегда можно придумать такую инструкцию) А если мы доказываем что-то, что должно работать для любого натурального числа, то давайте доказывать это по индукции! А именно, будем доказывать, что для любого N существует нужная инструкция длины меньше чем 100N. Как можно это сделать?
Подсказка 3
База понятное дело проверяется, а вот что делать с переходом...Нам в нем, очевидно, нужно пользоваться меньшим числом K, для которого условие верно. Значит, нам нужно свести ситуацию для N к меньшей ситуации. То есть, по факту нужно перенести все шарики в меньший промежуток, где они также стоят подряд. Как это можно сделать и какой промежуток брать для этого?
Подсказка 4
Давайте мы будем переносить все в левую половину (если N = 2k, то в первые k коробок, если N = 2k+1, то в первые k+1 коробок). И самая важная идея: представьте, что в коробках, в которых есть шарики - синие шарики, а в которых нет мы положили красные шарики. То есть, нам нужно синие шары положить левее красных, но при таком условии мы можем сделать наоборот, и с помощью дополнительных инструкций поменять нам на нужную ситуацию)
Подсказка 5
Если сейчас в лоб не получается придумать как перетащить все шарики синие шарики в левую половинку, то вот что поймите: мы же можем перетащить любые шарики влево а оставшиеся будут справа, а после сделать ситуацию наоборот. Поэтому перетаскивайте те шары, которых меньше (и кстати, их будет <не больше k как раз).
Подсказка 6
Раз наших шаров не больше k, то значит в i-ой и k+i-ой коробкой не больше одного нужного шарика....Попробуйте применить это и раскрутить дальше, возможно добавив какие-то инструкции)
Давайте считать, что все шарики синие. В пустые коробки положим по красному шарику. Теперь пустых коробок нет. Покажем даже более
сильное утверждение: что для любого 
есть инструкция не длиннее чем 
со следующим свойством.
Пусть в 
коробочках, стоящих в ряд, лежат красные и синие шарики, причём для хотя бы одного из цветов шарики этого цвета лежат
подряд (такие конфигурации назовём непрерывными). Тогда можно вычеркнуть часть строк и получить инструкцию, после выполнения
которой все синие шарики будут левее всех красных шариков, а также можно получить инструкцию, после которой все красные шарики
левее всех синих (нумерация коробок слева направо).
Воспользуемся методом математической индукции. Понятно, что для 
такая инструкция есть. Это база индукции. Теперь
покажем, как из инструкции для 
сделать инструкцию для 
и для 
этого будет достаточно. Обозначим 
или
Инструкция для 
будет выглядеть так:
I группа: сначала все пары вида 
в любом порядке
Если 
нечетно, сюда приходится добавить все пары вида 
при 
(назовём эти команды дополнительными).
II группа: инструкция для 
первых коробочек из индукционного предположения
III группа: все пары различных чисел вида 
в любом порядке
При 
длина этой инструкции не превышает 
При 
длина этой инструкции не превышает 
Теперь почему она работает. Есть тот
цвет, которого не больше 
, назовём его основным. Покажем, что можно выполнить часть инструкций I группы так, чтобы все шарики
основного цвета лежали среди первых 
коробочек, и при этом конфигурация среди первых 
коробочек будет тоже
непрерывной.
Есть четыре варианта того, как могут располагаться шарики основного цвета.
1) Они идут подряд, и все они среди левых 
коробок — ничего делать не надо;
2) Они идут подряд, и все они среди правых коробок — используем все пары вида 
;
3) Они есть и среди левых 
коробок, и среди остальных правых, при этом они идут подряд. Заметим, что ни в какой паре вида
нет двух шариков основного цвета. Все основные шарики тогда перенесем справа налево (тогда шарики не основного цвета будут
среди первых 
шариков лежать подряд.
4) Шарики основного цвета — самые первые и самые последние. Перенеся последние влево (при нечётном 
используя дополнительные
операции), получаем требуемое.
(Про это всё проще думать, если мыслить расположение коробочек не в ряд, а по окружности.)
После этого применим часть инструкций II группы, чтобы среди первых 
коробочек слева оказались все шарики основного
цвета.
После этого окажется, что среди 
коробочек сначала идут подряд шарики одного цвета, а потом шарики другого. То есть мы пришли
либо к искомой ситуации, либо к зеркальной. Перестановками третьей группы, если надо, отразим конфигурацию, и получим что хотели
получить.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
