Convex pentagons in a triangle

1 Problem
2 Solution
1. 2.1 Result
3 Conclusion

In the 17 May 2010 Issue of the New Yorker there is an interesting article about Andrey Ternovskiy, the founder of Chatroulette. A particular math problem stood out to me:

How do you cut a square into convex pentagons? “Here’s how Andrey solved it,” Puchkov said, and sketched a square with two abutting pentagons in the center and lines radiating out cleanly to the perimeter. It was the simplest solution—and Ternovskiy had come to it far more quickly than Puchkov had.

I started thinking about related problems, generalizations. An easy modification is to swap out the square for a triangle.

1 Problem

What is the least number of convex pentagons that can fit in a triangle snugly without overlap or leftover space? That is, how do you cut a triangle minimally into convex pentagons?

Here, I will provide a sketch of a proof that the answer is 9. It is not rigorous, but is meant to give a rough idea.

2 Solution

First, we know there is an upper bound of 9.

Illustration of the upper bound — FIGURE 1 A picture of how you might cut a triangle into 9 convex pentagons.

Claim 1: Suppose a convex polygon with vertices can be cut into a minimum of convex pentagons. Then, a concave polygon with convex vertices cannot be cut into fewer than convex pentagons.

Explanation: For each concave vertex of , there must be a cut at that vertex. So, we can “straighten out” this concave vertex by moving it outwards along the cut until it has an angle of $180^\circ$ , in which case it is effectively no longer a vertex. This won’t affect the convexity of the pentagons inside , and we can thus remove all the concave vertices of to be left with a convex polygon of vertices cut into convex pentagons. If were cut into fewer than convex pentagons, it would contradict the premise.

Claim 2: Suppose a triangle is cut into the minimum number of convex pentagons. Then each of the triangle’s edges must touch more than one convex pentagon.

Explanation: If there is an edge that touches only one convex pentagon, then the remainder area in the triangle still has three convex vertices. By Claim 1, this cannot be cut into fewer convex pentagons than a triangle can be. So this cannot be the minimal solution.

Illustration of Claim 2 — FIGURE 2 A picture showing the leftover space in a triangle if the bottom edge touches only one convex pentagon.

Claim 3: Suppose a triangle is cut into the minimum number of convex pentagons. There is no need to cut a triangle at its corner, i.e. each corner only has to touch one pentagon.

Explanation: Let us consider two cases: Either we cut a triangle at its corner, or we don’t. In both cases, after accounting for one convex pentagon touching the corner, the remaining area has 4 convex vertices. But in the former case, it has more concave vertices, which we can again “straighten out” using the logic behind Claim 1. So, it isn’t any better than the latter case of letting each vertex of the triangle touch only one convex pentagon.

Illustration of Claim 3 — FIGURE 3 Cutting a triangle at its corner results in a remaining area with more concave vertices than otherwise.

At this point, you might note that you can fit Andrey Ternovskiy’s solution for cutting a square into 8 convex pentagons into the leftover area here, and immediately arrive at the answer of 9. But let us pretend we never saw the New Yorker article and proceed with the proof.

Claim 4: Suppose a convex quadrilateral is cut into the minimum number of convex pentagons. Then, it must have at least one edge that touches more than two convex pentagons.

Explanation: First we can rule out the case of a single convex pentagon touching an edge by the same logic as Claim 2. But if every edge touches two convex pentagons, then we are left with a remaining area that has 4 convex vertices — again, not optimal due to Claim 1.

Illustration of Claim 4 — FIGURE 4 A convex quadrilateral cut such that every edge touches two convex pentagons is not optimal because the remaining area has 4 convex vertices.

Claim 5: Suppose a triangle is cut into the minimum number of convex pentagons. Then, each edge must touch more than 2 convex pentagons.

Explanation: If there is an edge that touches only two convex pentagons, the remaining area has 4 convex vertices with at least 2 more concave vertices. But you can get essentially the same remaining area in Figure 3, but with one fewer convex pentagon used!

Illustration of Claim 5 — FIGURE 5 No matter how you let only two convex pentagons touch a single edge of the triangle, it cannot be optimal.

Actually, in the above picture, it might seem case C has a different remaining area than in Figure 3. But from Claim 4, we know a quadrilateral must have at least one edge that’s cut twice. So, the remaining areas in case C and in the right side of Figure 3 need the same number of convex pentagons after all.

2.1 Result

Proposition 1: A triangle can be cut into a minimum of 9 convex pentagons.

Explanation: From Claim 5, we know each edge of the triangle must touch at least 3 convex pentagons. This already uses up 6 convex pentagons. There is no way to cover up the remaining area, which has 3 concave vertices, using only 2 convex pentagons, so at least 3 more must be used. This gives us a lower bound of 9 which matches the upper bound of 9 earlier. $\blacksquare$

Illustration of Proposition 1 — FIGURE 6 The center area marked with a question mark cannot be cut into fewer than 3 convex pentagons.

3 Conclusion

It is interesting to note that we have pretty much also shown that it takes 8 convex pentagons to cover a convex quadrilateral (e.g. a square). Generalizing this to larger convex polygons is less interesting though…

Number of sides	Minimum number of convex pentagons
3	9
4	8
5	1
6	2
7	2
8	2
9	3
10	3

Table 1 Table of the minimum number of convex pentagons it is possible to cut an arbitrary convex polygon into.

And thereafter, for a convex polygon of sides, you can cut it into $\left\lceil \frac{n}{4} \right\rceil$ convex pentagons. This is because a convex pentagon can contribute at most 4 sides, the fifth being used for an internal edge (a cut).