Тема ПитерГор (Санкт-Петербургская олимпиада)

Комбинаторика на Питергоре

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

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

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

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

Подтемы раздела питергор (санкт-петербургская олимпиада)

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

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

Задача 1#82676

Таблица $100×100$ заполнена числами как показано на рисунке:

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

Источники: СПБГОР - 2024, 11.1 (см. www.pdmi.ras.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Если в каких-то клетках прибавляем, в каких-то надо отнимать.

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

Рассмотрим раскраску таблицы в три цвета, как показано на рисунке:


1	2	3	…	1

2	3	1	…	2

3	1	2	…	3

$...$	$...$	$...$	$...$	$...$

1	2	3	…	1

Если в исходной таблице к числам цвета 2 прибавить единицу, а из чисел цвета 3 вычесть единицу, то мы получим такую перестановку, что набор чисел сохранится. А сумма в каждой тройке тоже.

Ответ: Можно

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

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

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

Задача 2#82681

На плоскости отмечено 100 точек общего положения (т.е. никакие три не лежат на одной прямой). Докажите, что можно выбрать три отмеченные точки $A$ , $B$ , $C$ так, чтобы для любой точки $D$ из оставшихся 97 отмеченных точек, прямые $AD$ и $CD$ не содержали бы точек, лежащих внутри треугольника $ABC$ .

Источники: СПБГОР - 2024, 11.5 (см. www.pdmi.ras.ru)

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

Подсказка 1

Прямые, соединяющие точки A, B, CЮ делят плоскость на 7 частей, включая треугольник внутри. Рассмотрите эти части. Точки D из каких частей нам подходят?

Подсказка 2

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

Подсказка 3

Верно, а теперь попробуйте получить противоречие через сумму углов, зная, что угол АВС максимальный из всех возможных

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

Применим принцип крайнего: выберем среди всех троек точек треугольник $ABC$ с самым большим углом $B.$

Предположим, что точки $A$ , $B$ , $C$ не подходят. Тогда существует точка $D$ в объединении частей плоскости, одна из которых заключена между прямыми $AC$ и $AB,$ а другая — между прямыми $CA$ и $CB.$

При этом $D$ не может лежать внутри треугольника $ABC$ , иначе $∠ADC >∠ABC$ .

Рассмотрим случай, когда $D$ лежит между лучами $AC$ и $AB$ (когда $D$ и $A$ лежат в разных полуплоскостях относительно $BC$ ). Тогда

∠ABD = ∠ABC +∠CBD > ∠ABC

получаем противоречие. То же работает для случая, когда $D$ лежит между лучами $AC$ и $BC$ .

Оставшиеся два случая (когда $D$ и $C$ лежат в разных полуплоскостях относительно $AB$ ) рассматриваются аналогично: в них

∠ABD = ∠CBA +∠ABD > ∠ABC

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

Задача 3#82683

Турист прибыл на остров, где живут 100 волшебников, каждый из которых может быть рыцарем или лжецом. Он знает, что на момент его приезда один из ста волшебников — рыцарь (но не знает, кто именно), а остальные — лжецы. Турист может выбрать любых двух волшебников $A$ и $B$ и попросить $A$ заколдовать $B$ заклинанием Вжух!, которое меняет сущность (превращает рыцаря в лжеца, а лжеца в рыцаря). Волшебники выполняют просьбы туриста, но если в тот момент волшебник $A$ — рыцарь, то сущность $B$ действительно меняется, а если $A$ — лжец, то не меняется. Турист хочет после нескольких последовательных просьб одновременно знать сущность хотя бы $k$ волшебников. При каком наибольшем $k$ он сможет добиться своей цели?

Источники: СПБГОР - 2024, 11.7 (см. www.pdmi.ras.ru)

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

Подсказка 1

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

Подсказка 2

Докажем, что ни в один момент времени ни про какое множество волшебников нельзя доказать, что в нём четное число рыцарей.

Подсказка 3

Рассмотрите первый такой случай. А что было до?

Подсказка 4

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

Подсказка 5

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

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

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

Изначально такого множества точно нет. Рассмотрим первый момент, когда удалось про некоторое множество $A$ доказать, что в нем четное число рыцарей. Пусть последним ходом «Вжух!» говорил волшебник $b$ . Несложным переборов вариантов можно убедится, что на прошлом ходу симметрическая разность $A$ и $b$ тоже содержала четное количество рыцарей, что противоречит выбранному первому такому моменту.

_________________________________________________________________________________________________________________________________________________________________________________

Пример. Пусть все волшебники с $1$ -го по $99$ -го поменяют сущность $100$ -го. Легко видеть, что в результате он в любом случае станет рыцарем.

Ответ: 1

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

Задача 4#89869

За какое наименьшее число операций можно перекрасить в чёрный цвет белую доску $100× 100,$ если за одну операцию можно перекрасить в противоположный цвет любые 99 клеток любой горизонтали или любой вертикали?

Источники: СПБГОР - 2023, 11.4 (см.pdmi.ras.ru)

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

Подсказка 1

Задача вида «оценка + пример», поэтому хочется понять ответ. Какой не очень сложный пример можно придумать?

Подсказка 2

Покрасить в чёрный первые 99 клеток в каждом столбце, после этого останется белой только последняя строка. Будем называть «операцией» перекрашивание всех клеток в строке кроме данной. Что будет, если применить операцию для каждой клетке в последней строке?

Подсказка 3

Конечно, вся доска станет чёрной, что и требовалось.

Подсказка 4

Перекрасятся только эти две выбранные клетки. Тогда можно объединить в такие операции в пары в строках и в столбах. Пусть после этого осталось p ходов в строчках и q ходов в столбцах. Какие простые ограничения можно сразу сделать для p и q?

Подсказка 5

p, q ≤ 100, так как в противном случае найдётся две клетки в одной строке или столбе, которые можно объединить в пару. Что будет, если одно из чисел равно 100? Рассмотрите несколько случаев для значения второго числа. А когда оба не более 99?

Подсказка 6

Также полезно понимать, могут ли p и q быть разной чётности, может ли тогда вся доска стать чёрной?

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

Оценка.

Будем говорить, что выполнили операцию в клетке, если перекрасили все 99 клеток в строке или столбце кроме данной. Пусть были операции над строками в клетках $a1,a2,...,an$ и над столбцами $b1,b2,...,bk$ .

Отметим два факта:

1.: Количество операций четно, ведь операция меняет четность числа черных клеток, тогда достаточно показать, что $n +k ≥199$ .
2.: Порядок выполнения операций не влияет на конечный результат перекрашивания.

Если дважды к одной клетке в строке применить операцию, то ничего не изменится, поэтому можно считать, что таких ходов нет. Аналогично для столбцов. Если в строчке применить операцию к двум различным клеткам, то результатом этих двух ходов будет перекрашивание рассматриваемых клеток. Будем выделять пары таких ходов в столбцах и строках, обозначим такую пару ходов как операцию I-го типа (пусть их будет $r$ штук). Пусть после этого осталось $p$ ходов в строчках (обозначим как операцию II-го типа), $q$ ходов в столбцах (обозначим как операцию III-го типа) Отметим, что $p,q ≤100$ , так как в противном случае найдётся две клетки в одной строке или столбе, которые можно объединить в операцию I-го типа. Тогда хотим доказать, что

p+q +2r≥ 199

Рассмотрим несколько случаев:

1.

$p,q ≤ 99$

Тогда клеток НЕ находящихся в столбцах и строках, где были операции II-го или III-го типа $(100− p)⋅(100 − q)$ , а любая операция I-го типа перекрашивает не более двух клеток, тогда всего ходов хотя бы

p+ q+ 2⋅ (100−-p)(100− q)= 1002− 99(p+q)+ pq = 199+ (99 − p)(99− q)≥199 2

2.

$p =100,q =0$

После выполнения операций II-го типа останется ровно 100 белых клеток. $q = 0$ , значит, операций III-го типа нет, тогда для перекрашивания белых клеток понадобиться хотя бы 50 операций I-го типа. Получаем, что всего операций не меньше, чем $(100+2 ⋅50)= 200$ .

3.

$p =100,q ≥2$

После операций II-го типа останется ровно 100 белых клеток, причём по одной в каждой строке. После выполнения операций III-го типа белых клеток останется хотя бы $99q− 100$ (так как в каждом из q столбцов перекрашивается по 99 клеток, все они чёрные, кроме, может быть, 100 белых клеток, тогда после применения операции белыми станут хотя бы $99q − 100$ ). Тогда потребуется еще хотя бы $99q− 100$ ходов, значит, всего шагов не менее

100+ q+99q− 100 ≥200

4.

$p =100,q$ : — нечётное.

Этот случай невозможен по чётности количества ходов.

Случаи для $q = 100$ аналогичны случаям для $p =100$ .

_________________________________________________________________________________________________________________________________________________________________________________

Пример.

Выполним операцию III-го типа ко всем клеткам из первой строки. Это 100 ходов. Далее применим операцию I-го типа к парам из клеток первой строки (на пары разобьем последовательно , то есть 1-ая и 2-ая клетки, 3-яя и 4-ая, $...$ , 99-ая и 100-ая). Это ещё $2 ⋅50 =100$ ходов. Итого 200.

Ответ: 200

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

Задача 5#89873

В связном графе $G$ даны два непересекающихся множества вершин $X$ и $Y,$ между этими множествами нет ни одного ребра. Пусть в графе $G − X$ ровно $m$ компонент связности, а в графе $G − Y$ ровно $n$ компонент связности. Какое наименьшее количество компонент связности может быть в графе $G− (X∪ Y)?$

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

Источники: СПБГОР - 2023, 11.7 (см.pdmi.ras.ru)

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

Подсказка 1

Операцию G - W, не так удобно рассматривать в данной задаче, как операцию G\Е(это граф получающий удалением в G всех ребер, входящих в Е), где Е — множество рёбер, у которых хотя бы один конец лежит в W.

Подсказка 2

Пусть количество компонент связанности в графе H = G\(E₁∩E₂) равно k, где G — связный граф, а E₁ и E₂ — два непересекающихся множества его рёбер. Пусть n₁ и n₂ — количество компонент связанности в G\E₁ и G\E₂ соответственно.

Подсказка 3

Если добавить и те, и другие ребра из прошлой подсказки, то граф станет связным, тогда можно составить неравенство для k, n₁ и n₂, которое и даст оценку для k.

Подсказка 4

Теперь можно использовать полученную оценку для G, Eₓ и Eᵧ. Тогда, если обозначить vₓ и vᵧ как количество вершин множества X и Y соответственно, то можно точно выразить число компонент связанности G\Eₓ и G\Eᵧ. Тогда, после применения ранее полученной оценки, останется привести для неё пример.

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

Пример графа показан на рисунке. Множество $X$ содержит $m− 1$ вершину, множество $Y$ — $n− 1$ вершину.

$PIC$

_________________________________________________________________________________________________________________________________________________________________________________

Оценка. Для графа $G = (V,E)$ и некоторого множества его ребер $E′ ⊂ E$ через $G∖E′$ обозначим граф, получающийся из графа $G$ удалением всех его ребер, входящих в $E ′$ , т.е. граф $(V,E∖E′)$ .

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть $G$ — связный граф, и пусть $E1$ и $E2$ — два непересекающихся множества его ребер. Обозначим через $ni$ ( $i= 1,2$ ) количество компонент связности графа $G ∖Ei$ . Тогда количество компонент связности графа $G ∖(E1∪ E2)$ не меньше, чем $n1+ n2− 1$ .

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство. Пусть в графе $H = G∖(E1∪E2)$ ровно $k$ компонент связности. Если добавить к $H$ все ребра из множества $E2$ , то получится $n1$ компонент связности. Поэтому если мы будем последовательно добавлять в граф $H$ те ребра из $E2$ , которые уменьшают число компонент связности, то, добавив в точности $k− n1$ ребер из $E2$ , получим $n1$ компонент связности (поскольку добавление каждого ребра уменьшает число компонент связности не более, чем на 1). Добавление остальных ребер из $E2$ уже не уменьшит количество компонент связности. Аналогично к графу $H$ можно добавить такие $k − n2$ ребер из множества $E1$ , что в итоге получаются все $n2$ компонент связности графа $G∖E2$ . Но если к графу $H$ добавить и те, и другие ребра (в общей сложности $(k − n )+ (k− n ) 1 2$ ребер), то граф станет связным. Следовательно, $(k− n)+ (k− n )≥ k− 1 1 2$ и, значит, $k ≥n + n − 1 1 2$ .

_________________________________________________________________________________________________________________________________________________________________________________

Обозначим через $vX$ и $vY$ количества вершин в множествах $X$ и $Y$ . Пусть $EX$ — множество ребер, хотя бы один конец, который лежит в $X$ , а $EY$ — множество ребер, хотя бы один конец которых лежит в $Y$ . Поскольку между вершинами из $X$ и $Y$ нет ни одного ребра, множества $EX$ и $EY$ не пересекаются. Тогда в графе $G ∖EX$ ровно $vX +m$ компонент связности (среди них $vX$ компонент состоят из одной вершины), в графе $G∖EY$ ровно $vY + n$ компонент связности, а в графе $G ∖(EX ∩EY )$ ровно $k+ vX + vY$ компонент связности, где $k$ — число компонент связности в графе $G− X − Y$ . Тогда по лемме

k+ vX + vY ≥ (vX + m)+ (vY +n)+ 1,

следовательно, $k≥ m + n− 1$ .

Ответ:

$m + n− 1$

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

Задача 6#70486

Есть $2n$ карточек, на каждой написано число от $1$ до $n$ (каждое — ровно на двух карточках). Карточки лежат на столе числами вниз. Набор из $n$ карточек называется хорошим, если на них каждое число встречается по одному разу. Барон Мюнхаузен утверждает, что он может указать $80$ наборов по $n$ карточек, из которых хотя бы один заведомо окажется хорошим. При каком наибольшем $n$ слова барона могут быть правдой?

Источники: СпбОШ - 2022, задача 11.7(см. www.pdmi.ras.ru)

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

Подсказка 1

Задача непростая, поэтому давайте сначала "причёсывать" её, наблюдать какие-то интересные свойства. Например, если у нас набор из n карточек хороший, то оставшиеся n карточек тоже образуют хороший набор(пусть дополнительный набор). Понятно, что слишком большое n взять не получится. Попробуйте изучить, перебрать какие-то n. Понятно, что n=10, наверное, уже слишком много, а n=5, n=6 маловато.

Подсказка 2

Надеюсь, вы порешали сами задачку, и догадываетесь какое примерно максимальное n, а может у вас получилось построить пример для него. При n = 8 и больше уже указать такой набор будет нельзя, т.е. ответ к задаче n = 7. Понятно, что если докажем для 8, то и для больших тоже. Наша цель — предъявить такой способ разметки карточек, чтобы ни один из 80 выбранных наборов не оказался хорошим. Давайте в наших 80 произвольных наборах рассмотрим какую-то карточку A. Можем ли мы сделать так, чтобы она была во всех наборах?

Подсказка 3

Да, меняя наш набор на дополнительный, мы добьёмся присутствия A во всех наборах. А дальше нам глобально нужно убрать плохие наборы, чтобы остались хорошие, но в конце концов, продолжая так делать, всё равно останется плохой набор. Мы докажем, что всегда можно так занумеровать карточки, что все 80 наборов окажутся плохими. Давайте этим и займёмся. Попробуйте понять с помощью принципа Дирихле, хотя бы сколько ещё других карточек B у нас будет? Тогда сколько наборов у нас может оказаться плохими, если цифра на B будет такая же, как у A?

Подсказка 4

Давайте просто аккуратно посчитаем. Оставшихся карточек всего у нас 80 * 7 = 560. А оставшихся карточек, кроме A, у нас 15. Отсюда по принципу Дирихле у нас будет хотя бы 38 карточек B(обозначение из предыдущей подсказки). И вот теперь у нас есть хотя бы 38 наборов с карточками A и B! Тогда пусть на них и оказалось какое-то число 8, теперь все эти наборы плохие. У нас остались 14 карточек(A и B мы убрали) и не больше 42 наборов, где в теории ещё может быть хороший. А теперь аналогично делаем дальше! Попробуйте проделать эти же шаги самостоятельно(их не так много, поэтому лучше, чтобы избежать путаницы и ошибок, сделать всё). Теперь, дойдя до конца процесса, поймите, почему мы доказали оценку? Сколько наборов и карточек остаётся на последнем шаге?

Подсказка 6

Ага, на последнем шаге должен был остаться 1 набор и 4 карточки. Тогда, написав на двух из них число 2, а на двух других число 1, мы победим(даже с запасом)! Мы доказали то, что было написано в 3 подсказке. Осталось разобраться с примером. Мы увидели, что 80 карточек хватает с запасом, поэтому, скорее всего, достаточно брать меньше наборов и среди них будет один хороший. Подумайте, сколько будет достаточно? Это число явно выражается через n.

Подсказка 7

Покажем, что для 2n карточек, мы можем выбрать 2^(n-1) наборов, среди которых точно есть один хороший. Это можно сделать по индукции. База понятна. Пусть на столе лежит 2n+2 карточки, а для 2n мы доказали. Попробуем взять 2 произвольные карточки. Какие варианты тогда возможны? Нужно рассмотреть их и применить предположение индукции!

Подсказка 8

Ага, возможны два варианта: мы вытащили карточки с одинаковыми числами или с различными. Первый случай совсем несложный и делается почти сразу. А во втором попробуйте объединить оставшиеся непарные карточки мысленно в одну и снова применить предположение индукции. Повозитесь со всем этим и у вас получится! Ну а исходную задачу мы тем самым решаем, так как 64<80. Победа!

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

Заметим, что если набор из $n$ карточек хороший, то набор из оставшихся $n$ карточек тоже хороший(назовём его дополнительным набором).

Покажем, что для $n≥ 8$ нельзя так указать $80$ наборов, чтобы хотя бы один из них оказался хорошим. Для этого достаточно убедиться в том, что при $n = 8$ нельзя указать такие $80$ наборов. Поскольку, барон выбирает наборы карточек, не зная, какие числа написаны на этих карточках снизу, мы можем считать, что изначально на карточках не было никаких надписей, а числа на карточках появляются уже после того, как выбор сделан. Наша цель — предъявить такой способ разметки карточек, чтобы ни один из $80$ выбранных наборов не оказался хорошим.

Итак, пусть выбрано $80$ наборов. Рассмотрим произвольную карточку $A.$ Меняя некоторые наборы на дополнительные, можно добиться того, что карточка $A$ будет присутствовать во всех наборах. Перечислим с учётом кратности все остальные карточки, встречающиеся в этих наборах. Всего будет перечислено $80⋅7= 560$ карточек. Кроме карточки $A$ у нас имеется $15$ карточек, значит, какая-то из них встретится не менее $38$ раз(так как $37⋅15 =555< 560$ ), назовём её карточкой $B.$ Напишем на карточках $A$ и $B$ число $8,$ тогда те $38$ (или более) наборов, в которых встречаются обе эти карточки, будут плохими. Уберём карточки $A$ и $B,$ останется $14$ карточек и $42$ (или менее) набора, среди которых должен найтись хотя бы один хороший.

Аналогично зафиксируем одну из оставшихся карточек $C$ и переделаем наборы так, чтобы карточка $C$ входила во все наборы. Выписав все остальные карточки, встречающиеся в наборах, получим $42⋅6= 252$ карточки. Поскольку, помимо карточки $C,$ у нас имеется $13$ карточек, какая-то из них — назовём её $D$ — встретится $20$ раз(так как $19⋅13= 247 <252$ ). Напишем на карточках $C$ и $D$ число 7 — в результате все эти наборы станут плохими. Уберём карточки $C$ и $D,$ останется $12$ карточек и $22$ набора, среди которых опять должен найтись хороший.

Действуя аналогично, получим, что какие-то две карточки встретятся вместе хотя бы в $212⋅15= 10$ наборах, напишем на них число $6$ и выкинем, останется $10$ карточек и $12$ наборов. Тогда, поскольку $12⋅94= 513,$ какая-то пара карточек встретится в одном наборе хотя бы $6$ раз. Написав на этих карточках число $5$ и выкинув, мы получим $8$ карточек и $6$ наборов. Какая-то очередная пара карточек встретится в одном наборе хотя бы $6⋅37 =2 47$ раз, напишем на них число 4 и выкинем, в результате получим $6$ карточек и $3$ набора. Далее какая-то пара карточек встретится в одном наборе хотя бы $3⋅25 = 115$ раз, записываем на них число $3$ и выкидываем, останется $4$ карточки и $1$ набор. Напишем на двух карточках из этого набора число $1,$ а на двух других — число $2,$ тогда и этот набор также окажется плохим. Мы доказали, что всегда можно так занумеровать карточки, что все $80$ наборов окажутся плохими.

Покажем теперь, что для $2n$ карточек всегда можно выбрать $2n−1$ наборов так, чтобы хотя бы один из них оказался хорошим. В нашем случае $n= 7$ и мы сможем выбрать $26 =64< 80$ наборов, что решает задачу. Набор из $2n$ карточек, на которых записаны $n$ различных чисел(каждое — в двух экземплярах), будем называть двойным.

Пример 1. Докажем индукцией по $n,$ что для любого двойного набора из $2n$ карточек всегда можно предъявить $2n−1$ наборов, среди которых есть хороший. База $n =1$ очевидна.

Пусть на столе лежит двойной набор из $2n+ 2$ карточек. Попробуем наудачу выбрать из них две одинаковые карточки, взяв произвольные карточки $a$ и $b.$ Самоуверенно отложим их в сторону. Если мы угадали, то на столе остался двойной набор из $2n$ карточек, для которого, применив предположение индукции, можно указать $2n−1$ наборов, среди которых есть хороший. Теперь для каждого указанного набора $M$ рассмотрим наборы

Ma = M ∪{a}, Mb = M ∪{b}.

Мы утверждаем, что среди наборов $M b$ и $Ma$ (а их в сумме получается ровно $2n$ штук) непременно найдётся хороший(для исходного множества карточек) набор. Если карточки $a$ и $b$ и в самом деле одинаковые, это очевидно — подойдут даже два набора.

Предположим теперь, что на карточках $a$ и $b$ написаны разные числа(обозначим их также $a$ и $b$ ). Тогда в оставшемся множестве из $2n$ карточек были “непарные” карточки с числами $a$ и $b$ — мысленно соединим их в новую пару и применим предположение индукции, указав $n−1 2$ наборов, среди которых есть хороший набор $M,$ содержащий по одной карточке из каждой пары. На самом деле он содержит ровно одно из чисел новой пары, скажем $a,$ и по одному представителю всех остальных пар. Но тогда набор $Mb$ в исходном множестве карточек является хорошим!

Пример 2. Построим граф, вершинами которого являются карточки. Каждую пару карточек с одинаковыми числами соединим красным ребром. Проивзольным образом разобьём карточки на пары и соединим карточки в каждой паре синим ребром. Полученный красно-синий граф(на самом деле мультиграф, поскольку между одной парой вершин может быть проведено и красное, и синее ребро) представляет собой несколько циклов чётной длины. Рассмотрим такой набор его вершин, что в каждом цикле вершины выбраны через одну, назовём его чередующимся набором. Тогда в этом наборе будет присутствовать ровно один конец каждого красного ребра и, значит, он будет хорошим. Проблема в том, что мы, т.е. Мюнхгаузен, не знаем как именно проведены красные рёбра. Но заметим, что любой чередующийся набор содержит ровно по одной вершине каждого синего ребра. Поэтому, указав все $n 2$ наборов, содержащих ровно по одной вершине каждого синего ребра, мы заведомо укажем и чередующийся набор. Поскольку набор и его дополнение лишь одновременно могут быть чередующимися, из каждой пары взаимодополняющих наборов достаточно брать только один. Стало быть, достаточно указать лишь $n−1 2$ наборов.

Ответ:

при $n = 7$

Курсы

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

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

Задача 7#71955

Клетки таблицы $100×100$ окрашены в белый цвет. За один ход разрешается выбрать любые $99$ клеток из одной строки или из одного столбца и перекрасить каждую из них в противоположный цвет — из белого в черный, а из черного в белый. За какое наименьшее количество ходов можно получить таблицу с шахматной раскраской клеток?

Источники: СпбОШ - 2021, задача 11.2(см. www.pdmi.ras.ru)

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

Подсказка 1

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

Подсказка 2

Посмотрим на диагональ, покрашенную в чёрный цвет. В ней 100 чёрных клеток, и при перекрашивании одной из них мы никак не меняем окрас другой. А значит, всего было сделано >= 100 ходов. Теперь попробуем привести пример на 100.

Подсказка 3

Попробуем в столбцах под номерами вида 2n+1 не красить клетку с номером 2n+1. То же самое сделаем со строками. Попробуйте доказать, что в этом случае мы получим шахматную раскраску.

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

Оценка.

Покажем, что $100$ ходов обязательно придётся сделать.

Первый способ. Предположим, что мы получили шахматную раскраску. Рассмотрим диагональ, покрашенную в чёрный цвет. За ход можно перекрасить не более одной клетки этой диагонали, следовательно, потребовалось не менее $100$ ходов.

Второй способ. Предположим, что мы сделали менее $100$ ходов. Тогда найдётся строка, которую мы не задействовали. Но в этой строке в результате появилось $50$ чёрных клеток, значит, было сделано как минимум $50$ “вертикальных” ходов. Аналогично показывается, что было сделано как минимум $50$ “горизонтальных” ходов, т.е. всего не менее $100$ ходов.

Пример.

Покажем, как за $100$ ходов можно получить шахматную раскраску, для этого перекрасим первый столбец без первой клетки, третий столбец без третьей клетки, пятый столбец без пятой клетки, $...,$ $99−$ й столбец без $99−$ й клетки. Дальше перекрасим первую строку без первой клетки, третью строку без третьей клетки, пятую без пятой клетки, $...,$ $99−$ ю строку без $99−$ й клетки. Тогда все клетки, у которых номер строки и номер столбца имеют разную чётность, окажутся переркашенными ровно один раз и, значит, чёрными, а остальные клетки будут белыми.

Ответ:

$100$ ходов

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

Задача 8#71934

$N$ олигархов построили себе страну с $N$ городами, каждый олигарх владеет ровно одним городом. Кроме того, каждый олигарх построил несколько дорог между городами: любая пара городов соединена максимум одной дорогой каждого из олигархов (между двумя городами может быть несколько дорог, принадлежащих разным олигархам). Суммарно было построено $d$ дорог. Некоторые олигархи хотели бы создать корпорацию, объединив свои города и дороги так, чтобы при этом из любого города корпорации можно было доехать до любого другого ее города по дорогам этой корпорации, возможно, заезжая по дороге в города других олигархов. Но оказалось, что никакая группа олигархов создать корпорацию не может! При каком наибольшем $d$ это возможно?

Источники: СпбОШ - 2020, задача 11.7(см. www.pdmi.ras.ru)

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

Пронумеруем олигархов и их города числами от $1$ до $N$ соответственно.

Пример.

Пусть дорога между городами $i$ и $j$ принадлежит олигарху под номером $k$ тогда и только тогда, когда $k > i,k> j.$ Тогда количество дорог равно

(N − 1)(N − 2) (N − 2)(N − 3) 2⋅1 -----2----- + -----2-----+ ...+ -2-= 1 ( 2 2 2 2 ) = 2 (N( − 1) − (N − 1)+(N − 2) − (N)− 2)+ ...+ 2 − 2 +1 − 1 = = 1 N(N-− 1)(2N-−-1)-− N-(N-−-1) = N-(N-−-1)(N-− 2) 2 6 2 6

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

Оценка 1.

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

Рассмотрим произвольную тройку олигархов $A,B$ и $C.$ Докажем, что эта тройка сопоставлена не более чем одной дороге.

Предположим, что это не так. Выбраниая тройка олигархов может быть сопоставлена всего трем дорогам (если таковые имеются): дороге $BC,$ принадлежащей олигарху $A,$ дороге $AC,$ принадлежащей $B,$ и дороге $AB,$ принадлежащей $C.$ Легко видеть, что каким бы двум из этих дорог ни была сопоставлена тройка $A,B,C,$ эта тройка олигархов сможет образовать корпорацию. Следовательно, каждая тройка олигархов сопоставлена не более одной дороге, т. е. дорог не более $C3N .$

Заметим, что в нашем примере любая тройка олигархов $i< j < k$ сопоставлена дороге $ij,$ принадлежащей олигарху $k,$ т. е. всего $C3N$ дорог, что дает комбинаторный способ подсчета количества дорог в примере.

Оценка 2.

Рассмотрим граф, в котором вершиины — это города, а ребра цвета $i$ — дороги, принадлежащие олигарху номер $i.$ Заметим, что если из графа, удовлетворяющего условию задачи, удалить часть вершин, выходящие из них ребра и все ребра, принадлежащие олигархам-владельцам удаляемых вершин, то для оставшегося графа условие задачи о невозможности построить корпорацию продолжит выполняться.

Докажем индукцией по $N,$ что если в графе $N$ вершин, то при удалении любой вершины, всех ее ребер и всех ребер соответствующего ей цвета суммарное количество ребер уменьшается не более чем на $(N−1)(2N−2).$

База $N = 2$ очевидна.

Переход. Пусть мы хотим удалить олигарха номер $N$ . Так как все $N$ олигархов не могут образовать корпорацию, граф на. ребрах всех цветов несвязен. Обозначим через $U$ компоненту связности, содержащую город олигарха номер $N$ , через $V$ — объединение всех остальных компонент связности, а через $u$ и $v$ — количество вершин в $U$ и $V$ соответственно. Тогда подграф $V$ содержит не более $v(v−1) 2$ ребер $N$ -го цвета. Далее, из вершины $N$ выходит не более $v(u− 1)$ ребер с цветами, соответствующими вершинам из $V.$ Наконец, применяя к графу $U$ индукционное предположение, получаем, что в графе $U$ имеется не более $(u−1)(u−2) 2$ ребер, имеющих цвет $N$ или выходящих из вершины $N.$ Следовательно, при удалешии вершины $N$ исчезнет не более

v(v− 1)+ v(u− 1)+(u−-1)(u−-2)= 2 (v+2u− 1)(v+ u− 2) (N − 1)(N − 2) = -------2--------= -----2-----

ребер.

Для доказательства оценки будем по одной удалять вершины, подсчитывая, сколько ребер при этом пропадает. Получается, что мы удалили не более $C2N−1+ C2N−2+ ...+ C22 = C3N$ ребер. Заметим, что если в нашем примере удалять олигархов в порядке убывания номеров, то при удалении олигарха номер $k$ будет пропадать в точности $(k−1)(k2−2)$ ребер. Следовательно, в любом графе ребер не больше, чем в построенном нами примере.

Ответ:

максимальное число дорог равно $N(N-−1)(N−2) 6$

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

Задача 9#73686

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

$1$ ) каждый состоит ровно в одной группе;

$2$ ) каждая группа связна в указанном выше смысле;

$3$ ) одна из групп содержит от $1$ до $100$ членов, а каждая из остальных от $100$ до $900$ членов.

Источники: СпбОШ - 2020, задача 10.6(см. www.pdmi.ras.ru)

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

Социальная сеть представляет собой граф, в котором люди - это вершины, а отношение “дружба” — ребра. Достаточно рассмотреть случай, когда этот граф является деревом. В требованиях условия задачи группу, в которой состоит от $1$ до $100$ членов, будем называть малой, а группу, где от $100$ до $900$ членов, — большой. Докажем утверждение задачи индукцией по числу пользователей сети. База индукции: $n ≤900.$ Если в сети не более $100$ пользователей, объявим их всех малой группой. Если в сети от $101$ до $900$ пользователей, назначим малой группой любого пользователя, соответствующего висячей вершине, а всех остальных запишем в большую группу.

Индукционный переход. Достаточно проверить, что если число пользователей больше $900,$ то можно подобрать большую группу, при удалении которой граф останется связным. Подвесим наше дерево и рассмотрим наиболее далекую от корня вершину $A$ (одну из вершин), у которой больше $900$ потомков. У каждого из сыновей вершины $A$ не более $900$ потомков, при этом количество сыновей — не более $9.$ Если у каждого из сыновей $A$ не более $99$ потомков, то в сумме у $A$ не более $9⋅99< 900$ потомков, что противоречит выбору вершины $A.$ Значит, один из сыновей $A$ имеет от $100$ до $900$ потомков, назначим его и его потомков большой группой.

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

Задача 10#71909

В начале игры у Малыша и Карлсона есть один кусок шоколадки в виде квадрата $2019× 2019$ клеточек. Каждым ходом Малыш делит какой-нибудь кусок по клеточкам на три прямоугольных куска, а Карлсон съедает один из этих трёх кусков по своему выбору. Игра заканчивается, когда сделать очередной ход невозможно. Если всего было сделано чётное число ходов — побеждает Малыш, если нечётное — Карлсон. Кто выигрывает при правильной игре?

Источники: СпбОШ - 2019, задача 11.3(см. www.pdmi.ras.ru)

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

Назовем кусок шоколадки $большим,$ если его можно разрезать, и $малым,$ если нельзя. Изначально есть только один большой кусок, а в конце игры их $0.$ Карлсон может играть так, чтобы четность количества больших кусков после его хода обязательно менялась: один большой кусок уничтожается ходом Малыша, после чего появляется от $0$ до $3$ новых больших кусков. Если количество новых больших кусков нечетно, то один точно есть и Карлсон его съест. Если же количество больших кусков четно, то есть хотя бы один малый и Карлсон съест именно малый кусок. Итак, число больших кусков после каждой пары полуходов меняет четность, а по окончании игры чётность чисел больших кусков должна измениться, значит, будет сделано нечётное количество ходов, т.е. Карлсон выиграет.

Ответ: Карлсон

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

Задача 11#71912

Пусть между городами $A,B,C$ и $D$ есть дороги $AB$ и $CD,$ но нет дорог $BC$ и $AD.$ Назовем пеpecтройкой замену пары дорог $AB$ и $CD$ на пару дорог $BC$ и $AD.$ Изначально в стране было несколько городов, некоторые пары городов были соединены дорогами, причем из каждого города выходило по $100$ дорог. Министр нарисовал новую схему дорог, в которой из каждого города по-прежнему выходит $100$ дорог. Известно, что как в старой, так и в новой схемах никакие два города не соединены более, чем одной дорогой. Докажите, что новую схему можно получить из старой с помощью нескольких перестроек.

Источники: СпбОШ - 2019, задача 11.6(см. www.pdmi.ras.ru)

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

Рассмотрим множество $M,$ состоящее из всех возможных $100$ -регулярных(степени всех вершин в графе равны 100) графов на данном множестве вершин $V$ (наши две схемы дорог — среди них). Докажем что любые два графа из $M$ можно перевести друг друга серией перестроек. Для двух графов $′ G,G ∈ M$ пусть $′ F(G,G )$ - множество необщих рёбер этих графов, а $′ ′ f(G,G )= |F (G,G )|$ . Очевидно, что число $′ f (G,G )$ всегда четно, и в множестве $′ F (G,G )$ поровну рёбер из $G$ и $′ G .$

Предположим, что существуют пары непереводимых друг в друга перестройками графов в $M.$ Рассмотрим такую прару графов $(A,B)$ с минимальным $f(A,B).$ Граф $H = (V,F (A,B ))$ имеет в каждой вершине поровну рёбер из $A$ и из $B$ . Следовательно, в $H$ существует чередующийся цикл(в котором рёбра $A$ и $B$ чередуются). Рассмотрим цикл $Z =a1a2...a2k$ с минимальным числом вершин(это не обязательно простой цикл, вершины в нем могут повторяться). Первая наша цель - найти на этом цикле четыре последовательные различные вершины. В самом деле, пусть среди $a1,a2,a3,a4$ есть совпадающие. Очевидно, возможно лишь совпадение $a1 =a4$ . Так как рёбра цикла не повторяются, тогда $a2 ⁄= a5$ и в качестве искомой четверки подойдет $a2,a3,a4,a5.$

Итак, не умаляя общности будем считать, что все вершины $a1,a2,a3,a4$ различны, причем $a1a2,a3a4 ∈$ $E(A)$ и $a2a3 ∈ E(B).$ Рассмотрим три случая.

(а) $a1a4 ∈E (B ).$ Тогда проведем перестройку $a1a2a3a4$ в графе $B$ (это возможно, так как $a1a2,a3a4∈∕E(B)$ ) и получим граф $C$ с $f(A,C)= f(A,B)− 2.$ По предположению, $C$ можно получить из $A$ перестройками, значит, можно получить и $B.$

(b) $a1a4 ∈ E(A )∖E(B)$ . Тогда $a1a4a5...a2k$ — чередующийся цикл, меньший чем $Z,$ противоречие.

(c) $a1a4 ∕∈E (A)∪ E(B).$ Тогда проведем перестройку $a1a2a3a4$ в графе $A$ (это возможно, так как $a2a3,a4a1 ∕∈$ $E (A))$ и получим граф $C$ с $f(B,C )=f(A,B)− 2.$ По предположению, $C$ можно получить из $B$ перестройками, значит, можно получить и $A.$

Интенсивы

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

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

Задача 12#71900

У Васи есть $100$ карточек трёх цветов, карточек каждого цвета не больше $50.$ Докажите, что он может выложить из них квадрат $10 ×10$ так, чтобы любые две соседние (по стороне) карточки оказались разного цвета.

Источники: СпбОШ - 2018, задача 11.2(см. www.pdmi.ras.ru)

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

Пусть для определённости карточки были красного, синего и зеленого цветов и меньше всего было карточек зелёного цвета. Тогда зелёных карточек не более $33.$ Покрасим клетки квадрата $10× 10$ в шахматном порядке так, что левый нижний угол квадрата чёрный. Начнём раскладывать красные карточки на черные клетки, начиная с левого нижнего угла квадрата. Сначала будем заполнять слева направо чёрные клетки из нижней строки, затем также слева направо чёрные клетки из второй снизу строки и т.д. до тех пор, пока не разложим все красные карточки. Далее разложим синие карточки на белые клетки, начиная с левого верхнего угла доски. Сначала будем заполнять слева направо белые клетки из верхней строки и т.д. до тех пор, пока не разложим все синие карточки. На оставшиеся клетки разложим зелёные карточки. Покажем, что никакие зелёные карточки не могут оказаться рядом (для красных и синих карточек это очевидно). Поскольку красных и синих карточек вместе не менее $67$ штук, а в строке лежит не более пяти карточек каждого из этих цветов, количество строк, занимаемых красными карточками, и количество строк, занимаемых красными карточками, вместе не меньше $12.$ Поэтому есть строка, которая целиком заполнена красными и синими карточками. Но тогда зелёные карточки над этой строкой лежат на белых клетках (и значит, не рядом), а зелёные карточки под этой строкой лежат на чёрных клетках(и значит, тоже не рядом).

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

Задача 13#71905

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

Источники: СпбОШ - 2018, задача 11.5(см. www.pdmi.ras.ru)

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

Пусть в графе нашёлся цикл, и пусть он проходит по горизонтальному отрезку $a 0$ слева направо. Возьмём ромб, примыкающий к стороне $a0,$ и отметим в нём параллельную сторону $a1.$ Возьмём ромб, примыкающий к стороне $a1,$ и отметим в нём параллельную сторону $a2$ и т.д.

Такую же конструкцию провернём в другую сторону: возьмём ромб, примыкающий к отрезку $a0$ с другой стороны, и отметим в нём параллельную сторону $a−1,$ и т.д.

$PIC$

Мы получили “полосу ширины $a$ ”, которая рассекает наш шестиугольник. При этом цикл заведомо пересекает эту полосу, но всё время в направлении слева направо. Это невозможно.

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

Задача 14#72171

На круглом ожерелье висят $2n > 3$ бусинок, каждая покрашена в красный или синий цвет. Если у какой-то бусинки соседние с ней бусинки покрашены одинаково, ее можно перекрасить (из красного в синий или из синего в красный). Можно ли из любой исходной раскраски бусинок сделать ожерелье, в котором все бусинки покрашены одинаково?

Источники: СпбОШ - 2018, задача 9.4(см. www.pdmi.ras.ru)

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

Подсказка 1

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

Подсказка 2

Какой самый простой инвариант мы знаем? Инвариант по четности какой-то величины. Посмотрите на количество пар соседних красных бусинок...

Подсказка 3

Это действительно инвариант, ведь если мы имели участок ожерелья (к)(c)(к) и мы перекрасили центральный, количество увеличилось на 2, а если (к)(к)(к), уменьшилось на 2 (если мы меняли участок вида (с)(?)(c) эта величина не изменилась). В любом случае четность не поменялась. Не трудно увидеть, что тоже самое можно сказать про четность количества пар соседних синих бусинок. Как тогда построить контрпример?

Подсказка 4

Давайте посмотрим на значение инвариантов при одноцветной раскраске: в любом случае бусинок какого-то цвета не будет, а это значит, что количество таких пар будет просто 0, т.е. четное число. Тогда нам нужно придумать такой пример, что изначально количество пар соседних красных и количество пар соседних синих бусинок были нечетными числами. Я в вас верю!

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

Докажем, почему ожерелья с чётным количеством бусинок нам не подходят. Легко убедиться, что при любом перекрашивании количество пар соседних бусинок вида (к)-(к) либо не меняется, либо меняется ровно на $2,$ т.е. в любом случае не меняется четность этого числа. То же самое верно и про число пар вида (с)-(с). В одноцветном ожерелье четной длины оба эти количества четны. Поэтому из ожерелья, в котором оба эти количества нечетны, нельзя получить ни одно из двух одноцветных ожерелий. При четном n таково, например, ожерелье (к)-(к)-(с)-(с)- $...$ -(с)(не забываем, что у нас ожерелье имеет форму окружности).

Варианты правильных ответов:

нет
Нет
нельзя
Нельзя

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

Задача 15#71261

Ученики школы посещают $m$ кружков. В каждый кружок ходит ровно $mk$ детей. Докажите, что можно рассадить всех учеников школы по $k$ кабинетам так, чтобы в каждом кабинете был хотя бы один представитель каждого кружка ( $m$ и $k$ — натуральные числа).

Источники: СпбОШ - 2017, задача 11.1(см. www.pdmi.ras.ru)

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

Выберем $k$ учеников из первого кружка, рассадим их в разные кабинеты. Выберем $k$ других человек из второго кружка и рассадим их, и так далее.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Ученики школы посещают $N$ кружков. В каждый кружок ходит ровно $mk$ детей. Всех учеников можно рассадить по $k$ кабинетам так, чтобы в каждом кабинете был хотя бы один представитель каждого кружка, даже если $N$ существенно больше $m.$ Ниже мы докажем, что это можно сделать при $m∕2 N ≈ e .$

Рассмотрим $k+ a$ комнат, где число $a$ определим позже. Посадим каждого школьника в одну из этих комнат, выбирая ее случайно (все комнаты равновероятны). Назовем комнату подозрительной, если в ней оказались представители не всех кружков. Предположим, что случилась УДАЧА: оказалось не более чем $a$ подозрительных комнат. Тогда имеется $k$ неподозрительных комнат, мы можем назвать их кабинетами, и искомая рассадка найдена. УДАЧА заведомо иногда случается, если математическое ожидание $E$ числа подозрительных комнат меньше $a+ 1.$ Заметим, что $E$ равно количеству комнат $k+ a,$ умноженному на вероятность того, что конкретная комната подозрительна. Эта вероятность, в свою очередь, не превосходит $( )km N 1 −k1+a .$ Итак, если

( ) N (k+a) 1 −--1- km < a+ 1 k +a

то при таком $N$ требуемая рассадка существует. Уже при $a =k$ получается экспоненциальное по $m$ выражение, наилучшего результата — около $em-−1 m$ — можно добиться при $a ≈ -k-. m−1$

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

Задача 16#71374

В стране некоторые математики знакомы между собой и при любом разбиении математиков на две непустые группы найдутся двое знакомых из разных групп. Известно, что если посадить за круглый стол любой набор из $4$ или более математиков так, чтобы любые два соседа были знакомы, то за столом найдутся двое знакомых, не сидящих рядом. Обозначим через $ci$ количество наборов из $i$ попарно знакомых математиков. Докажите, что

c1− c2+ c3− c4+ ...= 1.

Источники: СпбОШ - 2017, задача 11.6(см. www.pdmi.ras.ru)

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

Рассмотрим граф знакомств математиков. По условию этот граф хордовый, т.е. в нем любой цикл из $4$ или более вершин содержит хорду (пару смежных вершин, не соседних в цикле). Докажем, что для хордового графа $G$ выражение $f(G):= c1− c2+ c3− ...,$ где $ci$ — количество клик (полных подграфов) в $G$ на $i$ вершинах, равно числу $k(G)$ компонент связности графа $G.$

Предположим, что это не так, и рассмотрим в качестве $G$ наименьший по числу вершин контрпример. Ясно, что граф $G$ содержит больше одной вершины и связен (иначе одна из компонент связности была бы меньшим контрпримером). Удалим из графа $G$ произвольную вершину $v,$ пусть новый граф $G∖v$ распался на компоненты $G1,...,Gk.$ Пусть $H1$ , $H2,...,Hk$ — подграфы в $G1,...,Gk$ соответственно на соседях вершины $v.$ Несложно видеть, что

k k f(G)= 1+ ∑ f (Gi)− ∑ f(Hi) i=1 i=1

где слагаемое $1$ соответствует клике ${v},$ слагаемые $f(Gi)$ — кликам, не содержащим $v,$ слагаемые — $f(Hi)$ — кликам, содержащим $v$ (при удалении из них вершины $v$ меняется четность, а стало быть, знак в выражении для $f$ ). В силу минимальности контрпримера $f (Gi)= 1,f (Hi)= k(Hi).$ Проверим, что $k(Hi)= 1$ при всех $i.$ Предположим противное, тогда вершины одного из графов $Hi$ можно разбить на два непустых подмножества $− + V ,V$ так, что ни одно ребро не ведет из $− V$ в $+ V .$ Рассмотрим наименьший по числу ребер путь $x...y$ из $− V$ в $+ V$ в графе $Gi.$ Тогда цикл $vx...yv$ не имеет хорды в графе $G.$

Мы проверили, что $f (Hi)= f(Gi)$ при всех $i.$ Тогда по формуле $(∗)$ $f(G)= 1= k(G ),$ т. е. граф $G$ оказался неконтрпримером.

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

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

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

Задача 17#70500

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

$PIC$

Какое наибольшее количество не бьющих друг друга ладей можно расставить на поверхности куба $50 ×50× 50?$

Источники: СпбОШ - 2016, задача 11.2(см. www.pdmi.ras.ru)

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

Оценка
Назовем ободком множество клеток, находящихся в одном ряду, а также на продолжении этого ряда за одно или несколько ребер. Каждая ладья держит под боем клетки двух ободков. Всего на поверхности куба имеется $150$ ободков (есть три возможных направления, по $50$ ободков в каждом). На каждом ободке может стоять не более одной ладьи, и любая ладья стоит на двух ободках. Поэтому ладей не может быть больше $75.$

Пример
Рассмотрим три соседние грани и поделим каждую на $4$ квадрата $25× 25$ . Далее в трех квадратах, указанных на рисунке, поставим ладьи на одной из главных диагоналей.

$PIC$

Ответ:

$75$ ладей

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

Задача 18#70630

В стране $50$ городов, каждые два города соединены (двусторонними) авиалиниями, цены всех перелетов попарно различны (для любой пары городов цена перелета «туда» равна цене «обратно»). В каждом городе находится турист. Каждый вечер все туристы переезжают: богатые туристы — по самой дорогой, бедные — по самой дешевой линии, ведущей из соответствующего города. Через $k$ дней оказалось, что в каждом городе снова по одному туристу. За это время ни один турист не посетил никакой город дважды. При каком наибольшем $k$ такое возможно?

Источники: СпбОШ - 2016, задача 11.6(см. www.pdmi.ras.ru)

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

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

Допустим, что среди туристов имеется $25$ (или более) «богачей». Нарисуем граф: вершины — это города, из каждого города проведем самый дорогой выходящий путь. Тогда этот граф представляет собой лес, в каждом дереве которого все ребра направлены к корню, за исключением единственного ребра, выходящего из корня, — это ребро в дереве как бы двустороннее. Возьмем богача, который расположен ближе всего к корню своего дерева. Этот богач будет в течение $25$ ходов самым близким к корню. Значит, он проедет по городам, в которых еще не было других богачей. Это может быть только если граф — это путь из $50$ вершин, богачи занимают первые $25$ вершин этого пути (т. е. половину) и гуськом движутся по этому пути в сторону второй половины. Отсюда следует, что богачей не может быть больше $25,$ а также что количество переездов тоже не превосходит $25.$

Тогда бедных туристов тоже $25$ и они двигаются по аналогичному «бедному» пути, причем в начальный момент они занимают всю вторую половину «богатого» пути. Эти пути не имеют общих звеньев, и при этом движение бедняков таково, что с каждым ходом они должны освобождать от своего присутствия очередную вершину второй половины богатого пути, смещаясь гуськом в первую половину. Тогда движение туристов может происходить, например, следующим образом.

Обозначим города $A1,A2,...,A50.$ Допустим, что путь

A1 → A2 → A3 → ⋅⋅⋅→ A49 → A50

составлен из самых дорогих авиалиний, для определенности пусть цена перелета $Ai → Ai+1$ равна $106 − i$ рублей. А «бедный путь» пусть сначала проходит по городам с большими четными номерами, потом — по городам с большими нечетными, а далее — с малыми: сначала с четными, потом с нечетными:

A26 → A28 → ⋅⋅⋅→ A50 → A27 → A29 → ⋅⋅⋅→ A49 → → A2 → A4 → ⋅⋅⋅→ A24 → A1 → A3 → ⋅⋅⋅→ A25

Цены этих авиалинии пусть убывают от $49$ до $1$ рубля при движении вдоль этого пути. Цены остальных авиалиний назначим произвольно в диапазоне от $100$ до $100000$ рублей.

Ответ:

При $k= 25$

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

Задача 19#70351

Набор разновесов содержит по одной гире каждого из весов $1,3,5,7,9...$ граммов. Для натурального $n> 1$ докажите, что количество способов набрать этими гирями $n$ граммов не больше, чем количество способов набрать $n+ 1$ грамм.

Источники: СпбОШ - 2015, задача 11.3(см. www.pdmi.ras.ru)

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

Пусть имеется $a n$ способов выбрать $n$ граммов без использования гири в $1$ г и $b n$ способов набрать $n$ граммов с использованием гири в $1$ г.

Добавив к каждому из способов первой группы гирю в $1$ г, мы получим суммарный вес $n +1$ граммов. Значит, $bn+1 ≥an$ (способов выбрать $n$ граммов без единицы может быть равно нулю, поэтому знак больше или равно).

С другой стороны, если для каждого способа набрать $n$ граммов с использованием гири в $1$ г мы уберём эту гирю и заменим самую большую использованную гирю в этом способе на ту, которая весит на $2$ г больше, снова получится суммарный вес $n+ 1$ граммов.

Следовательно, $an+1 ≥bn$ (при нечётном $n$ появляется ещё один способ взять гири вне этого алгоритма, поэтому знак больше или равно).

Сложив полученные два неравенства, имеем требуемое.

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

Задача 20#70786

В стране Центумии некоторые пары городов соединены дорогами, причем из каждого города выходит ровно $100$ дорог. Пучком называется набор из $10$ дорог, выходящих из одного города. Докажите, что все дороги можно разбить на несколько пучков.

Источники: СпбОШ - 2015, задача 11.6(см. www.pdmi.ras.ru)

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

Рассмотрим граф $G$ , в котором вершины — это города, а рёбра — дороги. Степени всех вершин этого графа равны $100.$ Разобьем все рёбра графа $G$ на реберно непересекающиеся циклы. В каждом цикле зададим произвольно порядок обхода и ориентируем рёбра в направлении обхода цикла. Тогда в каждую вершину $G$ входит $50$ ребер и из каждой вершины выходит тоже $50$ ребер. Разобьем все ребра, выходящие из каждой вершины, на 5 пучков. Тогда все рёбра графа $G$ разобьются на пучки.

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

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


1	2	3	…	100

101	102	103	…	200

$.. .$	$.. .$	$.. .$	$.. .$	$.. .$

9901	9902	9903	…	10000