IMO 2021 Shortlist C7
Consider a checkered 3m ˆ3m square, where m is an integer greater than 1. A frog sits on the lower left corner cell S an...
Category: Combinatorics
Problem
Consider a checkered 3m ˆ3m square, where m is an integer greater than 1. A frog sits on the lower left corner cell S and wants to get to the upper right corner cell F. 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 X of cells is called blocking if the frog cannot reach F from S when all the cells of X 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 ´3m cells. (b) Prove that every minimal blocking set contains at most 3m2 cells. Note.An example of a minimal blocking set for m “2 is shown below. Cells of the set X are marked by letters x. S F x x x x x x