Romanian Mathematical Olympiad

Question

Each of the small squares of a 50 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.

Accepted Answer

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 = x y + (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).