Kvant Math Problem 31
Each cut is made on a single existing piece and splits it into two pieces.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m43s
Source on kvant.digital
Problem
A square sheet of paper is cut along a straight line into two pieces. One of the resulting pieces is then cut into two, and this process is repeated many times. What is the minimum number of cuts needed so that among the resulting pieces there are exactly one hundred 20-sided polygons?
I. N. Bernstein
Moscow Mathematical Olympiad (1970)
Exploration
Each cut is made on a single existing piece and splits it into two pieces. Thus after $n$ cuts there are exactly $n+1$ pieces.
The number of sides of a polygon changes in a simple way under a straight cut. Suppose a polygon has $m$ sides. The cutting line meets its boundary in two points. If these points lie on distinct sides, and if $r$ sides lie on one boundary arc between them while $m-r$ lie on the other, then the two new polygons have
$$r+2,\qquad (m-r)+2$$
sides. Their total number of sides is
$$(r+2)+((m-r)+2)=m+4.$$
Thus every cut increases the total number of sides of all pieces by $4$.
The initial square contributes $4$ sides. After $n$ cuts the total number of sides over all pieces equals
$$4+4n.$$
If there are one hundred $20$-gons, they already contribute
$$100\cdot20=2000$$
sides. Hence
$$4+4n\ge2000,$$
so
$$n\ge499.$$
This lower bound is very suggestive. Equality would mean that the total number of sides of all pieces is exactly $2000$, so every piece must be one of the hundred $20$-gons. Since $499$ cuts produce $500$ pieces, this is impossible. Thus at least $500$ cuts are needed.
Can $500$ cuts actually suffice? After $500$ cuts there are $501$ pieces. If one hundred of them are $20$-gons, the total number of sides is
$$4+4\cdot500=2004.$$
The remaining $401$ pieces must then contribute only
$$2004-2000=4$$
sides altogether. Since every polygon has at least $3$ sides, this is impossible. So the preceding counting is too crude because the pieces need not all be polygons in the ordinary sense? No, every piece obtained by cutting a polygon with a line is again a polygon, hence has at least $3$ sides. Therefore a stronger estimate is available.
Let $P$ be the total number of pieces. After $n$ cuts, $P=n+1$. Let $S$ be the total number of sides of all pieces. Then
$$S=4+4n=4P.$$
Hence the average number of sides per piece is always exactly $4$.
If there are $100$ twenty-gons and the remaining $P-100$ pieces have at least $3$ sides each, then
$$S\ge100\cdot20+3(P-100).$$
Using $S=4P$ gives
$$4P\ge2000+3P-300,$$
hence
$$P\ge1700.$$
Therefore
$$n=P-1\ge1699.$$
Now the question is whether this bound is attainable. Equality requires every non-twenty-gon to be a triangle. Then we need exactly $100$ twenty-gons and $1600$ triangles, since
$$100+1600=1700.$$
The crucial point is whether a $20$-gon can be created from a triangle by a sequence of cuts while producing only triangles as by-products.
Starting from a triangle, cut off a small triangle at a vertex. The small removed piece is a triangle, while the remaining piece gains one side. A triangle becomes a quadrilateral. Repeating this operation on the large piece increases its number of sides by $1$ each time and always creates another triangle. Thus a triangle can be transformed into a $20$-gon by $17$ cuts, producing $17$ triangles.
Beginning with the square, one cut along a diagonal yields two triangles. If one triangle is converted into a $20$-gon, we obtain one $20$-gon and $18$ triangles altogether. Repeating the same procedure on one of the triangles creates another $20$-gon and adds $17$ more triangles. Each new $20$-gon requires $18$ cuts and increases the number of triangles by $16$.
After producing $100$ twenty-gons, the count becomes exactly $100$ twenty-gons and
$$2+100\cdot16=1602$$
triangles? That gives too many. Let me compute carefully.
Initially, after the diagonal cut: $2$ triangles.
Transforming one triangle into a $20$-gon replaces one triangle by one $20$-gon plus $17$ triangles. Net gain: $+16$ triangles and $+1$ twenty-gon.
After $100$ such transformations, starting from $2$ triangles:
$$T=2+100\cdot16=1602.$$
Together with $100$ twenty-gons, that gives $1702$ pieces, corresponding to $1701$ cuts. The lower bound was $1699$, so we need a more efficient construction.
The discrepancy is $2$ triangles. Since the initial square can itself be turned into a $20$-gon by $16$ cuts, producing $16$ triangles. Net result from the square: one $20$-gon and $16$ triangles. Then each additional $20$-gon can be produced from one triangle at cost $17$ cuts and net gain $16$ triangles.
Starting with the square:
For the first $20$-gon: $16$ cuts, yielding $1$ twenty-gon and $16$ triangles.
For each of the remaining $99$ twenty-gons: choose a triangle and convert it, gaining one twenty-gon and $16$ triangles.
Then
$$T=16+99\cdot16=1600,$$
and
$$G=100.$$
Total pieces:
$$1600+100=1700,$$
exactly the lower-bound value. The number of cuts is
$$1700-1=1699.$$
So the lower bound is attained.
Problem Understanding
We repeatedly choose one existing polygonal piece and cut it by a straight line. After many such operations we want the collection of resulting pieces to contain exactly one hundred $20$-gons. We must determine the minimum possible number of cuts.
This is a Type C problem. We must find the minimum number of cuts, construct a configuration achieving it, and prove that no smaller number is possible.
The core difficulty is obtaining a sharp lower bound. The invariant is the total number of sides of all pieces. Every cut increases this total by exactly $4$, and comparing this with the requirement of having one hundred $20$-gons yields the optimal bound.
The answer is $1699$. Intuitively, the average number of sides per piece always remains $4$. Since a $20$-gon contributes far above this average, many other pieces must be triangles. The extremal configuration is exactly one hundred $20$-gons and sixteen hundred triangles.
Proof Architecture
The first lemma states that if a polygon with $m$ sides is cut by a straight line, the sum of the numbers of sides of the two resulting polygons is $m+4$. This follows from counting the sides on the two boundary arcs determined by the intersection points.
The second lemma states that after $n$ cuts, the total number of sides of all pieces equals $4+4n$. This follows by induction from the first lemma.
The third lemma states that after $n$ cuts there are $n+1$ pieces. Each cut increases the number of pieces by exactly one.
The fourth lemma states that if there are $100$ twenty-gons among the pieces, then the number of pieces is at least $1700$. This follows from comparing the total number of sides with the fact that every other polygon has at least three sides.
The construction lemma states that a polygon can gain one side while producing a triangle by cutting off a small triangle at a vertex. Repeating this operation converts a triangle into a $20$-gon while producing only triangles as additional pieces.
The hardest direction is proving optimality. The lemma most likely to fail under careless scrutiny is the side-counting inequality leading to the bound $1700$ pieces.
Solution
Let $S$ denote the sum of the numbers of sides of all pieces.
Suppose a polygon with $m$ sides is cut by a straight line. The cutting line meets the boundary in two points. These points divide the boundary into two arcs. If one arc contains $r$ sides of the original polygon, the other contains $m-r$ sides.
The two new polygons consist of these boundary arcs together with the two segments of the cutting line. Hence they have
$$r+2 \quad\text{and}\quad (m-r)+2$$
sides. Their total number of sides is
$$(r+2)+((m-r)+2)=m+4.$$
Thus every cut increases $S$ by $4$.
Initially there is one square, so $S=4$. After $n$ cuts,
$$S=4+4n.$$
Also, each cut replaces one piece by two pieces, so after $n$ cuts there are
$$P=n+1$$
pieces. Eliminating $n$ gives
$$S=4P.$$
Assume that among the pieces there are exactly one hundred $20$-gons. Every remaining piece is a polygon and therefore has at least $3$ sides. Consequently,
$$S\ge100\cdot20+3(P-100).$$
Using $S=4P$,
$$4P\ge2000+3P-300,$$
which simplifies to
$$P\ge1700.$$
Therefore
$$n=P-1\ge1699.$$
This proves that at least $1699$ cuts are necessary.
It remains to construct a process using exactly $1699$ cuts.
Consider a polygon and one of its vertices. Cut off a sufficiently small triangle at that vertex. The removed piece is a triangle. The remaining piece acquires one additional side, since the vertex is replaced by a new side joining two points on the adjacent edges.
Starting from the square, perform this operation repeatedly on the large remaining piece. Each cut increases its number of sides by $1$ and produces one triangle.
After $16$ cuts the original square has become a $20$-gon, and $16$ triangles have been produced.
Now take one of these triangles. Applying the same operation $17$ times converts that triangle into a $20$-gon and produces $17$ new triangles. Thus one triangle is replaced by one $20$-gon and $17$ triangles, a net increase of $16$ triangles.
Repeat this procedure on triangles until there are one hundred $20$-gons in total.
The first $20$-gon came from the square. The remaining $99$ twenty-gons are obtained from triangles. Hence the final numbers are
$$100$$
twenty-gons and
$$16+99\cdot16=1600$$
triangles.
The total number of pieces is
$$100+1600=1700.$$
Hence the number of cuts is
$$1700-1=1699.$$
Since $1699$ cuts are both necessary and sufficient, the minimum number of cuts is
$$\boxed{1699}.$$
Equality is attained in the construction described above.
Verification of Key Steps
The first delicate point is the claim that every cut increases the total number of sides by exactly $4$. Let the original polygon have $m$ sides. If the boundary arcs between the intersection points contain $r$ and $m-r$ sides, the new polygons have $r+2$ and $m-r+2$ sides. The increase is
$$(r+2)+(m-r+2)-m=4.$$
No geometric position of the cut changes this count.
The second delicate point is the inequality
$$S\ge100\cdot20+3(P-100).$$
A careless argument might forget that every remaining piece is still a polygon. Since a polygon has at least three sides, the contribution of the non-twenty-gons is at least $3(P-100)$. Equality occurs only when every remaining piece is a triangle.
The third delicate point is the construction. Cutting off a small triangle from a $k$-gon yields a triangle and a $(k+1)$-gon. For example, a triangle becomes a quadrilateral, a quadrilateral becomes a pentagon, and a pentagon becomes a hexagon. After $17$ such cuts, a triangle becomes a $20$-gon because
$$3+17=20.$$
The by-products remain triangles throughout, which is exactly what is needed for equality in the lower bound.
Alternative Approaches
Instead of tracking the total number of sides directly, one may define the excess
$$E=\sum (\text{number of sides}-4)$$
over all pieces. A cut changes a polygon with $m$ sides into two polygons whose side counts sum to $m+4$, so $E$ is invariant. Since the initial square has excess $0$, the total excess always remains $0$.
Each $20$-gon contributes $16$ to the excess, while every triangle contributes $-1$. Thus one hundred $20$-gons require at least sixteen hundred triangles to balance the excess. This immediately yields at least $1700$ pieces and therefore at least $1699$ cuts. The construction described above realizes exactly one hundred $20$-gons and sixteen hundred triangles, showing that the bound is sharp.
The invariant $E$ is essentially equivalent to the side-sum method, but it packages the extremal argument more compactly. The main proof was preferred because it derives the invariant directly from the geometry of a single cut and makes the equality case completely transparent.