Problem
COM-B2-M01-P010 Common Marked Columns
#10
★★★☆☆ Level 3 of 5
In a \(6\times6\) table, exactly \(3\) cells are marked in each row. Prove that there are two columns that are marked together in at least two rows.
Count pairs of columns marked in the same row.
Each row with \(3\) marks gives \(\binom32=3\) pairs of columns. There are \(6\cdot3=18\) pair occurrences. There are only \(\binom62=15\) pairs of columns. If each pair appeared at most once, there would be at most \(15\) occurrences, a contradiction. Hence some pair of columns appears in at least two rows.
A typical problem on “pairs inside a row”.