Two Rectangles

Problem:

Two identical rectangles have been independently subdivided, each into N polygons of the same area. The two rectangles are then placed one on top of the other. Is it always possible to pierce them by N pins, so that each of the 2N polygons in the two subdivisions gets pierced exactly once? (No pin should hit the boundary of any of the polygons.)

Solution

Yes, this is always possible. Let P and Q denote the sets of polygons in the subdivisions of the two rectangles. Construct a bipartite graph G as follows. The set of vertices of G is P U Q. Draw an edge between a vertex p ϵ P and a vertex q ϵ Q if there exists a pin that pierces both polygons p and q in their interiors.

Consider an arbitrary subset X of P. Since all 2N polygons involved in the subdivisions have equal areas, there exist at least |X| polygons in Q that can be pierced by a pin through a polygon in X. For the graph G, this means that the set
{y ϵ Q | there exists an edge between y and a vertex in X} has size at least |X|.

This is exactly the condition in Hall’s Marriage Theorem, which guarantees a perfect matching in the graph G, i.e., a bijection σ : P → Q such that p and σ(p) are connected by an edge, for every p ϵ P.