Let S be the set of 2 x 2 matrices each of whose elements is one of the 15 squares 0, 1, 4, ... , 196. Prove that if we select more than 154 - 152 - 15 + 2 matrices from S, then two of those selected must commute.
There are 225 diagonal matrices in the set. Any two of those commute. There also 14 (non-diagonal) matrices with equal elements and 14 other matrices with zeros on the diagonal and the other two elements equal. Any two of those 28 commute. Thus unless we leave out at least 224 + 27 matrices we will get two that commute. In other words, we are sure to get two that commute if we pick at least 154 - 152 - 25, which is slightly stronger than the required result.
51st Putnam 1990
© John Scholes
1 Jan 2001