Problem
COM-B2-M01-P014 Rows with Limited Intersections
#14
★★★★☆ Level 4 of 5
In an \(n\times n\) table, exactly \(r\) cells are marked in each row. Any two columns are marked together in at most one row. Prove that \(n\binom r2\le\binom n2\).
Count pairs of columns marked in one row.
Each row gives \(\binom r2\) pairs of marked columns, for a total of \(n\binom r2\) occurrences. By the condition, each pair of columns appears at most once. There are \(\binom n2\) column pairs in total. Hence \(n\binom r2\le\binom n2\).
This is the same idea in matrix form.