Maths Olympiad Prep

Library / /12 of 86

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=23337ab = 2022 = 2 \cdot 3 \cdot 337 where the factors are primes, numbers aa and bb must be coprime. Thus bkb \mid k, implying ak=abk=2022kak = abk' = 2022k' for some integer kk'. 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,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.