Remarks on Problem B-3 on the 1990 William Lowell Putnam Mathematical Competition

conditions (1) and (2). While it is beyond what students could reasonably be expected to solve during the exam, clearly the elegant question is: What is the maximum order of a subset S c U in which no two elements commute? We shall show that this order is 32,390, so that any subset of 32,391 matrices in U must include a commuting pair. The method we use can be applied to numerous variations of the problem posed. For our purposes, the requirement of perfect square entries creates an extra level of difficulty. Consequently, let us first solve a variation that seems more natural. We shall then return to the original question of finding the largest totally noncommuting set S when the entries must be perfect squares. Specifically, we ask what is the order of a maximum noncommuting set among all 2 X 2 matrices (a b) with nonnegative integer entries bounded by 0 < a, b, c, d < n. In this case our universal set U has (n + 1)4 matrices in it.