Maths Olympiad Prep

Library / /110 of 196

Combinatorics Difficulty 5.3 AIME, harder Prove it Soviet Union

Problem:

Can the squares of a 1990×19901990 \times 1990 chessboard be colored black or white so that half the squares in each row and column are black and cells symmetric with respect to the center are of opposite color?

Solution

Solution:

Answer no

Figure 1
Suppose it can be done. Divide the board into 4 quadrants. Suppose there are bb black and 9952b995^2 - b white squares in the top left quadrant. Then there are 9952b995^2 - b black and bb white squares in the bottom right quadrant (by the symmetry property).

If half the squares in each row are black, then half the squares in the first 995995 rows are black, so the number of black squares in the top right quadrant is 9951990/2b=9952b995 \cdot 1990 / 2 - b = 995^2 - b. So if half the squares in each column are black, then half the squares in the right-hand half of the board are black, so (9952b)+(9952b)=9952(995^2 - b) + (995^2 - b) = 995^2, in other words, b=9952/2b = 995^2 / 2, which is impossible.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.