Browse · MathNet
PrintCzech-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.
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