Library / Chinese Girls' Mathematical Olympiad /3 of 7

Chinese Girls' Mathematical Olympiad

Combinatorics Difficulty 5.9 AIME, harder Prove it China

As shown below, a square grid of side length $8$ is constructed by $144$ sticks of length $1$ . Find the least number of sticks to be removed so that the resulting figure contains no rectangle.

Solution

The answer is $43$ .

First, we prove that at least $43$ sticks must be removed. Suppose the figure does not contain any rectangles, then each bounded connected area must consist of at least three unit squares, i.e., the area is at least $3$ . Therefore, there can be at most $\lfloor \frac{64}{3} \rfloor = 21$ bounded connected areas. Removing one stick can at most reduce the number of bounded connected areas by $1$ (either by merging two bounded areas into one, or by merging a bounded area with an unbounded area). Initially, there are $64$ bounded connected areas, so at least $64 - 21 = 43$ sticks must be removed.

The figure below shows an example of removing $43$ sticks, where each bounded connected area has an area of $3$ , and the figure does not contain any rectangles.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.