Maths Olympiad Prep

Track / Stage 5 / 382 of 400 #982 of 1964

Problem 982

AIME late
Combinatorics Difficulty 6.0 Prove it

XLIX OM - III - Problem 6

We consider unit squares on the plane, whose vertices have both integer coordinates. Let S S be a chessboard whose fields are all unit squares contained in the circle defined by the inequality x2+y219982 x^2+y^2 \leq 1998^2 . On all the fields of the chessboard, we write the number +1 +1 . We perform a sequence of operations, each of which consists of selecting any horizontal, vertical, or diagonal row and changing the signs of all numbers written on the fields of the selected row. (A diagonal row consists of all the fields of the chessboard S S whose centers lie on a certain line intersecting the coordinate axes at an angle of 45 45^\circ .)
Determine whether it is possible to achieve a situation where one field has the number 1 -1 written on it, and all the others have +1 +1 written on them.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Answer: It is not possible.
Suppose it is possible to obtain a configuration with exactly one field P1 P_1 , on which the number 1 -1 is written. Due to the standard symmetries of the chessboard S S , we can assume that the field P1 P_1 has its center at (a12,b12) (a-\frac{1}{2},b-\frac{1}{2}) , where ab1 a \geq b \geq 1 (a a , b b - integers). The point (a a , b b ) is a vertex of the field P1 P_1 , so a2+b2<19982 a^2 + b^2 < 1998^2 .
We will show that the unit square P2 P_2 with center (a32,b+12) (a-\frac{3}{2},b+\frac{1}{2}) is also a field of the chessboard S S .
If a>b a > b , then (a1)2+(b+1)2a2+b219982 (a-1)^2 + (b+1)^2 \leq a^2 + b^2 \leq 1998^2 . If, however, a=b a = b , then the inequality a2+b2=2a219982 a^2 + b^2 = 2a^2 \leq 1998^2 is definitely not an equality; hence,

Therefore, the point (a1,b+1) (a-1,b+1) , which is the top right vertex of the square P2 P_2 , lies within the circle mentioned in the problem. Consequently, the entire square P2 P_2 is contained within this circle, meaning it is a field of the chessboard S S .
om49_3r_img_2.jpg
Now consider eight unit squares, two of which are the fields P1 P_1 and P2 P_2 , arranged as shown in the adjacent figure. Since the squares P1 P_1 and P2 P_2 are fields of the chessboard S S , the remaining six squares are also fields.
Notice that each vertical, horizontal, or diagonal row either contains exactly two of the eight given fields or none of them. The product of the numbers written on these eight fields does not change as a result of the operations performed and remains constantly equal to 1 1 . It is therefore not possible for the number 1 -1 to appear on the field P1 P_1 at some point, while the others have +1 +1 .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.