Задача
COM-B2-M01-P014 Строки с ограниченными пересечениями
#14
★★★★☆ Уровень 4 из 5
В таблице \(n\times n\) в каждой строке отмечено ровно \(r\) клеток. Любые два столбца вместе отмечены не более чем в одной строке. Докажите, что \(n\binom r2\le\binom n2\).
Считайте пары столбцов, отмеченные в одной строке.
Каждая строка даёт \(\binom r2\) пар отмеченных столбцов, всего \(n\binom r2\) появлений. По условию каждая пара столбцов появляется не более одного раза. Всего пар столбцов \(\binom n2\). Поэтому \(n\binom r2\le\binom n2\).
Это та же идея, но в матричной форме.