Maths Olympiad Prep

Library / /13 of 36

Combinatorics Difficulty 5.7 AIME, harder Prove it Saudi Arabia

A large rectangle is subdivided into smaller rectangles, each of which has at least one pair of sides of integer length. Prove that the large rectangle also has at least one pair of sides of integer length.

Solution

Label the large rectangle by RR and place it in the plane so that its lower-left corner is at (0,0)(0, 0) with sides parallel to Ox,OyOx, Oy.
Let SS be the set of vertices of the small rectangles whose both coordinates are integers, and let TT be the set of all the small rectangles. We form a bipartite graph on the vertex set STS \cup T by joining each point in SS to every rectangle in TT of which it is a vertex. Observe that each small rectangle has either 0, 2, or 4 vertices in SS (because of integer length side), so it contributes an even number of edges. Hence the total number of edges in this bipartite graph is even. On the other hand, each point in SS that is not a corner of RR is a vertex of exactly 2 or 4 small rectangles, and so also has even degree.
Since (0,0)(0, 0) is in SS and is a corner of exactly one small rectangle, it has odd degree. Therefore there must be another vertex in SS of odd degree. The only vertices of odd degree can be corners of RR, so at least one other corner of RR lies in SS. In particular, either the width or the height of RR is an integer. \Box

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

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