🎓 Мои уроки
Главная › Физтех-лето › Олимпиадная математика › Ответы
← Все уроки: Олимпиадная математика 📄 PDF

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

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

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

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

  2. 9901. При замене чисел $a,b$ на $a+b-1$ сумма всех чисел уменьшается ровно на 1. Начинаем со ста чисел, делаем 99 ходов — сумма уменьшается на 99. Начальная сумма $1+2+\dots+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 \pmod 3$, и остаётся $\equiv 1$ навсегда. А $0 \equiv 0 \pmod 3$. Ноль голов недостижим — дракон бессмертен.

  5. Не может (только нечётное). Каждый ход заменяет два числа их суммой, при этом общая сумма всех чисел не меняется — она инвариант. Финальное единственное число равно начальной сумме $1+2+\dots+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)\bmod 3$ и по правилу $(i-j)\bmod 3$. Прямое тримино $1\times 3$ в каждой из этих раскрасок берёт по одной клетке всех трёх цветов. Подсчёт клеток на доске $8\times 8$ даёт, что в раскраске $(i+j)\bmod 3$ цвет, которого 22 клетки (а не 21), — это цвет $1$; аналогично во второй раскраске «лишний» цвет — $0$. Оставшийся после 21 тримино квадратик обязан стоять на клетке, «лишней» в обеих раскрасках одновременно, то есть где $(i+j)\equiv 1$ и $(i-j)\equiv 0 \pmod 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 маленьких равносторонних треугольника со стороной $\tfrac12$. Точек 5, треугольничков 4 — по Дирихле в один попадут две точки. Расстояние между точками внутри треугольника со стороной $\tfrac12$ не превосходит его наибольшей стороны, то есть $\tfrac12$. (Договоримся точки на общих границах относить к одному из треугольников.)

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

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

  8. ⭐ Доказательство. Каждое число $x$ из ${1,\dots,200}$ запишем как $x = 2^k\cdot m$, где $m$ нечётно. Нечётных $m$ в диапазоне $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 = \tfrac12\sum\deg \ge 9$. Лес (граф без циклов) на 6 вершинах имеет не более $6-1 = 5$ рёбер. У нас рёбер $\ge 9 > 5$, значит граф не лес — в нём есть цикл.

  4. Минимум 9, максимум 45. Связный граф на 10 вершинах имеет не меньше $10-1 = 9$ рёбер (это дерево — минимально связный граф). Максимум рёбер без кратных и петель — это когда соединены все пары: $\binom{10}{2} = 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 \pmod 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,\dots \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 \pmod 3$, поэтому $2^{100} \equiv (-1)^{100} = 1 \pmod 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 \pmod 3$ — не делится на 3, значит и само число не делится. Вообще сумма цифр репьюнита из $k$ единиц равна $k$, поэтому он делится на 3 ровно тогда, когда $k$ кратно 3 (например, из 3, 6, 9, … единиц).

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

  5. Доказательство. Достаточно показать, что $a^5 \equiv a \pmod 5$ для любого целого $a$ (тогда $\sum k^5 \equiv \sum k \pmod 5$). Проверим по остаткам: $0^5=0$, $1^5=1$, $2^5 = 32 \equiv 2$, $3^5 = 243 \equiv 3$, $4^5 = 1024 \equiv 4 \pmod 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 \pmod 5$. Сумма делится на 5.

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

  7. Доказательство. $30 = 2\cdot 3\cdot 5$, множители попарно взаимно просты, поэтому достаточно доказать делимость $n^5-n$ на 2, на 3 и на 5 по отдельности. • На 5: как в задаче 5, $n^5\equiv n \pmod 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\cdot3\cdot5 = 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. $\binom{8}{3} = 56$. Выбор трёх книг из восьми без учёта порядка: $\frac{8\cdot 7\cdot 6}{3\cdot 2\cdot 1} = 56$.

  2. 54 диагонали. Всего пар вершин у 12-угольника $\binom{12}{2} = 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$ ровно $\binom{n}{k}$, а $k$ пробегает $0,1,\dots,n$. Всего $\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{n}$. Оба способа считают одно и то же, поэтому сумма равна $2^n$.

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

  6. Доказательство (теорема Мантеля). Команды — вершины, сыгранные матчи — рёбра графа на 20 вершинах; рёбер 101, «тройка попарно сыгравших» — это треугольник. Докажем, что при $> 100$ рёбрах треугольник обязан быть. Предположим противное: граф без треугольников. Возьмём ребро между командами $u$ и $v$. Тогда у $u$ и $v$ нет общего соперника (иначе был бы треугольник), поэтому $\deg(u) + \deg(v) \le 20$ (их соседи не пересекаются, а всего вершин 20). Просуммируем это неравенство по всем 101 ребру: слева каждое ребро $u v$ даёт $\deg(u)+\deg(v)$; вершина степени $d$ учитывается в $d$ рёбрах, поэтому сумма слева равна $\sum_v \deg(v)^2$. Справа — $20$ на каждое ребро, итого $\sum_v \deg(v)^2 \le 20\cdot 101 = 2020$. С другой стороны, по неравенству о средних (или Коши) $\sum \deg(v)^2 \ge \frac{(\sum \deg v)^2}{20} = \frac{(2\cdot 101)^2}{20} = \frac{202^2}{20} = \frac{40804}{20} = 2040{,}2$. Получаем $2040{,}2 \le \sum\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 чёрные клетки. В каждом таком столбце выберем пару строк с чёрными клетками; пара строк — это одна из $\binom{3}{2} = 3$ возможных пар ${1,2}, {1,3}, {2,3}$. У нас 4 столбца и всего 3 возможные пары строк — снова Дирихле: у двух из этих столбцов чёрная пара строк совпадает. Эти два столбца и эти две строки дают прямоугольник, все 4 угла которого чёрные. Одноцветный прямоугольник найден. ∎