Crux Mathematicorum CC157

Started subscription to CM magazine. I will occasionally post solutions here

Show that if a 5×5 matrix is filled with zeros and ones, there must always be a 2×2 submatrix (that is, the intersection of the union of two rows with the union of two columns) consisting entirely of zeros or entirely of ones.

Solution: Any column of the matrix will have a number with 3 or more instances of that number in that column. WLOG, assume that number is 1, and choose 3 rows. We will now consider this sub 3×5 matrix.

If the remaining 4 columns contain a column with two 1s, then we are done. Else, note that there are only 4 remaining columns with one 1 or zero 1, with one of those columns being all 0s. Hence, we will have a 2×2 submatrix of 0s.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.