IMO Shortlist 2006 problem C4
Kvaliteta:
Avg: 3,0Težina:
Avg: 7,0 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.
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n^{2}](/media/m/8/9/c/89ce8c999ff2fb1129c116f0f254932f.png)
![A](/media/m/5/a/e/5ae81275ee67d638485e903bdc0e9cde.png)
![B](/media/m/c/e/e/ceebc05be717fa6aab8e71b02fe3e4e3.png)
![B](/media/m/c/e/e/ceebc05be717fa6aab8e71b02fe3e4e3.png)
![A](/media/m/5/a/e/5ae81275ee67d638485e903bdc0e9cde.png)
Prove that arrangement
![B](/media/m/c/e/e/ceebc05be717fa6aab8e71b02fe3e4e3.png)
![A](/media/m/5/a/e/5ae81275ee67d638485e903bdc0e9cde.png)
Izvor: Međunarodna matematička olimpijada, shortlist 2006