Maths Olympiad Prep

Library / /6 of 16

Combinatorics Difficulty 5.7 AIME, harder Prove it Czech-Polish-Slovak Mathematical Match

Let pp be a prime number. Show that one can choose p3p^3 fields of a p2×p2p^2 \times p^2 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 p2p^2 rows and the p2p^2 columns of the chessboard by all the pairs (a,b)(a, b) and (c,d)(c, d), respectively, where a,b,c,d{0,1,,p1}a, b, c, d \in \{0, 1, \dots, p-1\}. A field lying in the row (a,b)(a, b) and in the column (c,d)(c, d) will be called good if and only if
acb+d(modp).(1) ac \equiv b+d \pmod{p}. \qquad (1)
Given a pair (a,b)(a, b), (1) holds for exactly pp pairs (c,d)(c, d). Thus the number of good fields is pp in any row and p3p^3 in total.

It remains to show that there are no four good fields with the prohibited property. Suppose on the contrary that
aicjbi+dj(modp)whenever i,j{1,2},(2) a_i c_j \equiv b_i + d_j \pmod{p} \quad \text{whenever } i, j \in \{1, 2\}, \qquad (2)
for some pairs (a1,b1)(a2,b2)(a_1, b_1) \neq (a_2, b_2) and (c1,d1)(c2,d2)(c_1, d_1) \neq (c_2, d_2). Subtracting (2) with a fixed ii yields
ai(c2c1)d2d1(modp)for i{1,2},(3) a_i(c_2 - c_1) \equiv d_2 - d_1 \pmod{p} \quad \text{for } i \in \{1, 2\}, \qquad (3)
which (in the same way) leads to
(a2a1)(c2c1)0(modp). (a_2 - a_1)(c_2 - c_1) \equiv 0 \pmod{p}.
Thus a1=a2a_1 = a_2 or c1=c2c_1 = c_2. In view of symmetry, we can assume that c1=c2c_1 = c_2. Then (3) implies that d1=d2d_1 = d_2, hence (c1,d1)=(c2,d2)(c_1, d_1) = (c_2, d_2), 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.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.