Ответы к заданиям — Олимпиадная математика

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

Урок 1. Инварианты

1. Нельзя. Инвариант — чётность числа стаканов, стоящих «неправильно» (вверх дном). Изначально таких 5 (нечётно). Один ход переворачивает ровно 4 стакана, а значит меняет число «неправильных» на чётную величину ($+4,+2,0,-2,-4$ — всегда чётно, ведь переворачиваются 4 стакана, и каждый меняет свой статус). Поэтому чётность числа неправильных стаканов не меняется и остаётся нечётной. Ноль неправильных стаканов (все стоят верно) — чётно, значит недостижимо.

2. 9901. При замене чисел $a,b$ на $a+b-1$ сумма всех чисел уменьшается ровно на 1. Начинаем со ста чисел, делаем 99 ходов — сумма уменьшается на 99. Начальная сумма $1+2+\cdots +100=5050$, финальное число $=5050-99=4951$. (Инвариант тут — величина «сумма минус количество чисел»: $S-k$ не меняется, ведь и сумма, и количество уменьшаются на 1. В начале $5050-100=4950$, в конце $\text{(число)}-1=4950$, откуда число $=4951$.)

3. Нельзя. У каждой фишки при ходе на 2 клетки чётность её координаты сохраняется. Значит инвариант — количество фишек, стоящих на клетках с нечётным номером. В начале фишки на $1,2,3$: нечётные позиции — две ($1$ и $3$). В цели $2,3,4$ нечётная позиция одна ($3$). Два не равно одному — переход невозможен.

4. Не сможет. Посчитаем, как меняется число голов: $-15+24=+9$, $-17+2=-15$, $-20+14=-6$, $-5+17=+12$. Все изменения ($9,-15,-6,12$) кратны 3. Значит остаток числа голов при делении на 3 — инвариант. Вначале $100\equiv 1(\mathrm{mod}3)$, и остаётся $\equiv 1$ навсегда. А $0\equiv 0(\mathrm{mod}3)$. Ноль голов недостижим — дракон бессмертен.

5. Не может (только нечётное). Каждый ход заменяет два числа их суммой, при этом общая сумма всех чисел не меняется — она инвариант. Финальное единственное число равно начальной сумме $1+2+\cdots +2026=\frac{2026\cdot 2027}{2}=2053351$. Это число нечётно, поэтому чётным результат быть не может.

6. Доказательство. Инвариант — произведение всех 64 чисел. Смена знаков целой строки или столбца меняет знак у 8 чисел, то есть умножает произведение на $(-1{)}^8=1$ — не меняет его. В позиции «все $+1$» произведение равно $+1$, значит оно $+1$ всегда. Если бы сумма была $-2$, то при 64 клетках со значениями $\pm 1$ число минус-единиц равнялось бы 33 (так как $64-2\cdot 33=-2$). Но тогда произведение равно $(-1{)}^{33}=-1\ne +1$. Противоречие — такая позиция недостижима.

7. Нельзя. Инвариант — произведение всех семи чисел. Ход меняет знак у двух соседних чисел, то есть умножает произведение на $(-1{)}^2=1$ — не меняет. Вначале одно число $-1$ и шесть $+1$, произведение равно $-1$. Оно навсегда останется $-1$. У позиции «все $+1$» произведение равно $+1\ne -1$. Значит цель недостижима.

8. ⭐ Да, такой маршрут (замкнутый маршрут коня) существует. Здесь инвариант не запрещает: конь при каждом ходе меняет цвет клетки (с чёрной на белую и наоборот), поэтому замкнутый маршрут из 64 ходов проходит 32 чёрные и 32 белые клетки — ровно поровну, никакого противоречия. Раскраска говорит лишь, что маршрут не исключён; чтобы доказать существование, нужно предъявить сам маршрут — а замкнутые обходы конём доски $8\times 8$ (их называют «замкнутый маршрут коня») действительно существуют, они хорошо известны и строятся, например, разбиением доски на четверти и соединением четырёх «полумаршрутов» в один цикл. Мораль урока: инвариант доказывает только невозможность; когда он не мешает, ответ «да» надо подтверждать конструкцией.

Урок 2. Раскраски и замощения

1. Да, всегда. Идея (теорема Гомори): центры клеток шахматной доски можно соединить в один замкнутый маршрут, проходящий по всем 64 клеткам (гамильтонов цикл по соседним клеткам). Вдоль этого цикла цвета строго чередуются чёрный-белый. Удалив одну чёрную и одну белую клетку, мы разрываем цикл на два пути (или один), и в каждом куске число клеток чётно, а цвета чередуются — значит каждый кусок легко замощается домино (берём подряд идущие пары). Поэтому оставшиеся 62 клетки всегда замостимы.

2. Нельзя. В доске $5\times 5$ ровно 25 клеток — нечётное число. Каждое домино накрывает 2 клетки, поэтому любое домино-замощение покрывает чётное число клеток. 25 нечётно — замостить невозможно.

3. Разбор (фиктивная линия существует). Внутренних линий сетки у доски $6\times 6$ пять горизонтальных и пять вертикальных — всего 10. Ключевая лемма: любую внутреннюю линию домино-замощение пересекает чётное число раз. (Доказательство: клетки строго по одну сторону линии, но лишь в части столбцов/строк, разбиваются дополнительными дoминошками на пары; аккуратный подсчёт по чётности даёт чётное число пересечений.) Всего домино 18, и каждое пересекает ровно одну внутреннюю линию (ту, что лежит между его двумя клетками). Если бы фиктивной линии не было, каждая из 10 линий пересекалась бы $\ge 1$, а значит (по лемме) $\ge 2$ раза — итого $\ge 20$ пересечений. Но пересечений ровно 18 (по числу домино). $18<20$ — противоречие. Значит хоть одна линия не пересекается ни одним домино.

4. Да; квадратик $1\times 1$ может стоять только в одной из четырёх клеток $(3,3),(3,6),(6,3),(6,6)$ (считая строки и столбцы от 1). Разбор: раскрасим доску одновременно двумя диагональными 3-раскрасками — по правилу $(i+j)\mathrm{mod}3$ и по правилу $(i-j)\mathrm{mod}3$. Прямое тримино $1\times 3$ в каждой из этих раскрасок берёт по одной клетке всех трёх цветов. Подсчёт клеток на доске $8\times 8$ даёт, что в раскраске $(i+j)\mathrm{mod}3$ цвет, которого 22 клетки (а не 21), — это цвет $1$; аналогично во второй раскраске «лишний» цвет — $0$. Оставшийся после 21 тримино квадратик обязан стоять на клетке, «лишней» в обеих раскрасках одновременно, то есть где $(i+j)\equiv 1$ и $(i-j)\equiv 0(\mathrm{mod}3)$. Таких клеток ровно четыре: $(3,3),(3,6),(6,3),(6,6)$. Для каждой из них замощение действительно существует (строится явно).

5. Доказательство. Отметим «особые» клетки $(i,j)$ с чётными $i$ и $j$ (нумерация от 1 до 10). Их ровно $5\times 5=25$. Любая плитка $2\times 2$ накрывает ровно одну особую клетку (в её двух строках ровно одна чётная, в двух столбцах — тоже). Любая плитка $1\times 4$ накрывает чётное число особых клеток: вертикальная — либо 0, либо 2 (если стоит в чётном столбце); горизонтальная — так же 0 или 2. Пусть плиток $2\times 2$ было $x$, тогда особых клеток покрыто $x+(\text{чётное})=25$. Значит $x$ нечётно. Итак, число плиток $2\times 2$ в любой правильной укладке нечётно. Если бы можно было заменить одну плитку $2\times 2$ на одну $1\times 4$ и переложить пол, число $2\times 2$-плиток изменилось бы на 1 — сменило бы чётность. Но оно обязано оставаться нечётным. Противоречие — замена невозможна.

6. $6\times 6$ — можно; $5\times 6$ — можно. Приём один и тот же: два L-тримино складываются в прямоугольник $2\times 3$. Доску $6\times 6$ режем на $2\times 3$-блоки (например, шесть блоков), каждый мостим двумя уголками. Доску $5\times 6$ режем на полосу $2\times 6$ (два блока $2\times 3$) и полосу $3\times 6$ (её режем на блоки $3\times 2$, каждый — это тот же $2\times 3$). Всё замащивается.

7. Да, можно. Требуется замкнутая ломаная по центрам, где каждое звено соединяет соседние по стороне клетки, — это гамильтонов цикл в сеточном графе $8\times 8$. Он бипартитен (чёрно-белая раскраска), цикл обязан иметь чётную длину — здесь 64, чётно, препятствия нет. И такой цикл действительно строится: например, «змейка» вниз по первому столбцу... — стандартная конструкция даёт замкнутый обход. Значит ответ «да».

8. ⭐ Доказательство индукцией по $n$. База $n=1$: доска $2\times 2$ без одной клетки — это ровно один L-уголок, замощается. Шаг: пусть для доски $2^{n-1}\times 2^{n-1}$ с любой вырезанной клеткой утверждение верно. Возьмём доску $2^n\times 2^n$ с одной вырезанной клеткой и разрежем её на 4 четверти размера $2^{n-1}\times 2^{n-1}$. Вырезанная клетка попала в одну из четвертей. Положим один L-уголок точно в центр доски так, чтобы он накрыл по одной клетке в каждой из трёх «пустых» четвертей (уголок ложится в угол каждой из этих трёх четвертей, сходящихся в центре). Теперь в каждой из четырёх четвертей ровно одна клетка «отсутствует» (в одной — исходно вырезанная, в трёх — накрытая уголком). По предположению индукции каждая четверть замащивается уголками. Собрав всё вместе, замостим всю доску. ∎

Урок 3. Принцип Дирихле

1. Доказательство. «Клетки» — 12 месяцев года, «кролики» — 30 учеников. Так как $30>12$, по принципу Дирихле хотя бы в одном месяце родились не меньше двух учеников. (На самом деле даже не меньше $\lceil 30/12\rceil =3$.)

2. Доказательство. Клетки — остатки от деления на 11 (их 11: от 0 до 10). Двенадцать чисел раскладываем по остаткам; $12>11$, значит два числа $a,b$ дают равный остаток. Тогда $a-b$ делится на 11.

3. Пара любого цвета — 4 носка. Синяя пара — 22 носка. Для пары любого цвета: 3 цвета — «клетки»; вытащив 3 носка, можно получить по одному каждого цвета, но 4-й обязательно совпадёт по цвету с одним из первых трёх (Дирихле: 4 носка, 3 цвета). Три носка не гарантируют (могут быть все разные). Для синей пары: в худшем случае невезения сначала вытащим все 10 красных и все 10 зелёных (20 носков, ни одной синей пары), потом 2 синих. Итого $10+10+2=22$ гарантируют синюю пару; 21 носка мало (могло быть 20 не-синих и 1 синий).

4. Доказательство. Сопоставим каждому числу его остаток $r$ по модулю 100 и объединим остатки в «клетки» так: пара $\{r,100-r\}$ — одна клетка (для $r=1,\dots ,49$), плюс отдельные клетки $\{0\}$ и $\{50\}$. Всего клеток $49+2=51$. Чисел 52, значит два числа попадают в одну клетку. Если у них равный остаток — их разность делится на 100. Если остатки $r$ и $100-r$ — их сумма делится на 100. В любом случае условие выполнено.

5. Доказательство. Разобьём треугольник со стороной 1 средними линиями на 4 маленьких равносторонних треугольника со стороной $\frac{1}{2}$. Точек 5, треугольничков 4 — по Дирихле в один попадут две точки. Расстояние между точками внутри треугольника со стороной $\frac{1}{2}$ не превосходит его наибольшей стороны, то есть $\frac{1}{2}$. (Договоримся точки на общих границах относить к одному из треугольников.)

6. Доказательство. Рассмотрим частичные суммы $s_0=0$, $s_1=a_1$, $s_2=a_1+a_2$, …, $s_{100}=a_1+\cdots +a_{100}$ — всего 101 число. Их остатки по модулю 100 — «кролики» в 100 «клетках» (остатки $\mathrm{0..99}$). $101>100$, значит два из них, $s_i$ и $s_j$ ($i<j$), дают одинаковый остаток. Тогда $s_j-s_i=a_{i+1}+\cdots +a_j$ делится на 100 — это и есть искомая непустая группа чисел.

7. Доказательство. Возьмём равносторонний треугольник со стороной 1. Его три вершины покрашены в два цвета, значит по Дирихле какие-то две вершины одного цвета. Расстояние между вершинами равно 1. Готово: нашлись две точки одного цвета на расстоянии ровно 1.

8. ⭐ Доказательство. Каждое число $x$ из $\{1,\dots ,200\}$ запишем как $x=2^k\cdot m$, где $m$ нечётно. Нечётных $m$ в диапазоне $\mathrm{1..199}$ ровно 100 (это $1,3,5,\dots ,199$) — они и будут «клетками». Выбрано 101 число; по Дирихле у двух выбранных чисел одинаковая нечётная часть $m$: пусть это $2^{a}m$ и $2^{b}m$ с $a<b$. Тогда меньшее $2^{a}m$ делит большее $2^{b}m$ (частное $2^{b-a}$ — целое). Значит одно из выбранных чисел делится на другое.

Урок 4. Графы

1. Невозможно. Люди — вершины, рукопожатия — рёбра; каждая из 9 вершин имеет степень 3. Сумма степеней $=9\cdot 3=27$ — нечётна. Но по лемме о рукопожатиях сумма степеней равна $2E$ и всегда чётна. Противоречие.

2. Ни одной, ни трёх — нельзя. Число вершин нечётной степени всегда чётно (следствие леммы о рукопожатиях: сумма степеней чётна, значит нечётных слагаемых чётное число). Одна и три — нечётные количества, поэтому невозможны.

3. Доказательство. У графа 6 вершин, каждая степени $\ge 3$, значит сумма степеней $\ge 18$, а рёбер $E=\frac{1}{2}\sum \mathrm{deg}\ge 9$. Лес (граф без циклов) на 6 вершинах имеет не более $6-1=5$ рёбер. У нас рёбер $\ge 9>5$, значит граф не лес — в нём есть цикл.

4. Минимум 9, максимум 45. Связный граф на 10 вершинах имеет не меньше $10-1=9$ рёбер (это дерево — минимально связный граф). Максимум рёбер без кратных и петель — это когда соединены все пары: $\left(\genfrac{}{}{0ex}{}{10}{2}\right)=45$.

5. Нельзя. Клетки $3\times 3$ — вершины, ходы коня — рёбра. Из центральной клетки конь не может пойти никуда в пределах $3\times 3$ (все его ходы уводят за доску). Значит центральная вершина изолирована (степень 0). Обход, посещающий все вершины, должен зайти и в неё, но попасть в изолированную вершину нельзя. Поэтому маршрута коня по всем 9 клеткам не существует.

6. Пример. «Да»-фигура: любой замкнутый контур, например квадрат с двумя диагоналями (каждая вершина — угол квадрата степени 3... тогда 4 нечётных вершины — не рисуется). Возьмём проще: треугольник — все три вершины степени 2 (чётные), рисуется одним росчерком (эйлеров цикл). «Нет»-фигура: четырёхлучевая звезда/«крест» из четырёх отрезков, выходящих из центра, плюс замыкающий контур так, чтобы получилось 4 вершины нечётной степени — например, полный граф на 4 вершинах $K_4$: там все 4 вершины степени 3, нечётных вершин четыре (> 2), поэтому эйлерова пути нет — одним росчерком не нарисовать. (Обоснование в обоих случаях — критерий Эйлера по числу вершин нечётной степени: 0 или 2 — можно, иначе — нельзя.)

7. Доказательство. Города — вершины, дороги — рёбра; каждая вершина степени $\ge 2$. Пойдём гулять: выйдем из любого города и будем идти по дорогам, не повторяя рёбер. Всякий раз, входя в новый город, мы вошли по одному ребру, а так как степень $\ge 2$, найдётся ещё не использованное ребро, чтобы выйти. Города конечны, поэтому рано или поздно мы придём в город, где уже были, — участок пути между двумя визитами в этот город образует замкнутый маршрут (цикл) без повторов дорог.

8. ⭐ Идея (теорема Дирака). Утверждение: если у каждого из $n\ge 3$ человек не меньше $n/2$ знакомых, то всех можно усадить за круглый стол так, что соседи всегда знакомы (гамильтонов цикл существует). Для $n=4$: условие даёт каждому $\ge 2$ знакомых. Проверим, что тогда цикл есть. Если кто-то знаком со всеми тремя — разложим остальных так, чтобы замкнуть; при минимальной степени 2 у всех граф на 4 вершинах — это либо квадрат (уже цикл), либо содержит цикл длины 4 (несложный перебор). Почему условие $n/2$ существенно: возьмём два треугольника (две компании по 3 человека), которые между собой не знакомы вовсе. Тогда $n=6$, у каждого 2 знакомых — но $2<n/2=3$. Граф несвязен, за один круглый стол их не усадить: соседями двух компаний оказались бы незнакомцы. Значит порог $n/2$ нельзя понизить. (Полное доказательство теоремы использует приём «крайнего» — берут самый длинный путь и раздвигают его; это классика, которую стоит однажды разобрать целиком.)

Урок 5. Игры и стратегии

1. Выигрывает второй. Проигрышные для того, кому ходить, — суммы, кратные 5 ($0,5,10,15,20,25,30$), потому что из них любой ход (прибавить $1$–$4$) выводит в некратную пятёрке сумму, а из некратной всегда можно вернуть противника на кратную. Стартовая сумма $0$ кратна 5 — значит первый игрок ходит из проигрышной позиции. Стратегия второго: после хода первого (тот прибавил $k$) прибавлять $5-k$, снова оставляя кратную 5 сумму; в итоге второй назовёт 30 и победит.

2. Выигрывает первый. Теперь назвавший 30 проигрывает, значит цель — заставить соперника назвать 30, то есть самому оставить сумму 29 (тогда сопернику придётся прыгнуть в $30$–$33$, а разрешено только до 30, и он вынужден сказать 30). «Хорошие» суммы, которые нужно оставлять сопернику: $4,9,14,19,24,29$ (это $30-1$ и дальше с шагом 5, то есть $\equiv 4(\mathrm{mod}5)$). Первый первым ходом берёт 4 (сумма 4), далее отвечает на ход $k$ соперника числом $5-k$. В итоге он оставит 29 и вынудит соперника назвать 30.

3. Выигрывает второй. Две равные кучки — классическая симметрия. Что бы первый ни взял из одной кучки, второй берёт столько же из другой, восстанавливая равенство. После каждого хода второго кучки снова равны, поэтому у второго всегда есть ответ, и последний камень возьмёт именно он. (На языке нима: ним-сумма $10\oplus 10=0$ — позиция проигрышна для того, кто ходит, то есть для первого.)

4. Выигрывает второй. Фишка идёт из угла в противоположный угол доски $8\times 8$, каждый ход сдвигает её на 1 клетку вправо или вверх. Чтобы дойти, нужно ровно 7 шагов вправо и 7 вверх — всего $14$ ходов, независимо от игры (это скрытый инвариант — длина пути фиксирована). 14 чётно: ходы 1,3,…,13 делает первый, ходы 2,4,…,14 — второй. Последний, 14-й ход делает второй, после чего первый не может ходить и проигрывает.

5. Выигрывает первый. Ним-сумма кучек $4,7,9$: в двоичном $100,111,1001$; XOR по разрядам $=1010_2=10\ne 0$, значит позиция выигрышна для первого. Выигрышный ход: превратить ним-сумму в 0. Ищем кучку $p$, для которой $p\oplus 10<p$: для $p=9$ имеем $9\oplus 10=3<9$. Значит нужно из кучки 9 сделать 3 (взять 6 камней). Останутся кучки $4,7,3$ с ним-суммой $4\oplus 7\oplus 3=0$ — теперь в проигрышной позиции соперник.

6. Выигрывает второй. Стратегия центральной симметрии. После каждого хода первого (он кладёт домино) второй кладёт домино на клетки, симметричные относительно центра доски. Так как доска $8\times 8$ имеет чётные стороны, её центр — не клетка, а точка на пересечении линий; поэтому домино и его центрально-симметричный образ никогда не пересекаются и не совпадают (проверяется: ни одно домино не переходит само в себя при повороте на $180°$). Значит у второго всегда есть законный симметричный ответ, и без хода первым останется именно первый — он и проиграет.

7. Проигрышны позиции, кратные 3 ($0,3,6,9,\dots$). Разбор: последний взявший выигрывает, значит $n=0$ (ходить некому) — проигрыш. Из позиции, кратной 3, любой ход берёт степень двойки ($1,2,4,8,\dots$), а все степени двойки дают остаток 1 или 2 по модулю 3 (никогда 0: $1,2,4,8,16,\cdots \equiv 1,2,1,2,\dots$). Поэтому из кратной 3 позиции нельзя попасть снова в кратную 3 — попадаешь в некратную (выигрышную для соперника). А из некратной 3 позиции всегда можно взять 1 или 2 (обе — степени двойки), вернув соперника на кратную 3. Значит кратные 3 — ровно проигрышные позиции. В частности из $100$ ($100=3\cdot 33+1$, не кратно 3) первый выигрывает, взяв 1 камень.

8. ⭐ Выигрывает первый. Ключ — скрытый инвариант: сколько бы кусок ни ломали, каждый разлом увеличивает число кусочков ровно на 1. Начинаем с 1 куска ($5\times 8$), заканчиваем, когда все $40$ долек разделены, то есть $40$ кусочков. Значит всего будет сделано ровно $40-1=39$ разломов — независимо от того, как играют. Число ходов в игре фиксировано и равно 39 (нечётно). Первый делает ходы $1,3,\dots ,39$ — то есть последний, 39-й разлом. После него ломать нечего, второй не может ходить и проигрывает.

Урок 6. Модульная арифметика

1. Остаток 1. $2\equiv -1(\mathrm{mod}3)$, поэтому $2^{100}\equiv (-1{)}^{100}=1(\mathrm{mod}3)$.

2. Последняя цифра 9. Последние цифры степеней тройки идут с периодом 4: $3,9,7,1,3,9,7,1,\dots$. Так как $2026=4\cdot 506+2$, последняя цифра $3^{2026}$ такая же, как у $3^2=9$, то есть 9.

3. Не делится; репьюнит из $k$ единиц делится на 3 ⇔ $k$ делится на 3. Сумма цифр репьюнита из 2026 единиц равна 2026. Число сравнимо со своей суммой цифр по модулю 3, а $2026=3\cdot 675+1\equiv 1(\mathrm{mod}3)$ — не делится на 3, значит и само число не делится. Вообще сумма цифр репьюнита из $k$ единиц равна $k$, поэтому он делится на 3 ровно тогда, когда $k$ кратно 3 (например, из 3, 6, 9, … единиц).

4. На 9 делится, на 11 — нет. Сумма цифр $1+2+\cdots +9=45$ делится на 9 → число делится на 9. Знакочередующаяся сумма цифр (с конца): $9-8+7-6+5-4+3-2+1=5$, не делится на 11 → число на 11 не делится.

5. Доказательство. Достаточно показать, что $a^5\equiv a(\mathrm{mod}5)$ для любого целого $a$ (тогда $\sum k^5\equiv \sum k(\mathrm{mod}5)$). Проверим по остаткам: $0^5=0$, $1^5=1$, $2^5=32\equiv 2$, $3^5=243\equiv 3$, $4^5=1024\equiv 4(\mathrm{mod}5)$ — везде $a^5\equiv a$. Значит ${\sum }_{k=1}^{100}{k}^5\equiv {\sum }_{k=1}^{100}k=\frac{100\cdot 101}{2}=5050\equiv 0(\mathrm{mod}5)$. Сумма делится на 5.

6. Остаток 2. $17\equiv 2(\mathrm{mod}5)$, поэтому $17^{17}\equiv 2^{17}(\mathrm{mod}5)$. Степени двойки по модулю 5 имеют период 4: $2,4,3,1,\dots$; $17=4\cdot 4+1$, значит $2^{17}\equiv 2^1=2(\mathrm{mod}5)$.

7. Доказательство. $30=2\cdot 3\cdot 5$, множители попарно взаимно просты, поэтому достаточно доказать делимость $n^5-n$ на 2, на 3 и на 5 по отдельности. • На 5: как в задаче 5, $n^5\equiv n(\mathrm{mod}5)$, значит $5\mid n^5-n$. • На 2 и на 3: $n^5-n=n(n^4-1)=n(n-1)(n+1)(n^2+1)$. Среди $n-1,n,n+1$ (три подряд идущих) есть чётное и есть кратное трём, значит произведение делится и на 2, и на 3. Итого $n^5-n$ делится на $2\cdot 3\cdot 5=30$.

8. ⭐ Доказательство. Число $\overline{abcabc}$ можно записать так: $\overline{abcabc}=\overline{abc}\cdot 1000+\overline{abc}=\overline{abc}\cdot 1001$. А $1001=7\cdot 11\cdot 13$. Значит $\overline{abcabc}=\overline{abc}\cdot 7\cdot 11\cdot 13$ делится и на 7, и на 11, и на 13 при любом трёхзначном $\overline{abc}$. (Например, $538538=538\cdot 1001$.)

Урок 7. Комбинаторные оценки

1. $\left(\genfrac{}{}{0ex}{}{8}{3}\right)=56$. Выбор трёх книг из восьми без учёта порядка: $\frac{8\cdot 7\cdot 6}{3\cdot 2\cdot 1}=56$.

2. 54 диагонали. Всего пар вершин у 12-угольника $\left(\genfrac{}{}{0ex}{}{12}{2}\right)=66$. Из них 12 пар — это стороны (соседние вершины), остальные — диагонали: $66-12=54$.

3. Доказательство. У каждого из 10 человек число друзей внутри компании — целое от 0 до 9 (10 возможных значений). Но значения 0 и 9 не могут встретиться одновременно: если кто-то дружит со всеми девятью (степень 9), то ни у кого не может быть 0 друзей (он-то дружит с этим человеком). Значит реально возможных значений не больше 9. Людей 10, «клеток» (значений) не больше 9 → по Дирихле у двоих число друзей совпадает.

4. Доказательство (двойной подсчёт). Посчитаем число подмножеств множества из $n$ элементов двумя способами. Способ 1: каждый элемент независимо либо входит, либо не входит в подмножество — по правилу произведения $2^n$ подмножеств. Способ 2: сгруппируем подмножества по их размеру $k$: подмножеств размера $k$ ровно $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, а $k$ пробегает $0,1,\dots ,n$. Всего $\left(\genfrac{}{}{0ex}{}{n}{0}\right)+\left(\genfrac{}{}{0ex}{}{n}{1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n}{n}\right)$. Оба способа считают одно и то же, поэтому сумма равна $2^n$.

5. Отрезков 21, треугольников 35. Никакие три из 7 точек не лежат на прямой, поэтому каждая пара точек даёт отрезок: $\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$. Каждая тройка точек — вершины треугольника: $\left(\genfrac{}{}{0ex}{}{7}{3}\right)=35$.

6. Доказательство (теорема Мантеля). Команды — вершины, сыгранные матчи — рёбра графа на 20 вершинах; рёбер 101, «тройка попарно сыгравших» — это треугольник. Докажем, что при $>100$ рёбрах треугольник обязан быть. Предположим противное: граф без треугольников. Возьмём ребро между командами $u$ и $v$. Тогда у $u$ и $v$ нет общего соперника (иначе был бы треугольник), поэтому $\mathrm{deg}(u)+\mathrm{deg}(v)\le 20$ (их соседи не пересекаются, а всего вершин 20). Просуммируем это неравенство по всем 101 ребру: слева каждое ребро $uv$ даёт $\mathrm{deg}(u)+\mathrm{deg}(v)$; вершина степени $d$ учитывается в $d$ рёбрах, поэтому сумма слева равна ${\sum }_v\mathrm{deg}(v{)}^2$. Справа — $20$ на каждое ребро, итого ${\sum }_v\mathrm{deg}(v{)}^2\le 20\cdot 101=2020$. С другой стороны, по неравенству о средних (или Коши) $\sum \mathrm{deg}(v{)}^2\ge \frac{(\sum \mathrm{deg}v{)}^2}{20}=\frac{(2\cdot 101{)}^2}{20}=\frac{202^2}{20}=\frac{40804}{20}=2040,2$. Получаем $2040,2\le \sum {\mathrm{deg}}^2\le 2020$ — противоречие. Значит треугольник есть. (Сравни: при ровно 100 матчах контрпример существует — разбей команды на две группы по 10 и соедини рёбрами все пары из разных групп: $10\cdot 10=100$ матчей, ни одного треугольника, ведь внутри групп матчей нет.)

7. Можно ровно тогда, когда $n$ чётно. Инвариант — чётность числа горящих лампочек. Каждый ход переключает две лампочки, поэтому число горящих меняется на $+2,0$ или $-2$ — чётность числа горящих сохраняется. Вначале горящих 0 (чётно), значит горящих всегда чётное число. Позиция «все горят» имеет $n$ горящих. Если $n$ нечётно — недостижимо (нечётное $\ne$ чётное). Если $n$ чётно — достижимо: переключая пары соседних лампочек $(1,2),(3,4),\dots ,(n-1,n)$, зажжём все. Итог: все лампочки удаётся зажечь ⇔ $n$ чётно.

8. ⭐ Доказательство. Посмотрим на 7 столбцов; в каждом 3 клетки двух цветов, значит какой-то цвет в столбце встречается не меньше двух раз («цвет большинства» столбца — хотя бы 2 клетки этого цвета). Цвета два, столбцов 7, поэтому по принципу Дирихле у не менее чем $\lceil 7/2\rceil =4$ столбцов цвет большинства одинаков — пусть это чёрный. Итак есть 4 столбца, в каждом из которых хотя бы 2 чёрные клетки. В каждом таком столбце выберем пару строк с чёрными клетками; пара строк — это одна из $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$ возможных пар $\{1,2\},\{1,3\},\{2,3\}$. У нас 4 столбца и всего 3 возможные пары строк — снова Дирихле: у двух из этих столбцов чёрная пара строк совпадает. Эти два столбца и эти две строки дают прямоугольник, все 4 угла которого чёрные. Одноцветный прямоугольник найден. ∎