Problem 818

Answer: It is possible to obtain exactly 100 20-sided polygons with 1699 cuts, and it is impossible to obtain 100 20-sided polygons with fewer cuts. With each cut, the total number of paper pieces increases by 1 (since one piece is cut into two new pieces), so after $n$ cuts, there will be ($n+1$) pieces of paper. Now let's calculate the maximum possible total number of vertices in all pieces after $n$ cuts. With each cut, the total number of vertices increases by either 2 (if the cut goes through two vertices), 3 (if the cut goes through a vertex and a side), or 4 (if the cut goes through two sides). Since there were initially 4 vertices, after $n$ cuts, the total number of vertices in all pieces together will not exceed $4n+4$. Suppose that after $N$ cuts, 100 20-sided polygons are obtained. Since the total number of pieces after these cuts will be $N+1$, there will be $N+1-100$ additional pieces besides these 20-sided polygons. Each of these additional pieces will have at least three vertices, so the total number of vertices in all pieces will be at least $100 \cdot 20 + (N-99) \cdot 3$. As proven earlier, this number does not exceed $4N+4$. Therefore, $4N+4 \geq 100 \cdot 20 + (N-99) \cdot 3 = 3N + 1703$, from which it follows that $N \geq 1699$. Thus, we have proven that it is impossible to obtain 100 20-sided polygons with fewer than 1699 cuts. This is the main and most difficult part of the proof.

Now let's show how 100 20-sided polygons can be obtained with 1699 cuts. Here is one way: cut the square into 100 rectangles (99 cuts) and convert each rectangle into a 20-sided polygon by making 16 cuts to remove triangles from the corners (1600 cuts). In total, there will be 1699 cuts.

## Answer

It is possible to obtain exactly 100 20-sided polygons with 1699 cuts, and it is impossible to obtain 100 20-sided polygons with fewer cuts.