We have a rectangular piece of paper. We want to produce 20-sided polygons using the following procedure. In each step, we select a piece of paper (initially, only the starting piece of paper is available), and cut it into two along a straight line. Continuing this process, what is the minimum number of cuts needed to obtain at least one hundred 20-sided polygons?
Solution. First, we cut the rectangle parallel to one of its sides into two rectangles. Then, we cut one of the resulting pieces similarly into two rectangles. We continue this process until we have 100 rectangles. Since each cut produces one additional rectangle, and we started with one rectangle, a total of 99 cuts are required.

If we cut off a corner of the rectangle in such a way that a triangle is formed, the remaining piece will be a pentagon. By cutting off new corners of this pentagon, the number of vertices increases by one each time. Thus, we can turn a quadrilateral into a 20-sided polygon with 16 cuts, meaning that to transform 100 quadrilaterals into 20-sided polygons, we need \(100 \cdot 16 = 1600\) cuts. Therefore, a total of \(99 + 1600 = 1699\) cuts are required to create 100 20-sided polygons.

Now, we will show that fewer than 1699 cuts are not sufficient. After a general cutting process that meets the conditions, let the number of cuts be \(v\), the total number of vertices of all resulting polygons be \(c\), and the number of polygons other than the 100 20-sided polygons be \(m\). Since each cut produces one new polygon, and we started with one rectangle, we have \(100 + m = v + 1\), or \(99 = v - m\). The 100 20-sided polygons have a total of \(20 \cdot 100 = 2000\) vertices, and each of the other polygons is at least a triangle, so they have at least \(3m\) vertices in total. Therefore, the total number of vertices of all polygons is \(c \geq 2000 + 3m\).

When a polygon is cut, new vertices are created. Where a cut passes through a vertex, the number of vertices increases by one; where it passes through an interior point of an edge, two new vertices are created. Since a cut intersects the perimeter of a polygon at two points, the number of vertices can increase by at most 4 with each cut.

Initially, the rectangle had 4 vertices. After \(v\) cuts, the number of vertices can increase by at most \(4v\), so \(c \leq 4 + 4v\).

From the above two inequalities: \(2000 + 3m \leq c \leq 4 + 4v\), or

\[
2000 + 3m \leq 4 + 4v, \quad \text{which implies} \quad 1996 \leq v + 3(v - m).
\]

Since \(v - m = 99\), we have \(1996 \leq v + 3 \cdot 99\), or \(1699 \leq v\). Therefore, at least 1699 cuts are required to produce 100 20-sided polygons.