[ Various cutting problems ]

Can a regular triangle be cut into 1000000 convex polygons such that any line intersects no more than 40 of them?

#
If cuts are made close to the vertices of a convex $n$-gon, then one can cut off $n$ triangles from it and obtain a convex $2n$-gon. It is easy to check that in this case, any line intersects no more than two of the cut-off triangles.

Cut off 3 triangles from an equilateral triangle, then 6 triangles from the resulting hexagon, and so on, until a $3 \cdot 2^{19}$-gon is obtained. Any line can intersect no more than two triangles cut off at each step. Therefore, a line can intersect no more than $1 + 2 \cdot 19 = 39$ polygons in total. The total number of polygons into which the equilateral triangle is divided is $1 + 3 + 3 \cdot 2 + \ldots + 3 \cdot 2^{18} = 1 + 3(2^{19} - 1) > 2^{20} = (2^{10})^2 > 1000^2$. It is clear that not all triangles need to be cut off to obtain exactly 1,000,000 polygons.

A square sheet of paper is cut into two parts by a straight line. One of the resulting parts is cut into two parts, and this is done several times. What is the minimum number of cuts needed to ensure that among the resulting parts there are 100 twenty-sided polygons?

## Solution

It is clear that after $n$ cuts, there will be $n+1$ pieces. Since the total number of vertices of the resulting figures increases by 2, 3, or 4 after each cut, the total number of vertices after $n$ cuts does not exceed $4n + 4$. If after $n$ cuts, there are 100 20-sided polygons, then besides these 20-sided polygons, there are still $n+1 - 100$ pieces, as the total number of pieces is $n+1$. Since each piece has at least three vertices, the total number of vertices is at least $100 \cdot 20 + (n - 99) \cdot 3 = 1703 + 3n$. Therefore, $1703 + 3n \leq 4n + 4$, i.e., $n \geq 1699$.

It remains to prove that 1699 cuts are sufficient to cut the square in the required manner. To cut the square into 100 rectangles, 99 cuts are sufficient, and to cut off 16 triangles from each of these rectangles and turn them into 20-sided polygons, 16000 cuts are sufficient.