Let be a prime number. Show that one can choose fields of a chessboard such that centres of no four chosen fields are vertices of a rectangle with sides parallel to the sides of the chessboard.
Solution
Let us label the rows and the columns of the chessboard by all the pairs and , respectively, where . A field lying in the row and in the column will be called good if and only if
Given a pair , (1) holds for exactly pairs . Thus the number of good fields is in any row and in total.
It remains to show that there are no four good fields with the prohibited property. Suppose on the contrary that
for some pairs and . Subtracting (2) with a fixed yields
which (in the same way) leads to
Thus or . In view of symmetry, we can assume that . Then (3) implies that , hence , a contradiction.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.