Всесиб 2026, 10 класс, задача 1
( баллов) На доске на произвольным образом отмечены клеток. Докажите, что всегда можно выбрать некоторые горизонтали и некоторые вертикали так, чтобы они содержали все отмеченные клетки.
Доказательство. Обозначим за количество отмеченных клеток в вертикалях доски, по условию . Если , то , а . В этом случае можно взять максимальных вертикали, содержащие соответственно отмеченных клеток и те, не более, чем горизонтали, содержащие остальные отмеченные клетки. Если , то , поэтому и , и снова можно повторить рассуждение предыдущего случая.
Только доказано, что максимальных вертикали содержат не меньше отмеченных клеток
Замечено, что для оставшихся клеток достаточно четырёх горизонталей
Если первый пункт не доказан, то только за второй пункт (3 не ставятся)