olymmath

ISL 2006 C4

A cake has the form of an n×nn \times n square composed of n2n^{2} unit squares. Strawberries lie on some of the unit squares so that each row or column contains exactly one strawberry; call this arrangement A\mathcal{A}. Let B\mathcal{B} 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 B\mathcal{B} than of arrangement A\mathcal{A}. Prove that arrangement B\mathcal{B} can be obtained from A\mathcal{A} 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. (Taiwan)

Official text Transcription from NuminaMath olympiads, checked word for word against the official paper. Quoted with source.

Official text: IMO 2006 Shortlist booklet, page 26.

Solutions

Official solution Solution 1 by the IMO Problem Selection Committee

The terms of the source let olymmath link to this solution but not copy it. Read the solution (IMO official site).

Similar problems

These problems have the most words in common with this statement.

Locator isl/2006/c4 · Tag A1RNVGAHGR · Edit this page on GitHub · Keys: j next, k previous