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