Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Комбинаторика на Турломе: графы, игры, клетчатые задачи, Дирихле

Тема ТурЛом (турнир Ломоносова)

Комбинаторика на Турломе: графы, игры, клетчатые задачи, Дирихле

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела турлом (турнир ломоносова)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#90451

Назовём словом любую последовательность букв. Со словами разрешается проделывать следующие операции: 1) удалить первую букву слова; 2) удалить последнюю букву слова; 3) добавить копию слова после него. Например, если исходное слово $ABC$ , применение операций даст $BC,AB$ и $ABCABC$ соответственно. Верно ли, что с помощью таких операций можно в любом слове переставить буквы в любом порядке?

Источники: Турнир Ломоносова - 2024, 11.4 (см. turlom.olimpiada.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Как получить циклический сдвиг?

Подсказка 3

Достаточно просто удвоить слово и удалить всё лишнее! Теперь попробуйте перейти от этого к произвольной перестановке.

Показать ответ и решение

Сначала заметим, что мы можем сделать циклический сдвиг букв в слове. Действительно, пусть у нас есть слово $A A ...A 1 2 n$ . Удвоим его и удалим буквы $A1A2 ...An−1$ слева. Получили слово $AnA1A2...An −1$ .

Теперь приведём алгоритм. Пусть у нас имеется слово $X$ , имеющее вид $A1A2...An$ . Сделаем копию $n$ раз, получим слово $Y$ , состоящее из $n 2$ копий $X$ , идущих подряд. Рассмотрим самое крайнее слово $X$ справа, из него будем делать нужную перестановку. Пусть мы хотим получить некоторую перестановку $B1B2...Bn$ . Пусть $i$ — минимальный индекс такой, что $Ai ⁄=Bi$ . Уберём в самом правом слове $X$ все буквы от $Ai$ до $An$ . Теперь сделаем циклический сдвиг, переместим $Bi$ в конец слова $Y$ . Далее будем следовать аналогичному алгоритму, найдём в слове $Y$ букву $Bi+1$ (она будет среди $n$ первых слева букв), удалим все буквы перед ней и сдвинем её в конец слова $Y$ и так дальше.

Спустя не более $n$ циклических сдвигов $n$ последних букв слова $Y$ будут нужной перестановкой, останется только удалить лишние буквы слева и мы получим требуемое.

Осталось объяснить, почему длины слова $Y$ хватит. На первом шаге мы удаляем не более $n$ букв справа и менее $n$ букв слева, а на остальных шагах — менее $n$ букв слева. Таким образом, всего будет удалено не более $2n +n(n− 1)=n2 +n$ букв. Длина слова $Y$ равна $n ⋅2n$ . Неравенство $n⋅2n ≥ n2+ n$ вытекает из неравенства $2n >n +1$ , которое можно доказать индукцией по $n$ . Таким образом, мы сможем выполнить $n$ циклических сдвигов и при этом точно останутся $n$ букв, составляющих нужную перестановку.

Ответ: да

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#90452

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

Источники: Турнир Ломоносова - 2024, 11.5 (см. turlom.olimpiada.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Подсказка 4

Так, попробуем ещё докрутить оценку для центрального (то есть 56-ого) горизонтального отрезка. У нас из всех 111 вертикальных отрезка 2 выходят из нашего. Тогда как мы можем оценить кол-во точек пересечения для 56-ого горизонтального отрезка?

Подсказка 5

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

Показать ответ и решение

Оценка. Для начала докажем, что больше $6049$ самопересечений быть не может. Назовём звенья одного направления горизонтальными, а звенья второго направления — вертикальными. Расположим плоскость так, чтобы горизонтальные звенья действительно стали горизонтальными. Заметим сразу две вещи:

$⋅$ каждая точка самопересечения — это пересечение вертикального и горизонтального звена; $⋅$ горизонтальные и вертикальные звенья чередуются, поэтому каждых по $111$ штук.

Пронумеруем сверху вниз горизонтальные звенья от $1$ до $111$ . Посмотрим на звено с номером $k$ . Каждое пересекающее его вертикальное ребро должно иметь над ним конец, совпадающий с концов некоторого горизонтального ребра. Горизонтальных рёбер выше всего $k− 1$ , поэтому на $k$ -м ребре не более $2(k− 1)$ точек самопересечений. Эта оценка хорошо работает для $k$ от $1$ до $55$ : на них суммарно не более

0+ 2+4 +...+ 2⋅54= 2970

точек самопересечений. Аналогичными рассуждениями (но рассматривая нижние концы вертикальных звений) доказывается, что и на звеньях с $57$ по $111$ суммарно не более $2970$ точек самопересечений.

Для ребра с номером $56$ немного улучшим оценку: всего существует $111$ вертикальных рёбер, но два из них выходят из концов $56$ -го звена, поэтому не могут его пересекать. Итого, на $56$ звене не более $109$ точек самопересечений. Значит, суммарно их не больше $2⋅2970+109= 6049.$

Пример. Пронумеруем и вертикальные звенья тоже. Пусть $⋅1$ -е вертикальное ребро соединяет $55$ и $56$ горизонтальные звенья; $⋅2$ -е вертикальное ребро — $54$ и $57$ горизонтальные звенья; $⋅3$ -е вертикальное ребро — $53$ и $58$ горизонтальные звенья; $...$ $⋅55$ -е вертикальное ребро — $1$ и $110$ горизонтальные звенья; $⋅56$ -е вертикальное ребро — $1$ и $111$ горизонтальные звенья; $⋅57$ -е вертикальное ребро — $2$ и $111$ горизонтальные звенья; $⋅58$ -е вертикальное ребро — $3$ и $110$ горизонтальные звенья; $⋅59$ -е вертикальное ребро — $4$ и $109$ горизонтальные звенья; $...$ $⋅111$ -е вертикальное ребро — $56$ и $57$ горизонтальные звенья.

Аналогичный пример для $222$ -звенной ломаной на картинке ниже:

$PIC$

Ответ: 6049

Ошибка.
Попробуйте повторить позже

Задача 3#68035

Авантюрист прибыл на остров, где живёт племя аборигенов, и пытается понять их язык. На данный момент ему известно следующее: 1. в языке всего две буквы $A$ и $B,$ каждая последовательность букв образует слово, у которого есть некоторое значение; 2. несмотря на то, что слов бесконечно много, значений у слов конечное количество;

Авантюрист придумал обозначение для слов, имеющих одинаковое значение: он стал писать между ними знак равенства «=». 3. если $w1 =w2,$ то для любых слов $s$ и $t$ выполнены равенства $sw1t=$ $sw2t,sw1 =sw2,w1t= w2t$ (для слов $x$ и $y$ под $xy$ понимается слово, полученное приписыванием к слову $x$ справа слова $y);$ другими словами, если в некотором слове заменить его подслово на слово с тем же значением, то значение слова от этого не изменится. Докажите, что если $ABB = B,$ то $BAB =B.$

Источники: Турнир Ломоносова-2023, 11.5 (см. turlom.olimpiada.ru)

Подсказки к задаче

Подсказка 1

Понятно, что хочется цепочкой слов что-то делать с ВАВ, причем используя АВВ. Не хватает В в конце ВАВ…подумаем в сторону В, сколько можно их добавить?

Подсказка 2

Если мы сколько-то добавим, заменим АВВ на В, то избавимся от А! Тогда у нас останется множество В-шэк, от которого хотим прийти к одной В… Тогда подумаем, а сколько В-шэк на какое количество В-шэк можно заменить?

Подсказка 3

Какое-то количество В-шэк точно можно заменять на меньшее количество (в силу конечного количества значений). Попробуем с помощью цепочки равенств доказать, что какое-то количество В можно заменять на одну В! Останься лишь воспользоваться подсказкой 2)

Показать доказательство

Поскольку различных значений у слов конечное количество, то среди слов $B,BB,...$ найдутся два с одинаковым значением. Пусть это слова из $n$ и $m$ $(n< m)$ букв $B :$

B◟B◝..◜.B◞= B◟B-.◝◜..B◞. n m

Докажем, что слово $B$ имеет то же значение, что и слово из $k= m − n +1 ≥2$ букв $B.$ Если для такой пары оказывается, что $n = 1,$ то это верно. В противном случае при $n ≥2 :$

BB ...B =B BB ...B =ABB BB...B= ABB ...B= ABB ...B = ABB BB ...B = ◟-◝n◜−1-◞ ◟-◝n◜−2-◞ ◟n◝−◜2-◞ ◟--◝n◜-◞ ◟--◝m◜-◞ ◟-◝m◜−2-◞

= BB◟B-.◝.◜.B◞= B◟B◝..◜.B◞. m−2 m −1

То есть одинаковые значения имеют слова из $n− 1,m − 1$ букв. Отсюда и следует верность утверждения, если продолжать до тех пор, пока $n ⁄=1.$

Тогда:

BAB = BA B◟B◝..◜.B◞=BABB B◟B◝..◜.B◞ =BB B◟B-.◝◜..B◞= B◟B.◝.◜.B◞= B. k k− 2 k−2 k

Что и требовалось доказать.

Ошибка.
Попробуйте повторить позже

Задача 4#76577

У Ярослава есть $N$ замков, пронумерованных числами от 1 до $N,$ расположенных по кругу в порядке увеличения номеров от 1 до $N$ по часовой стрелке. В начальный момент времени все замки открыты. Ярослав начинает с замка с номером 1 и движется всегда по часовой стрелке. Если Ярослав находится у замка с номером $k,$ то:

если открытых замков сейчас суммарно больше $k,$ то Ярослав закрывает следующие по часовой стрелке $k$ открытых замков, и переходит к следующему после этого открытому замку (возможно, снова к замку с номером $k$ );
если открытых замков сейчас суммарно не больше $k,$ то Ярослав закрывает все замки, кроме замка с номером $k,$ и заканчивает (таким образом, остаётся открытым только замок с номером $k$ ).

При каком наименьшем $N > 2022$ Ярослав оставит в конце открытым замок с номером 1?

Источники: Турнир Ломоносова-2022, 11.2

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Мы понимаем, что 1,3,7,15,31,63,127,255,511,1023 будут открыты. Посмотрите, что происходит в моменте, когда Ярослав стоит на 1023 замке, возможно, мы сможем получить оценку на N? Обратите внимание на то, что после замка с номером k он либо остаётся на нём же, либо переходит в замок с номером 2k+1.

Подсказка 3

Да, если N < 2046, то он гарантированно закроет замок с номером 1, а что будет при N = 2046? В этой задаче хорошо, что пример придумывать не нужно, а можно просто проверить, выполняется ли условие после проделанного алгоритма или нет.

Показать ответ и решение

Легко видеть, что Ярослав будет находится вначале у замка $1,$ потом — $3,7,15,31,63,127,255,511,1023.$

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

Если $N =2046,$ то дальше Ярослав закроет все замки с номерами от $1024$ до $2046$ и вновь встанет у замка с номером $1.$ Сейчас открыты замки $1,3,7,15,31,63,127,255,511,1023.$ Дальше Ярослав закрывает замок $3$ и переходит к замку $7,$ потом закрывает замки $15,31,...,1023,$ и переходит к замку $1,$ который и оставляет открытым.

Ответ: 2046

Ошибка.
Попробуйте повторить позже

Задача 5#76580

Пусть $k$ — целое неотрицательное число, не превосходящее $1001.$ На доске написаны $k$ единиц и $1001− k$ нулей, т.е. всего на доске $1001$ число. Саша и Марина играют в игру, делая ходы по очереди, начинает Саша. В свой ход Саша может заменить два каких-то числа на их произведение. Марина в свой ход может заменить два одинаковых числа на ноль, а два разных числа на $1.$ Так они ходят до тех пор, пока на доске не останется ровно одно число. Если это единица — выигрывает Саша, если ноль — Марина. При каких $k$ выигрывает Саша?

Источники: Турнир Ломоносова-2022, 11.5

Подсказки к задаче

Подсказка 1

В подобных задачах, когда возможных значений слишком много, бывает очень полезно начать с чего-то малого и простого. Подумайте, что будет, если в какой-то момент на доске останется только 1 единица. Кто в таком случае однозначно может победить? Не забудьте, что перед ходом Саши чисел нечётное количество, а перед ходом Марины - чётное

Подсказка 2

Конечно, неважно, чей сейчас ход: если на доске только одна единица, Саша однозначно победит. Теперь, продолжая разбирать простые случаи, попробуйте рассмотреть k = 1 или 2. Получится ли придумать победную стратегию для Саши?

Подсказка 3

Верно, при k=1 всё очевидно, а при k=2 первым ходом Саши ситуация сводится к одной единице. При этом если взять k ещё меньше, то получится, что на доске одни нули, и Марина сразу побеждает. А что происходит при бо́льших значениях k?

Подсказка 4

Если единиц три, то при любой стратегии Саши Марина может превратить все числа в нули. Обратите внимание, что при бо́льших k это также работает (ведь Саша может уменьшать количество единиц только на 1 за раз, и никто не может его увеличивать, так что общее количество единиц обязательно пройдёт через тройку). Теперь остаётся только аккуратно это доказать и грамотно расписать ситуацию для каждого значения k.

Показать ответ и решение

Заметим, для начала, что если на доске чётное количество чисел, то ходит Марина, а если нечётное — Саша.

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

Тогда, если $k= 1,$ то Саша сразу находится в выигрышном для себя положении, а если $k= 2,$ то он должен первым ходом перемножить две единицы и передать Марине ситуацию ровно с одной единицей.

Докажем теперь, что если $k= 0$ или $k ≥3,$ то выигрывает Марина. Заметим, что если в какой-то момент на доске окажутся одни нули, то Марина выигрывает. Тогда при $k= 0$ Марина точно уже выиграет.

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

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

Пусть сейчас ход Марины. Перед ней точно есть $1,1,1,0.$ Если есть какие-то ещё числа, то их чётное количество, то есть хотя бы два, поэтому она может сделать ход с ними, оставив ситуацию разнообразной. Если же других чисел нет, то Марина меняет $1,0$ на $1,$ оставляя Саше $1,1,1;$ тогда он делает ход и оставляет $1,1,$ и Марина выигрывает, делая после этого $0.$

Осталось заметить, что при $k≥ 3$ и $k⁄= 1001,$ ситуация на доске уже разнообразная, а при $k= 1001,$ Марина может сделать её разнообразной своим первым ходом.

Ответ:

$1,2$

Ошибка.
Попробуйте повторить позже

Задача 6#93393

Имеется табло $100× 100,$ в каждой ячейке которого находится лампочка; исходно все лампочки выключены. K этому табло подключены $200$ переключателей: по одному на каждую линию (т.е. строку или столбец). Переключатель меняет состояние всех лампочек той линии, к которой он относится: горящие выключает, негорящие — включает. За $1$ минуту $1$ горящая лампочка расходует $1$ единицу энергии.

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

Источники: Турнир Ломоносова - 2021, 11.4 (см. turlom.olimpiada.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Давайте посмотрим на ситуацию спустя некоторое число n минут. Пусть Саша нажал на i переключателей на строках и на j на столбцах. Тогда сколько лампочек горит в данный момент? А когда такое количество является минимальным?

Подсказка 3

В выражении для числа горящих лампочек число n = i + j является фиксированным, а произведение ij - нет. А когда произведение является минимальным при фиксированной сумме? Значит, как нужно действовать Саше?

Показать доказательство

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

Пусть Саша нажал на $n$ переключателей, из них $i$ относились к строкам, а $j$ — к столбцам. Тогда сейчас горят $100i+100j− 2ij$ лампочек: $100i$ лампочек в $i$ выбранных Сашей строках, $100j$ — в столбцах, $ij$ — лампочки на их пересечении (их Саша уже выключил). Сумма $100i+100j =100(i+ j)= 100n$ зависит только от номера текущей минуты. Хорошо известно, что если $i+ j$ фиксировано, то произведение $ij$ тем больше, чем меньше $|i− j|$ . Осталось заметить, что если переключать последовательно строки и столбцы, то $|i− j|$ на каждом шаге минимальное из возможных: $0$ для чётных $i+j$ и $1$ для нечётных.

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#49494

В классе $28$ учеников. На уроке программирования они делятся на три группы. На уроке английского языка они тоже делятся на три группы, но по-другому. И на уроке физкультуры они делятся на три группы каким-то третьим способом. Докажите, что найдутся хотя бы два ученика, которые на всех трёх занятиях находятся друг с другом в одной группе.

Источники: Турнир Ломоносова-2017, отборочный тур, (см. turlom.olimpiada.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

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

Показать доказательство

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

На уроке программирования можно выбрать группу, в которой $10$ человек, по принципу Дирихле (если нужно посадить $28$ котиков в $3$ домика, то найдётся домик, в котором хотя бы $10$ котиков, иначе всего их не больше $3⋅9= 27 <28$ ). Рассмотрим эти десять ребят, которые уже провели один урок в одной группе. На уроке английского хотя бы $4$ из них снова будут в одной группе по принципу Дирихле (если садим $10$ кроликов в $3$ клетки, то хотя бы в одной клетке найдётся $4$ кролика). Теперь рассмотрим этих четверых детей и снова заметим, что по принципу Дирихле на уроке физкультуры найдутся двое в одной группе. Эти двое и являются искомыми учениками.

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

На каждом из трёх предметов занумеруем группы числами от $1$ до $3.$ Каждому ученику сопоставим последовательность из трех номеров групп (в фиксированном порядке), в которых он оказался. Всего последовательностей длины $3,$ состоящих из чисел $1,2,3,$ ровно $3⋅3⋅3= 27< 28.$ Тогда по принципу Дирихле найдутся два ученика с одинаковыми последовательностями, это и означает, что на всех предметах они попали в одинаковые группы.

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Предыдущий раздел

Следующий раздел