Competition problem — Combinatorics

Library / /41 of 45

Combinatorics Difficulty 6.7 National olympiad Prove it Romania

Each of the small squares of a $50 \times 50$ table is coloured in red or blue. Initially all squares are red. A step means changing the colour of all squares on a row or on a column.

a) Prove that there exists no sequence of steps, such that at the end there are exactly $2011$ blue squares.

b) Describe a sequence of steps, such that at the end exactly $2010$ squares are blue.

Solution

Without loss of generality, we may consider that the rows or columns to be modified in a sequence of steps are consecutive, and that each column or row is modified only once.

Suppose then that the first $x$ rows and the first $50-y$ columns have been modified. One gets a $x \times y$ rectangle and a $(50-x) \times (50-y)$ rectangle with all squares coloured blue, the rest of the table being red.

The number of blue squares is then $A = xy + (50-x)(50-y)$ which is an even number, so it can not equal $2011$ .

For the second part, notice that $A = 2010$ is equivalent to $(x - 25)(y - 25) = 380 = 19 \cdot 20$ .

One can take $x = 25 + 19 = 44$ and $y = 25 + 20 = 45$ to give the answer (thus being clear that the steps are not unique).

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.