Maths Olympiad Prep

Library / Estonian Math Competitions /25 of 148

Estonian Math Competitions

Combinatorics Difficulty 4.9 AIME Prove it Estonia

A rectangle of integral side lengths is divided into 20222022 unit squares. At least one unit square is coloured black. There are equally many black squares in every row and also equally many black squares in every column. Find all possibilities of how many black unit squares there can be in total.

Solution

Answer: 20222022.

Let the rectangle be of size a×ba \times b. Let there be kk black unit squares in every row and ll black unit squares in every column; then ak=blak = bl. Since ab=2022=2⋅3⋅337ab = 2022 = 2 \cdot 3 \cdot 337 where the factors are primes, numbers aa and bb must be coprime. Thus b∣kb \mid k, implying ak=abk′=2022k′ak = abk' = 2022k' for some integer k′k'. Since at least one black square exists and the total number of unit squares is 20222022, the only possibility is ak=2022ak = 2022, i.e., all unit squares are black.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.