Задание 7. Аня, Боря и Вика вырезали из клетчатой бумаги фигуру, состоящую из 35 клеток. Каждый из них отметил по 15 клеток своим цветом: Аня — жёлтым, Боря — синим, Вика — красным. Докажите, что на этой фигуре обязательно найдётся не менее 4 клеток, которые были отмечены одной и той же парой цветов. Доказательство: обозначим множества клеток, отмеченных Аней, Борей и Викой, через A, B и C соответственно. Тогда для общего количества отмеченных клеток получаем, что |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Рассмотрим пары цветов: жёлтый и синий, жёлтый и красный, синий и красный. Для каждой пары посчитаем число клеток, отмеченных обоими цветами. В сумме получим

\(|A\cap B|+|A\cap C|+|B\cap C|\).

Каждая клетка отмечена не более чем тремя цветами, поэтому в эту сумму она вносит не более 3. Следовательно, сумма не превосходит \(3\cdot35=105\).

Пусть \(x\) — число клеток, отмеченных ровно одним цветом, \(y\) — ровно двумя, а \(z\) — всеми тремя. Всего сделано \(15+15+15=45\) отметок, значит \(x+2y+3z=45\), а \(x+y+z=35\). Вычитая второе равенство из первого, получаем \(y+2z=10\).

Сумма пересечений пар равна \(y+3z=10+z\), а потому не превосходит 105. Это ограничение слишком слабое для вывода о какой-либо конкретной паре; однако из \(y+2z=10\) следует, что клеток, отмеченных ровно двумя цветами, не более 10. Эти равенства не доказывают требуемое утверждение о 4 клетках для одной пары. Более того, приведённые данные допускают разметку, в которой утверждение неверно: взять 5 клеток, отмеченных всеми тремя цветами, и 30 клеток без отметок. Тогда каждый цвет отмечает только 5 клеток, поэтому для выполнения условия нужно ещё 10 отметок каждого цвета; заданная информация не запрещает добавлять их, но доказательство требует учитывать распределение пересечений.

Из данных задачи следует требуемое утверждение проще: для каждой клетки число отметок равно 0, 1, 2 или 3. Пусть числа клеток этих типов равны \(n_0,n_1,n_2,n_3\). Тогда \(n_0+n_1+n_2+n_3=35\) и \(n_1+2n_2+3n_3=45\), откуда \(n_2+2n_3-n_0=10\). Это также не исключает, например, большого числа клеток с отметками всех трёх цветов и не устанавливает требуемую нижнюю границу для отдельной пары.

На изображении показана только начальная часть доказательства, а условие о том, что именно означает «отмечал по 15 клеток» (можно ли отмечать клетку несколькими цветами и должны ли отметки быть сделаны на разных клетках), не уточнено. При буквальном прочтении без дополнительных ограничений утверждение не следует из одних приведённых чисел: например, если все трое отметили одни и те же 15 клеток, каждая пара цветов встречается на 15 клетках; но возможны и другие распределения. Нужна оставшаяся часть решения или полное условие, чтобы корректно завершить доказательство.