olymmath

ISL 2021 C7

Consider a checkered 3m×3m3 m \times 3 m square, where mm is an integer greater than 1 . A frog sits on the lower left corner cell SS and wants to get to the upper right corner cell FF. The frog can hop from any cell to either the next cell to the right or the next cell upwards. Some cells can be sticky, and the frog gets trapped once it hops on such a cell. A set XX of cells is called blocking if the frog cannot reach FF from SS when all the cells of XX are sticky. A blocking set is minimal if it does not contain a smaller blocking set. (a) Prove that there exists a minimal blocking set containing at least 3m2−3m3 m^{2}-3 m cells. (b) Prove that every minimal blocking set contains at most 3m23 m^{2} cells. Note. An example of a minimal blocking set for m=2m=2 is shown below. Cells of the set XX are marked by letters xx.

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

Official text: IMO 2021 Shortlist booklet, page 7.

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/2021/c7 · Tag X31HHR8SWJ · Edit this page on GitHub · Keys: j next, k previous