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

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

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

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

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

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

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

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

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

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

Задача 1#119820

Пусть $n >3$ — натуральное число. Сколько существует способ выбрать два не пересекающихся прямоугольника внутри квадрата $n× n,$ идущих по линиям сетки? Прямоугольники пересекаются, если у них есть хотя бы одна общая внутренняя клетка или общая точка на границе.

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Для начала разберите случай, когда не пересекаются "горизонтальные" интервалы. А сколько тогда способов будет для "вертикальных" интервалов?

Подсказка 4

Если "горизонтальные" интервалы не пересекаются, то вертикальные можно выбрать абсолютно любыми! Аналогично и со случаем, когда не пересекаются "вертикальные" интервалы. Осталось лишь проверить, не посчиталось ли ничего лишнего ;)

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

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

Сначала посчитаем количество способов, при которых горизонтальные интервалы не пересекаются. Пусть эти интервалы — $[a,b]$ и $[c,d].$ Поскольку порядок прямоугольников не имеет значения, без потери общности можно предположить, что $a< c,$ то есть $a <b< c< d.$ Тогда количество способов выбрать $a,b,c,d$ равно $4 Cn+1.$ На вертикальные интервалы ограничений нет, поэтому количество способов выбрать их равно $2 2 (C n+1) .$ Таким образом, общее количество пар прямоугольников с непересекающимися горизонтальными интервалами равно $4 2 2 Cn+1⋅(C n+1) .$ По симметрии, количество пар прямоугольников с непересекающимися вертикальными интервалами такое же.

Осталось посчитать и вычесть количество способов, при которых и горизонтальные, и вертикальные интервалы не пересекаются. Пусть горизонтальные интервалы — $[a,b]$ и $[c,d],$ а вертикальные — $[e,f]$ и $[g,h].$ Без потери общности можно предположить $a< b< c< d,$ поэтому оличество способов выбрать горизонтальные интервалы равно $C4n+1.$ Однако случаи $e <f <g <h$ и $g <h < e<f$ теперь различны, поэтому количество способов выбрать вертикальные интервалы равно $2⋅C4n+1.$ Следовательно, количество пар прямоугольников, у которых и горизонтальные, и вертикальные интервалы не пересекаются, равно $2 ⋅(C4n+1)2.$

Ответ:

$2⋅C4 ⋅(C2 )2 − 2⋅(C4 )2 n+1 n+1 n+1$

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

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

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

Задача 2#119833

Множество натуральных чисел $M$ назовём хорошим, если выполнены следующие два условия:

$(i)$ $M$ содержит все натуральные числа, меньшие $2025;$

$(ii)$ если $n ∈M,$ то в $M$ лежат все члены арифметической прогрессии, первый член которой равен $n,$ а разность равна $n +1.$

Верно ли, что для любого хорошего множества $M$ существует такое натуральное число $N,$ что в $M$ лежат все натуральные числа, не меньшие $N?$

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

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

Подсказка 1

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

Подсказка 2

Рассмотрим множество M', в котором лежат все числа из M, увеличенные на 1. Как тогда переписать условие для него?

Подсказка 3

В частности, если число m лежит в M', то в M' так же лежат все числа, кратные m. А вот это уже хорошее условие, потому что легко проверить, выполняется оно для множества или нет. Теперь гораздо легче придумать пример множества, для которого соблюдаются (i) и (ii) но для которого не верен вопрос задачи)

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

Рассмотрим множество $M ′,$ в котором лежат все числа из $M,$ увеличенные на $1.$ Тогда, если $n ∈M,$ то $n+ n+ 1= 2n+ 1∈ M$ согласно условию $(ii).$ Получается, $′ n+1 ∈M$ и $′ 2n +2 ∈M .$ Отсюда условие переписывается в виде:

$(i)$ $′ M$ содержит все натуральные числа от $2$ до $2025;$

$(ii)$ если $′ m∈ M ,$ то в $′ M$ лежат все члены арифметической прогрессии, первый член которой равен $m,$ а разность равна $m.$

Верно ли, что для любого такого множества $′ M$ существует такое натуральное число $N,$ что в $′ M$ лежат все натуральные числа, не меньшие $N?$

Заметим, что арифметическая прогрессия из условия $(ii)$ — это просто все числа, кратные $m.$ Возьмём в качестве $′ M$ все натуральные числа, не меньшие $2,$ кроме простых чисел, больших $2025.$ Легко видеть, что оно подходит под оба условия, но в силу бесконечности множества простых, не подходит под утверждение.

Ответ:

Нет

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

Задача 3#119855

Пусть $S n$ — множество всех возможных биекций множества ${1,2,...,n}$ в себя.

Для любых $U,V,W ⊂ Sn$ обозначим через $NUV W$ количество способов выбрать $f ∈U,g ∈V,h∈ W$ так, что $f(g(h(x)))$ — тождественное отображение, т.е. для любого $k∈ {1,2,...,n}$ выполнено $f(g(h(k)))= k.$

Пусть $A,B,C$ таковы, что $A∪ B∪ C =Sn$ и $A ∩B = B∩ C =C ∩A = ∅.$ Докажите, что $NABC =NCBA.$

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

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

Подсказка 1

Попробуем разбить одно из исходных подмножеств на объединение нескольких попарно непересекающихся множеств. Каким образом тогда при этом можно представить N в виде суммы?

Подсказка 2

А чему будет равна сумма количеств способов выбрать биекции для суммы следующих множеств: UVW, VVW, WVW? Попробуйте точно определить значение этой суммы.

Подсказка 3

А как можно сравнить количество способов выбрать биекции для UVW и VWU (или WUV)?

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

Через $A ⊔ A ⊔ ...⊔A 1 2 n$ будем обозначать объединение множеств, которые попарно не пересекаются.

Элементы $Sn$ мы, по традиции, будем называть перестановками, а также для каждой пары пересетановок $f1$ и $f2$ мы можем определить их композицию, т.е. перестановку $f1 ∘f2$ такую, что $(f1∘f2)(x):=f1(f2(x)).$ Тождественную перестановку будем обозначать $id.$

Таким образом, $NUVW$ по сути — количество троек $(f,g,h)$ таких, что $f ∘g∘h= id$ и $f ∈U,g ∈V,h∈ W.$

______________________________________________________________________________________________________________________________________________________

Мысль 1. Начнём решение с простого, но важного наблюдения: если $U = U1⊔U2,$ то

NUV W =NU1V W + NU2VW

т.е. если $U$ представлено в виде объединения двух непересекающихся множеств, то все тройки, соответствующие $NUV W$ способам выбрать $f,g$ и $h,$ очевидно, разбиваются на тройки по тому, откуда берётся $f$ — из $U1$ или $U2.$

В частности,

NABC +NBBC + BCBC = NSnBC

С другой стороны, легко видеть, что $NSnBC$ равно $|B|⋅|C|:$ для любого способа взять $g ∈B$ и $h∈ C$ существует ровно одна биекция $f$ такая, что $f ∘ (g∘ h) =id.$

______________________________________________________________________________________________________________________________________________________

Мысль 2. Для любых $U,V,W$ выполнено $NUV W =NV WU$ (а, значит, и $NWUV ).$ Для этого достаточно проверить, что $f ∘g ∘h= id$ тогда и только тогда, когда $g∘h∘f =id.$ Проследим за судьбой какого-то числа $k∈{1,2,...,n}$ при подстановке в $f ∘g∘ h.$ Под действием $g ∘h$ пусть $k$ переходит в $k′.$ Тогда $f(k′)= k.$ Но тогда

(g∘h ∘f)(k′) =(g∘h)(k)= k′

Поскольку пока $k$ пробегает все числа от $1$ до $n,$ число $′ k$ также пробегает все эти числа, утверждение остаётся верным.

_________________________________________________________________________________________________________________________________________________________________________________

Теперь у нас есть все, чтобы решить задачу. Ранее мы показали, что $NABC +NBBC + BCBC = NSnBC$ и $NSnBC = |B |⋅|C|.$ Тогда

NABC = NSnBC − NBBC − NCBC = |B |⋅|C|− NBBC − NCBC

Используя $N = N UVW V WU$ и $|B|⋅|C|= N , SnCB$ получаем, что последнее равно

NSnCB − NBCB − NCCB = NACB = NCBA.

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

Задача 4#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$ букв, составляющих нужную перестановку.

Ответ: да

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

Задача 5#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

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

Задача 6#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

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

Курсы

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

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

Задача 7#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

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

Задача 8#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$

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

Задача 9#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$ для нечётных.

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

Задача 10#103184

В классе учится $36$ человек. Каждое утро заходя в класс некоторые из них в качестве приветствия жмут друг другу руки, причём никто никому не жмёт руку за день более одного раза. В один из дней оказалось, что никакие двое учеников, которые сделали одинаковое количество рукопожатий, не жали руку друг другу. Какое максимальное число рукопожатий могло быть совершено в этот день?

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

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

Подсказка 1

Подумайте, как много может быть человек, которые совершили ровно k рукопожатий?

Подсказка 2

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

Подсказка 3

Людей, которые совершили ровно k рукопожатий, не более, чем k. Попробуем тогда построить оптимальный пример! Что мы должны максимизировать?

Подсказка 4

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

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

Заметим, что если в классе ровно $1$ человек, который поздоровался со всеми остальными, двое тех, кто поздоровались со всеми остальными, но не друг с другом, трое тех, кто поздоровался со всеми остальными, но не друг с другом, ... $8$ человек, которые пожали руку всем остальными, кроме как между собой, то будет ровно $556$ рукопожатий. Действительно, во-первых, $1 +2+ 3+ ...+ 8= 36,$ так что группы такого размера возможны. Во-вторых, в каждой группе каждый ребёнок сделал одинаковое число рукопожатий, а дети из разных групп — разное. Но дети из одной группы как раз не жали друг другу руки, а значит условие задачи выполнено. Наконец, если построить граф знакомств на этих детях, то от полного графа его будет отличать отсутствие внунтренних ребёр в каждой группе. То есть всего рёбер будет

36⋅35∕2− 1⋅2∕2 − 2⋅3∕2− 3⋅4∕2− 4⋅5∕2− 5 ⋅6∕2− 6⋅7∕2 − 7⋅8∕2= 18⋅35− 1− 3− 6− 10− 15− 21 − 28= 630− 84 =546.

Докажем, что не может быть больше $k$ людей, совершивших ровно $36− k$ рукопожатий. Допустим обратное, то есть что имеется хотя бы $k+ 1$ человек, сделавший ровно $36− k$ рукопожатий. Рассмотрим одно из них. Кроме него имеется всего $35$ человек в классе, при этом он совершил $36− k$ рукопожатий и есть ещё $k$ человек, который сделали ровно столько же рукопожатий. Тогда по принципу Дирихле, так как $(36− k)+ k> 35,$ найдётся человек, совершивший столько же рукопожатий, и которому он жал руку, что противоречит условию задачи.

Из доказанного утверждения легко понять, что приведённый пример является оптимальным. Докажем строго это утверждение. Для этого упорядочим всех школьников по количеству рукопожатий, которые они совершили, и обозначим количество рукопожатий первого из них (т. е. того, кто соврешил максимальное количество рукопожатий) за $a1$ , следующего по количеству — за $a2$ и т. д. Тогда $a1 ≥ a2 ≥a3 ≥...≥a36$ — количества рукопожатий, совершённые школьниками нашего класса.

Заметим, что $a1 ≤ 35$ , просто потому что больше, чем $35$ рукопожатий совершить невозможно. Причём если $a1 = 35$ , то $a2 ≤34$ по утверждению, доказанному ранее. Далее получаем, что $a2$ и $a3$ не больше, чем $34,$ причём $a4 ≤33$ , так как если бы $a3$ было равно хотя бы $34,$ то и $a2,a3$ тоже были бы равны $34,$ а таких людей по доказанному утверждению может быть не более, чем $2.$ Аналогично можно доказать, что

a4,a5,a6 ≤ 33 и a7 ≤32, и т. д.

Тогда

a1+ a2+ ...+a36 ≤ 35+34+ 34+ 33 +33+ 33+...+2◟8+-288+◝р.◜аз..+28◞.

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

Ответ: 546