Текстовые задачи на конструктивы в комбе

Сначала подставим число, состоящее из всех единиц, чтобы узнать их количество в

Далее будем рассматривать пятерку чисел, о которой мы будем знать количество единиц в ней, подставив число, состоящее из 5 двоек на позициях рассматриваемой пятерки. Далее в нашей пятерке зафиксируем число на произвольной позиции, относительно которого будем рассматривать пары чисел, подставляя на их позиции число 2. Таким образом, проведя 3 таких операции, мы определим число единиц в каждой такой паре. Значит, если в какой-то паре мы получили ответ, что в ней 0 или 2 единицы, то их позиции определяются однозначно. Зная, какая цифра находится на фиксированной позиции, мы однозначно определяем позиции остальных чисел. Если на все три пары мы получили ответ, что в них находится одна единица, то у нас возможны 2 варианта: либо на фиксированной позиции стоит цифра 2, а в остальных 1, либо наоборот, на фиксированной позиции стоит цифра 1. Зная количество единиц в этой пятерке, мы можем однозначно определить, какой из этих случаев выполняется.

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

Разобьем ленту на участков из числа и останется последние клетки. Стратегия будет повторяться отдельно для каждого участка.

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

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

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

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

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

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

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

Если в обоих взвешиваниях весы показали равенство, то монеты А, Б, В, Г все весят по  г. Третьим действием поставим А и Б на одну чашу, а Д — на другую. Так мы поймем массу монеты Д и при любой её массе среди известных масс набирается г.

Если в одном взвешивании было равенство, а в другом — неравенство, пусть А = Б и В > Г. Тогда монеты А и Б весят по  г, а В — или  г. Взвесив В с А и Б вместе, определим массу монеты В. Если В весит  г, то Г весит  г. Тогда монеты А, Б, В, Г имеют общую массу  г. Если В весит  г, то монеты А, Б и В имеют общую массу  г.

Рассмотрим очередь из школьников, где первый школьник изначально имеет конфет. Каждую минуту один из школьников передаёт стоящему за ним некоторое количество конфет причём после передачи выполняются условия:

где и — количество конфет у -го и -го школьников до передачи.

Введём функцию энергии системы:

При передаче конфет от школьника к изменение энергии составит:

Из условия следует:

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

Для применения Diamond-леммы проверим, что любые два шага коммутируют. Пусть возможны передачи:

1.

От школьника к конфет

2.

От школьника к конфет

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

При столкновении двух машинок их разворот эквивалентен тому, что они проходят друг через друга без изменения направления. Таким образом, столкновения не изменяют общую динамику системы, а лишь меняют “метки” машинок. Будем считать, что у машинок есть номера, а при столкновении происходит перестановка номеров двух машинок.

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

Рассмотрим граф, в котором вершинам соответствуют люди, а ребра между вершинами проведены, если соответствующие дети — участники одного марафона. С переходом человека между марафонами все ребра внутри прошлого марафона удаляются, и появляются ребра внутри нового марафона.

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

Рассмотрим самую левую букву Б. Эта буква Б не может сдвинуться вправо, поскольку любая операция с ней переставляет ее левее в слове. Предположим, что наш процесс бесконечен. Так как эта буква Б может двигаться только влево, то бесконечно двигаться она сама не может. То есть существует момент, начиная с которого буква Б перестает двигаться. Удалим начальный отрезок строки, состоящий из всех символов А до самой левой буквы Б и эту букву Б. Про действия, произведенные над этим начальным отрезком можно забыть. Тогда у нас все еще имеется бесконечный процесс, и в новой строке есть самая левая буква Б. Те же рассуждения можно повторить и для нее. Число букв Б в строке, очевидно, остается конечным и неизменным. Следовательно, процесс должен закончиться за конечное число ходов — противоречие.

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

Назовем человека, сидящего напротив Васи, Андреем. Сначала приведем пример, при котором меньше, чем печенек может не хватить. Пусть у Андрея печенек. Расставим людям веса, начиная от Андрея, у которого вес будет равен и идя по двум дугам к Васе, умножая вес очередного человека на (тем самым у Васи будет вес

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

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

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

Пусть — множество всех последовательностей из нулей и единиц длины Определим функцию сопоставляющую каждой последовательности из последовательность, состоящую из её последних цифр. Пусть — множество всех последовательностей из нулей и единиц длины в которых ровно один элемент равен а остальные равны а — множество всех остальных последовательностей длины

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

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

1) Если то он сообщает значение элемента под номером

2) Если и первая цифра последовательности равна то помощник сообщает значение и номер единицы из последовательности

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

Опишем действия фокусника.

1) Если он услышал цифру с номером из диапазона от до то он понимает, что это случай 1). Значит, по этому номеру с помощью функции нумерации (ввиду её биективности) он может восстановить а значит, и последние цифр вместе с их номерами.

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

(a) Покажем, что каждая компонента связности графа является простым циклом. Тогда разбиение на компоненты связности будет искомым.

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

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

(b) Аналогично пункту (a) будем считать граф связным и запустим покраску. Если есть вершина степени 0, то весь граф состоит только из неё. сама по себе образует цепочку. Если в графе нет вершин степени 1, то по пункту (a) мы найдём простой цикл. Если же есть вершина степени 1, то начнём покраску из неё. Граф конечен, поэтому процесс остановится, причём вернуться в уже посещенную вершину нельзя. Значит, мы закончим в другой вершине степени 1. Тогда получилась цепочка. Аналогично циклу, мы обошли весь граф.

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

тогда

Далее пусть

тогда

Продолжая аналогично, на -м шаге выберем:

тогда:

для На -м шаге выберем и получим последовательность из нулей.

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

База. тривиальна.

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

Отметим, что если — наименьшее число шагов, необходимое для “обнуления” последовательности то для где:

Действительно, для и всех имеем:

На -м шаге мы устанавливаем для экономии шагов, что противоречит минимальности

С другой стороны, для и всех имеем:

На -м шаге мы устанавливаем для экономии шагов , что опять противоречит минимальности

Итак, откуда для всех При этом из следует для всех

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

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

Занумеруем камни от до Занумеруем коробки от до по или против часовой стрелки так, чтобы все камни в начале были в -й коробке, а в конце оказались в -й.

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

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

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

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

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

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

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

Возьмём произвольного рыцаря Наложим заклинание на тех рыцарей, кто дружит с тем самым теперь будет со всеми враждовать. Выберем другого рыцаря Помимо их двоих осталось ещё 98 рыцарей (обозначим их за ), поэтому либо дружит хотя бы с рыцарями из либо враждует хотя бы с 49 из них. Наложением заклинания на (если необходимо) можно добиться того, чтобы реализовался второй вариант, при этом оно не затронет отношения с рыцарями из Таким образом мы добились того, что и вместе враждуют с группой из 49 рыцарей (обозначим их за ).

Продолжим процесс: выберем третьего рыцаря не из Тогда в найдётся либо хотя бы врагов либо хотя бы 25 друзей Во втором случае наложим заклинание на что даст нам группу из 25 рыцарей, враждующих с (обозначим их за ). Аналогично находятся рыцари и строятся множества рыцарей размера и соответственно, при этом все рыцари из будут враждовать с рыцарями что и требовалось.

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

Зафиксируем 5 рыцарей, назовём их орденом. На каждого из оставшихся рыцарей наложим заклинание в том и только в том случае, если он дружит не более чем с двумя рыцарями из ордена. После наложения всех заклинаний получим, что каждый рыцарь имеет не менее 3 друзей среди рыцарей ордена. Будем считать двух рыцарей не из ордена схожими, если они дружат с одинаковыми рыцарями ордена. Рыцарей вне ордена 95, а множество возможных друзей может принимать различных значений. Значит, по принципу Дирихле найдётся хотя бы схожих рыцарей, назовём их братством. Тогда фея Моргана может наложить заклинания на их общих друзей из ордена, после чего каждый рыцарь из ордена будет враждовать с каждым рыцарем из братства.

Третье решение.

Для решения нам понадобится:

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. для (считаем, что при ).

Доказательство. Достаточно заметить, что для натуральных выполнено неравенство Действительно, по условию поэтому По свойству числа сочетаний а что приводит нас к требуемому неравенству. Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

Расставим веса детям так, что если между ребёнком и Витей стоит промежутков между детьми (берём минимальное из расстояний), то его вес равен Пусть вес печеньки равен весу ребёнка, у которого она находится. Заметим, что наша операция не увеличивает сумму весов печенек. Пусть наиболее удалённого от Вити ребёнка зовут Никита.

Пусть Тогда рассмотрим ситуацию, где все печеньки находятся у Никиты. Его вес равен 1. Тогда сумма весов печенек меньше и если бы в процессе печенька появилась у Вити, то сумма весов стала бы не меньше Отсюда получаем противоречие. Значит, не подходит.

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

что меньше изначальной суммы весов у этих людей, откуда и получаем противоречие.

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

За один ход суммарное число камней увеличивается не более, чем на

Пусть было сделано ходов. Отсюда имеем неравенство

откуда после деления на очевидно следует, что

Пример. Делаем ходов; в каждом ходе одновременно кладём по одному числу из набора в разные коробки: восьмёрку — по очереди в коробки – четвёрку — по кругу в коробки – (каждая получит по два раза), двойку — попеременно в коробки и (по четыре раза), единицу — всегда в коробку После ходов во всех коробках по камней.

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

1) ход будет обязательно сделан и в первой последовательности ходов;

2) этот ход можно сделать прямо перед ходом сохранив все остальные ходы (и итоговое расположение шариков в коробках).

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

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

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

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

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

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