Spring 2017, problem 35
Comments
This proves that any board with at least 8 rows and at least 8 columns can be covered, so now we just need to look at smaller boards.
Suppose the sets and series where n is odd,
A = { 1, 2, 3, ... n }
B = { m[1], m[2], m[3], ... m[n] } (Note m[n] denotes "m subscript n")
S[1] = 1, 2, 3, ... n
S[2] = m[1], m[2], m[3], ... m[n]
Since the set B is a rearrangement of the set A, then A = B by the defintion of sets. Furthermore, S[1] contains all the elements of set A, and S[2] contains all the elements of set B where all m[n] terms are in their rearranged positions. Now suppose the following proposition: if A = B, then the series S[1] and S[2] must have the same parity at one position.
Proof (Contrapostive) Consider when S[1] and S[2] do not have the same parity at any position. That is,
S[1] = o, e, o, e, ... o (Note that "o" and "e" denote odd and even, respectively, for convenience)
S[2] = e, o, e, o, ... e
Notice that the set A does not equal the set B because the series m[n] does not contain the same terms as the series n. Therefore the contrapositive proves that the series m[n] and n must have the same parity at one position.
From this, at least one term ( m[n] - n ) must be even since m[n] and n have the same parity. Knowing this, any integer multiplied by an integer of opposite parity is even, and any even integer multiplied by an even integer is even. Therefore,
( m[1] - 1 ) ( m[2] - 2 ) ( m[3] - 3 ) ... ( m[n] - n )
must be even if n is odd.
For this product to be even, suffice to find one term Mk-k even with k in the set (1..n).. There are (n+1)/2 Mk which are odd because they are a rearrangement of 1,2,3....n with n odd. But there are only (n-1)/2 even k in the set (1....n) so that there must be at least one Mk odd with k odd so that their difference is even.