IMO Shortlist 2006 problem C4
Avg:
Avg:
A cake has the form of an
x
square composed of
unit squares. Strawberries lie on some of the unit squares so that each row or column contains exactly one strawberry; call this arrangement
. Let
be another such arrangement. Suppose that every grid rectangle with one vertex at the top left corner of the cake contains no fewer strawberries of arrangement
than of arrangement
.
Prove that arrangement
can be obtained from
by performing a number of switches, defined as follows: A switch consists in selecting a grid rectangle with only two strawberries, situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle.







Prove that arrangement


Izvor: Međunarodna matematička olimpijada, shortlist 2006