Текстовые задачи на конструктивы в комбе → .02 Процессы и алгоритмы

Легко видеть, что Ярослав будет находится вначале у замка потом —

Если то следующим действием Ярослав закроет замки с номерами и, возможно, ещё какие-то. В любом случае, замок под номером останется закрытым.

Если то дальше Ярослав закроет все замки с номерами от до и вновь встанет у замка с номером Сейчас открыты замки Дальше Ярослав закрывает замок и переходит к замку потом закрывает замки и переходит к замку который и оставляет открытым.

Назовем слова, которые можно получить, достижимыми. Всего существует различных слов длины поэтому достаточно доказать, что количество достижимых слов длины равно Докажем это утверждение по индукции.

База индукции. Для и это легко проверяется: А АА, А АБ.

Шаг индукции. Пусть для всех длин, не превосходящих утверждение верно. Посмотрим, как можно получить слово длины

1.

из слова длины применив операцию а): W АW

2.

из слова длины применив операцию б): W WБ

3.

из слова длины применив операцию в): W БWА

Слов 1-го и 2-го типа по а слов 3-го типа При этом слова 3-го типа не могут совпадать со словами 1-го и 2-го типа. А вот множества слов 1-го и 2-го типа пересекаются. Их общие слова имеют вид АБ. Докажем, что слова (которые находятся между буквами А и Б) — это все достижимые слова длины Понятно, что если — достижимое слово, то за две операции из него можно получить АБ. С другой стороны, если слово Б достижимое, то посмотрим, как оно было получено. Если проделать все те же операции, но пропустить приписывание последней буквы Б, то будет получено слово значит, оно достижимое.

Таким образом, общих слов 1-го и 2-го типа столько же, сколько достижимых слов длины то есть Следовательно, количество слов длины равно что и требовалось доказать.

Построим граф, вершинами которого будут хамелеоны, а ребрами — дружбы. Покрасим вершины в два цвета соответствующим образом. Заметим, что каждый день количество ребер с одноцветными концами увеличивается. Поскольку всего ребер конечное число, рано или поздно процесс прекратится.

Докажем, что меньшего количества ходов может не хватить. Положим первую монету решкой вверх, вторую — орлом вверх, третью — снова решкой вверх, и так далее. Предположим, что в такой ситуации нам хватит меньше ходов. Заметим, что каждая пара соседних монет имеет один из типов: либо они лежат одинаково, либо по-разному, причем мы также считаем парами границы ряда (то есть между крайними монетами и концами, границы считаем решками). Заметим, что за один ход мы меняем тип ровно пар. С другой стороны пар второго типа у нас изначально ровно для четных и для нечетных Тогда нам потребуется хотя бы ходов.

Осталось показать, что такого количества ходов нам всегда хватит. Разобьем монеты на блоки подряд идущих, повернутых одинаково (сначала блок орлов, потом решек, затем снова орлов и так далее, или наоборот). Заметим, что блоков каждого типа не больше (иначе некоторые два одинаково повернутых блока стояли подряд). Тогда можно перевернуть все блоки, которые повернуты решкой вверх.

Пронумеруем лампочки слева направо и покрасим каждую лампочку в цвет остатка ее номера при делении на Заметим, что каждый человек переключает по одной лампочке каждого цвета. Так как людей четное количество, то в конце будет гореть четное количество лампочек каждого цвета. Значит, если в конце лампочки какого-то цвета включены, то их хотя бы две штуки. Среди подряд идущих лампочек максимум одна включенная лампочка рассматриваемого цвета, то есть не более половины включённых. Проводя те же рассуждения для каждого цвета, получим, что среди любых подряд идущих лампочек не более включенных, что и требовалось.

Пусть первый узник назовёт цвет кота, которого ему привели, а второй — цвет, противоположный цвету кота, которого ему привели. Пусть не умаляя общности первому привели чёрного, тогда он назовёт чёрный цвет. Если второму привели чёрного, то они освободились. Если же второму привели белого, то он назовёт чёрный цвет, то есть в этом случае они также выйдут на свободу.

Рассмотрим любую строчку, пусть в ней сумма Затем рассмотрим множество всех строк и столбцов с суммой Заметим, что на пересечении строки и столбца с разной суммой стоит Значит, все положительные числа в линиях множества стоят на пересечении строк и столбцов из множества Подсчётом сумм чисел, стоящих на пересечении строк и столбцов из по строкам и по столбцам получаем, что в поровну строк и столбцов. Удалим все строчки и столбцы из Для оставшейся таблицы условие задачи остаётся верным. Продолжая этот процесс, получим, что строчек и столбцов в изначальной таблице поровну.

Если ящик лежит непосредственно в ящике , то будем говорить, что из ящика в ящик идёт стрелка. Пусть всего стало ящиков. Подсчитаем двумя способами общее количество стрелок. одной стороны, оно равно , поскольку из каждого ящика, кроме начальных семи, выходит ровно одна стрелка. другой стороны, число стрелок равно , поскольку в каждый из 10 непустых ящиков входит ровно 7 стрелок (а ни в какой пустой ящик стрелка не входит). Следовательно, , откуда

Данную задачу можно решить и по-другому. На каждом шаге процесса заполняется ровно один ящик – в него кладутся 7 ящиков. Поскольку вначале все ящики пусты, сделано 10 шагов, то есть добавлено 70 ящиков. Плюс семь начальных – итого 77 ящиков.

Допустим, могло. Рассмотрим первый раз, когда такое случилось. Возможны 2 случая:

1) в итоге остались 9 нулей. Значит, на предыдущем шаге все числа были равны, это противоречит тому, что эта ситуация случилась в первый раз.

2) в итоге осталось 9 единиц. Значит, на предыдущем шаге 0 и 1 чередовались, но это неозможно, так как число чисел чётно. Получаем противоречие.

Каждому прекрасному слову сопоставим позицию первой буквы последнего вхождения подслова в Докажем, что построено отображение является инъекцией, откуда будет следовать, что мощность всех прекрасных слов не превосходит мощности позиций всех букв в слова последнее же равно

Итак, предположим противное, тогда существуют два различных прекрасных слова и у которых совпадают позиции первых букв последних вхождений подслов и Пусть — количество букв в подслове Без ограничений общности будем считать, что Далее рассмотрим два случая.

Если то слово имеет своим префиксом слово но тогда первая буква второго вхождения слова в последнее вхождения слова является первой буквой какого-то вхождения слова что невозможно, ведь по предположению первая буква слова является первой буквой последнего вхождения слова

Пусть и — префикс последнего вхождения слова Во-первых, периодична с периодом Во-вторых, является префиксом слова но тогда она так же периодична с периодом Докажем, что тогда она периодична с периодом

Действительно, по теореме о линейном представлении НОД существуют такие целые числа и одинаковых знаков, что Будем считать, что второй случай разбирается аналогично.

Рассмотрим следующий процесс. Встанем на произвольную позицию в В силу периодичности, для любого на позиции при и при стоят те же буквы, что и на позиции Докажем, что мы сможем сделать операций первого вида и операций второго вида, тем самым придя в позицию

Пусть на некотором шаге мы сделали операций первого и операций второго вида. Если и то сделаем любую из операций, что возможно, поскольку текущая позиция удовлетворяет по крайней мере одному из требуемых неравенств. Если и то текущая позиция равна

но тогда мы можем сделать операцию первого типа, поскольку прибавление к текущей позиции даст не больше, чем то есть такая операция была возможно. Случай и рассматривается аналогично. Таким образом, в силу возрастания общего количество операций мы придем к случаю и чем получим требуемое. Таким образом, мы показали, что периодична с периодом Отсюда сразу следует, что и периодична с данным периодом.

Наконец, осталось заметить, что то есть то есть сдвинув все позиции последнего вхождения на мы получим снова слово поскольку индекс последней буквы равен что, как мы выяснили, меньше, чем а значит, каждая буква перешла в такую же. Тем самым, мы нашли вхождение позиция первой буквы больше изначальной.

Оценка. Рассмотрим шаг, на котором Василий помечает некоторый отрезок Перед этим шагом из каждой из точек и выходит максимум по отрезка, и они содержат максимум различных пометки. Значит, Василий точно сможет пометить этот отрезок числом, не превосходящим Итак,

Если чётно, эту оценку можно уточнить следующим образом. Назовём маленьким отрезок, помеченный единицей. Докажем, что в конце процесса из каждой точки будет выходить маленький отрезок; предположим противное. Точки, из которых выходят маленькие отрезки, разбиваются на пары точек, соединённых таким отрезком. Значит, есть хотя бы две точки и из которых не выходит маленьких отрезков. Выходит, что когда Василий проводил отрезок он должен был пометить его единицей — противоречие.

Значит, если отрезок не будет маленьким, то в конце процесса среди отрезков, выходящих из и кроме будут два маленьких отрезка. Значит, на этих отрезках будет максимум различных пометок. Следовательно, когда Василий будет проводить отрезок он сможет пометить его числом, не превосходящим и

Пример. Осталось доказать, что Василий может достичь указанных значений

______________________________________________________________________________________________________________________________________________________

Лемма. Если количество точек чётно и равно то Василий может пометить все отрезки между этими точками, использовать лишь числа от до При этом из каждой точки выходит ровно по одному отрезку с каждой пометкой.

Доказательство. Утверждение леммы не зависит от конкретного расположения точек, так что можно считать, что точек расположены в вершинах правильного -угольника, а оставшаяся точка — в его центре

Тогда все отрезки между этими точками можно разбить на множеств так, чтобы отрезки одного множества не имели общих концов. Например, в множество можно включить отрезок и все отрезки, соединяющие пары вершин -угольника и перпендикулярные Из каждой точки выходит по отрезку каждого из множеств.

Теперь Василий может сначала пометить все отрезки множества числом 1, затем все отрезки второго множества числом 2, и т. д.

_________________________________________________________________________________________________________________________________________________________________________________

Вернёмся к решению. Пусть нечётно, и пусть — отмеченная точка. Пусть Василий сначала пометит все отрезки между точками, отличными от числами от 1 до согласно лемме. Затем он проведёт отрезок из каждый отрезок ему придётся помечать числом, большим ибо из уже выходят отрезки, помеченные всеми меньшими числами. Кроме того, все эти отрезок будут помечены разными числами, ибо у них есть общий конец. Следовательно, они будут помечены числами

то есть Василий получит пометку

Пусть теперь чётно. Выберем две отмеченных точки и пусть

— остальные отмеченные точки. Пусть Василий сначала пометит все отрезки между точками числами от 1 до согласно лемме, а также пометит отрезок числом 1. Затем он последовательно проводит отрезки

поскольку в вершины уже входят отрезки с пометками от 1 до новые отрезки будут помечены числами

соответственно. Далее Василий проводит отрезки

аналогично, он пометит их числами

соответственно.

Теперь в вершины и уже входят отрезки со всеми пометками от до а в вершину — со всеми пометками от 1 до Значит, когда Василий проводит отрезки и первый будет помечен числом а второй — числом (ибо имеет общий конец с предыдущим). Значит, Василий добился появления числа

Назовём набор городов критическим, если есть рейсов, соединяющих два города этой группы, где — количество городов в группе. Тогда ибо иначе между городами группы есть не более

рейсов. Если группа из всех 998 городов критическая, то в стране уже рейсов.

В дальнейшем мы всегда предполагаем, что законы в любой момент соблюдены. Обозначим через количество рейсов, соединяющих два города группы

Докажем, что если группа из всех городов не критическая, то министерство может добавить один рейс с соблюдением законов. Повторяя такие операции, министерство добьётся требуемого. Заметим, что, если между городами и нет рейса, то добавить его министерство не может лишь в случае, когда оба города и входят в какую-то критическую группу.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть и — критические группы. Тогда группа также критическая.

Доказательство. Положим

Пусть

тогда По условию, имеем

Заметим, что все рейсы, посчитанные в и учитываются также и в более того, если какой-то рейс учтён и в и в то оба его конца лежат в то есть количество дважды учтённых рейсов равно Поэтому

Учитывая, что законы соблюдены, получаем что и требовалось.

_________________________________________________________________________________________________________________________________________________________________________________

Вернёмся к решению. Если в настоящий момент нет ни одной критической группы, можно добавить рейс между любой парой городов, между которыми его ещё нет (такая пара найдётся!). Иначе, применяя лемму, получаем, что объединение всех критических групп — тоже критическая группа по предположению, в ней городов. Пусть — город вне тогда не входит ни в какую критическую группу.

Пусть из идёт рейсов в города из Поскольку группа не критическая, имеем

откуда С другой стороны, поэтому в есть город не соединённый рейсом с и города и не входят в одну критическую группу. Значит, министерство может ввести рейс между и

Пусть — центр окружности (и описанной окружности треугольника соответственно). Прямые , и разделят плоскость на 6 частей, которые назовем областями. Пусть эти прямые пересекают окружность в точках и соответственно ( и на одном луче от — на другом, для других точек аналогично). Тогда стороны угла являются серединными перпендикулярами к отрезкам и , а значит, для всех точкек угла (равного ) и только для них является ближайшей из . При этом для точек, которые лежат внутри угла , но вне круга , после операции вершина становится ближайшей, а внутри угла — вершина . Для вершин и аналогично.

Рассмотрим, что происходит при применении нескольких операций к точке . Пусть образ точки , после применения к ней k операций. Докажем следующие утверждения:

Если лежит в , то все при — тоже. Так что теперь можем без ограничения общности считать, что лежит в угле и вне круга .

Вектор равен удвоенному вектору , так как для ближайшая вершина , для , композиция симметрий относительно потом — параллельный перенос на вектор .

Соответственно, если все точки лежат в но не в , то все вектора равны .

Пусть — первая из четных точек, не лежащая одновременно в угле и вне круга . Тогда лежит в одной из трех областей: и .

Итак, без ограничения общности можно считать, что попала в .

Итак, если точка когда-то за две операции перескочит из угла в соседний, то дальше за каждую пару операций точка перепрыгивает между ровно этими двумя соседними углами, пока не попадет в круг . Докажем, что это рано или поздно произойдет. В самом деле, пусть точка за двойную операцию переходит между и . Тогда она за каждую двойную операцию смещается на вектор или . Оба вектора имеют проекцию на луч , значит рано или поздно проекция точки на будет иметь отрицательную координату, то есть точка покинет углы и .

Сделать это четная точка может только попав в поскольку если — первая из четных точек, попавшая в , то попадет в или попадет в или и так далее (за каждые два хода точка перескакивает через границу между теми же двумя соседними углами, или запрыгивает в ).

_________________________________________________________________________________________________________________________________________________________________________________

Как доказано выше, каждому из шести углов, на которые разделена плоскость, сопоставлен свой вектор , такой что квадрат операции для точки, лежащей в данном угле, есть перенос на соответствующий вектор. Тогда множество точек, попадающих в круг не более чем за 1010 операций - это множество кругов, получаемых из круга при параллельных переносах на всевозможные линейные комбинации векторов с целыми неотрицательными коэффициентами, сумма которых не больше 1010 , и только два циклически соседних коэффициента отличны от нуля. Тогда самый близкий к граничный круг (обозначим его а его центр - представляющийся в виде , то есть . Заметим, что для только его дуга размером , отвернутая от , не покрыта остальными кругами, итого самая ближняя к граничная точка такова что , то есть .

По аналогичным соображениям, точки переходящие в за 2021 ход - образы кругов радиуса 1 с центрами в точках при переносах на ту же систему векторов. Тогда самый далекий от круг (обозначим его а его центр )получается при переносе на вектор , то есть имеющий длину . Поскольку образует угол в с имеем . Точка на границе круга еще на 1 дальше, итого ответ .

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

Пусть Саша нажал на переключателей, из них относились к строкам, а — к столбцам. Тогда сейчас горят лампочек: лампочек в выбранных Сашей строках, — в столбцах, — лампочки на их пересечении (их Саша уже выключил). Сумма зависит только от номера текущей минуты. Хорошо известно, что если фиксировано, то произведение тем больше, чем меньше . Осталось заметить, что если переключать последовательно строки и столбцы, то на каждом шаге минимальное из возможных: для чётных и для нечётных.

Покажем, что

Заметим, что достаточно доказать для Пусть Если , то равенство ( очевидно. Если то

Тогда

и равенство доказано. Следовательно,

То есть, на одном шаге шифрования — линейное преобразование числа Так как композиция линейных преобразований есть линейное преобразование, то , где и — неизвестные.

Воспользуемся тем, что на этом ключе буква Ъ переходит в букву Ь, а буква П — в Е:

Вычитая из первого равенства второе, получим: Отсюда Тогда

и, следовательно, Окончательно получили:

Тогда

Последовательно подставляя буквы шифрованного текста ЯГКЫНИ, получим исходное слово МОСКВА.

Покажем, как надо действовать. Сначала 48 электриков меняют по одному плафону в 48 люстрах, на это уходит 5 минут, и у 48 люстр один плафон заменен, у 12 — ни один не заменен. Затем 12 электриков меняют плафоны у тех люстр, у которых еще не меняли, остальные 36 электриков меняют в 36 люстрах вторые плафоны. На это опять уходит 5 минут, получаем 36 люстр с двумя новыми плафонами и 24 — с одним. Теперь 24 электрика меняют вторые плафоны, и 24 — третьи. Теперь 24 люстры с тремя новыми плафонами и 36 — с двумя. Теперь 36 электриков меняют 36 третьих плафонов и 12 электриков — 12 четвёртых плафонов. Теперь 48 люстр с тремя новыми плафонами и с четырьмя. Последний этап 48 электриков меняют последние плафоны на 48 люстрах. Итак, за 5 этапов, т.е. за 25 минут, все плафоны в люстрах заменены. Покажем, что меньше чем за 25 минут это сделать нельзя. Нужно заменить плафонов. На каждый плафон нужно 5 минут, значит, всего не меньше, чем минут. Но у нас есть 48 электриков, значит, это можно сделать за 25 минут, но никак не меньше.

Сначала четырежды обменяем черные шарики с белыми:

ЧЧЧЧББББ ЧЧЧБЧБББ ЧЧБЧЧБББ ЧЧБЧБЧББ ЧЧББЧЧББ.

Это обошлось нам в 2 руб. 40 коп. Теперь перекрасим два левых черных шарика в белый цвет, а два правых белых — в черный. На это мы потратим еще 4 руб., итого ровно 6 руб. 40 коп.

Фальшивых монет может быть две или одна. Занумеруем монеты числами от 1 до 6 в порядке их расположения. Первым взвешиванием на левую чашку кладём 1, 2, 3, на правую 4, 5, 6. Если наступит равновесие, то фальшивых монет две. Если нет, то фальшивая монета одна и лежит на более тяжёлой чашке. Сравним две монеты с этой чашки. Если равновесие, то фальшивая третья, иначе фальшивая на перетянувшей чашке. В случае равновесия в первом взвешивании найдём за второе взвешивание фальшивую среди 1, 2, 3, а вторая фальшивая лежит напротив.

Первое решение.

Присвоим цветам остатки от деления на 3 произвольным образом. Все операции с ними также будем производить по модулю Тогда операция, производимая роботом, такова: если уничтожаются кубики цветов и то появляется кубик цвета

Если то после каждого прохода полного круга количество кубиков уменьшается вдвое, а их сумма меняет знак. Значит, в конце получится кубик цвета вне зависимости от места старта. Мы доказали, что степени двойки удачны.

Если где то рассмотрим расстановку из одного красного кубика и белого. Если робот стартует перед красным кубиком, то после ходов останутся один синий кубик и белых. Если робот стартует непосредственно после красного кубика, то через ходов останутся один красный кубик и белых. Вышеприведённые аргументы для степени двойки показывают, что в этих двух ситуациях итоговые цвета будут разными, то есть неудачно.

Второе решение.

Заметим сразу, что, если чётное число удачно, то и тоже. Действительно, если в расстановке кубиков робот будет начинать только с чётных позиций, то после ходов он будет получать одну и ту же расстановку, в которой он стоит на всевозможных позициях. Поскольку каждая расстановка кубиков может быть получена таким образом, получаем требуемое.

Рассмотрим две расстановки, отличающиеся ровно в одном месте. Запустим в них по роботу параллельно; тогда получающиеся расстановки всегда будут отличаться ровно в одном месте. В частности, итоговые цвета будут различны.

Отсюда уже следует, что все нечётные (а значит, по замечанию, и все кроме степеней двойки) неудачны. Действительно, начнём с расстановки с одним красным и белыми кубиками. Если робот стоял перед красным кубиком, через ход останутся один красный и белый кубик, робот стоит после красного. Если же робот стартует непосредственно после красного, через ход останутся один синий и белых кубиков, робот стоит непосредственно после синего. Как показано выше, итоговые цвета в этих двух ситуациях будут разными.

Покажем теперь, что, если — степень двойки, то итоговый цвет не зависит от места старта. Для этого сделаем ещё одно наблюдение по поводу замены цвета. Если цвет одного кубика в расстановке сменить на следующий в циклическом порядке

то после одного использования цвет сдвинется в противоположную сторону.

Значит, если любая такая замена исходного кубика приведёт к сдвигу цвета итогового кубика в одну и ту же сторону. Осталось заметить, что две расстановки, отличающиеся поворотом, получаются из расстановки всех белых кубиков за одинаковое количество замен "вперёд по циклу".

Пусть первая сестра загадала число а вторая сестра — число Нам нужно узнать, верно ли, что Мы не можем сравнить числа и просто раскрыть модуль, так как каждая из сестёр знает только своё число, поэтому рассмотрим, чему эквивалентно неравенство в зависимости от

1) Если больше пятисот, то должно быть меньше пятисот для того, чтобы неравенство выполнялось. То есть, если то неравенство эквивалентно или же Таким образом, нам нужно сравнить два числа: и при этом первая сестра знает, чему равно а вторая сестра знает, чему равно Пусть множество всех возможных значений это множество а множество всех возможных значений — это Сейчас Тогда

2) Аналогично, если то неравенство эквивалентно или же То есть нам так же нужно сравнить два числа: и при этом первая сестра знает, чему равно а вторая сестра знает, чему равно Пусть множество всех возможных значений это множество а множество всех возможных значений — это Сейчас Тогда

Итак, в обоих случаях у нас получилось, что нужно сравнить два числа и причём одно из чисел известно первой сестре, а другое второй, а пересечение множеств возможных значений этих чисел состоит из пятисот элементов. Зададим первой сестре вопрос: «Верно ли, что » После этого введем и согласно случаям, расписанным выше, и будем сравнивать эти числа по одному алгоритму.

С каждым шагом будет уменьшать пересечение множеств и в два раза. Например, второй вопрос будет: «Верно ли, что » или «Верно ли, что » в зависимости от ответа на первый вопрос. Если на каком-то шаге то мы спрашиваем, верно ли, что (или в зависимости от того, кому задаем вопрос) больше, чем Таким образом, после второго вопроса в пересечении множеств будет и будет 250 элементов, после третьего вопроса — 175 элементов, после четвёртого — 88, и так далее. Получается, после десятого вопроса в пересечении будет всего один элемент. Пусть это будет число

При этом, после каждого вопроса уменьшается так же количество элементов в или в Пусть после десятого вопроса (или наоборот, все элементы множества не меньше а все элементы множества — небольше). Последние два вопроса будут: «Верно ли, что » или «Верно ли, что ». Если ответы на оба вопроса «да», то числа и равны, и загаданные сёстрами числа различаются ровно на 500. Если ответ на первый из этих вопросов «нет», то Аналогично, если ответ на второй вопрос «нет».