Punch 2000 holes in 2000 polygons with 1000 needles

You have two identical perfectly square pieces of paper. The area of each paper is 1000 units.

On each paper, draw 1000 convex, non-overlapping polygons with all polygons having the same area (exactly 1 unit). Obviously, the polygons are covering both papers completely and edges of paper also serve as edges of some polygons). Polygons may have different shapes and number of sides and the drawing on the first paper is completely different from the drawing on the second paper.

Now put the first paper on top of the second and align paper edges perfectly. Prove that it is always possible to punch a hole in all 2000 polygons with 1000 needles (each needle goes through both papers).

What have I tried?

This problem came from my son who likes to torture his father with difficult problems brought back from his math school. My first try was to steal his clever analysis book while he was sleeping and find the right page in the answer section. Alas, this problem had no solution, which basically means that it's either too simple (and I'm too stupid) or it's too difficult.

So I decided to read some theory and discovered that I had some pretty huge gaps in my math education. This problem is definitely about functions. You have a set of 1000 polygons on one side and a set of 1000 polygons on the other side. I have to prove that there is a bijective function between these two sets. Needles are just lines connecting the dots. However, all my attempts to construct such function ended miserably. I guess there has to be some clever theorem than can be applied to problems like this one but I would have to read a pretty thick book to find it.

Thanks for the hint.

Solution 1:

The clever theorem that can be applied to questions like this one is Hall's theorem.

Construct a bipartite graph, with the vertices on one side being the polygons on the first sheet of paper, and the vertices on the other side being the polygons on the second sheet of paper. Draw an edge between two polygons whenever they overlap.

A perfect matching in this graph is a one-to-one pairing of the polygons on the two sheets such that any two polygons that are paired overlap somewhere. If we find a perfect matching, we can punch the holes: for every pair of polygons in the perfect matching, poke a needle through some part of their overlapping region.

Hall's theorem says that a perfect matching is guaranteed to exist if, for every set $S$ of vertices on one side, the set $N(S)$ of vertices adjacent to some vertex in $S$ satisfies $|N(S)| \ge |S|$. In other words, if you pick any $k$ polygons on one sheet of paper, there will be at least $k$ polygons on the other sheet of paper adjcent to at least one of the ones you picked.

This follows from looking at the areas. An individual polygon has area $1$. So the $k$ polygons you chose on one sheet have total area $k$. On the other sheet, that same region needs at least $k$ polygons to cover.

Solution 2:

It is "self evident" that we cannot use fewer than 1000 needles, just to punch a hole in every polygon in a single sheet.

By the pigeon hole principle, if we use more than 1000 needles, then some polygons must have more than one hole in them.

Suppose that punching 1000 holes in 1000 polygons in the upper sheet does not achieve perfect coverage in the lower sheet: not all 1000 polygons receive a hole. That requires that one or more polygons to receive two holes. (Our friend, pigeon hole, again).

Is that possible? Yes it is. For that to happen, all we need is the situation that two needles (necessarily) going through different polygons in the top sheet pierce the same polygon in the bottom sheet.

However, is this unavoidable? No, it isn't. Two needles going through different top polygons are never forced to map to the same bottom polygon. For such a situation to be unavoidable, it would have to be that some lower layer polygon entirely covers two (or more) upper layer polygons. This is ruled out by the key constraint that all polygons have the same area. Therefore the situation is avoidable; no pair of needles have to share the same lower-layer polygon.