Skip to main content
OlympiadHQ

Browse · MathNet

Print

Czech-Slovak-Polish Match

counting and probability

Problem

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.

Techniques

Coloring schemes, extremal argumentsOther