Задача
COM-B2-M01-P010 Общие отмеченные столбцы
#10
★★★☆☆ Уровень 3 из 5
В таблице \(6\times6\) в каждой строке отмечено ровно \(3\) клетки. Докажите, что найдутся два столбца, которые вместе отмечены в одной строке хотя бы дважды.
Считайте пары столбцов, отмеченные в одной строке.
Каждая строка с \(3\) отметками даёт \(\binom32=3\) пар столбцов. Всего таких появлений пар \(6\cdot3=18\). Всего пар столбцов \(\binom62=15\). Если бы каждая пара столбцов появлялась не более одного раза, появлений было бы не больше \(15\), противоречие. Значит, некоторая пара столбцов появляется хотя бы в двух строках.
Типичная задача на “пары внутри строки”.