Задача М31‍‍

При каждом разрезании общее число кусков бумаги увеличивается на 1 (так как один кусок пропадает и появляются два новых), поэтому после $n$‍‍ разрезов будет $n+1$‍‍ кусков бумаги.

Подсчитаем теперь, каким может быть общее число вершин во всех кусках вместе после $n$‍‍ разрезов. При каждом разрезании общее число вершин увеличивается либо на 2 (если резали через две вершины), либо на 3 (если резали через вершину и сторону), либо на 4 (если резали через 2 стороны). Так как сначала было 4 вершины, то после $n$‍‍ разрезов во всех кусках вместе будет не больше чем $4n+4$‍‍ вершин.

Предположим, что после $N$‍‍ разрезов получилось 100 двадцатиугольников. Так как при этом общее число полученных кусков будет $N+1$‍,‍ то, кроме этих двадцатиугольников, будет ещё $N+1-100$‍‍ кусков. Каждый из этих кусков будет иметь не меньше трёх вершин, поэтому общее число вершин во всех кусках будет не меньше чем $100\cdot20+(N-99)\cdot3$‍.‍ Как было доказано раньше, это число не больше чем $4N+4$‍.‍ Значит, $$ 4N+4\ge100\cdot20+(N-99)\cdot3=3N+1703, $$ откуда $N\ge1699$‍.‍

Итак, мы доказали, что нельзя получить 100 двадцатиугольников, сделав меньше чем 1699 разрезов. Это основная и самая трудная часть доказательства.

Покажем теперь, как можно получить 100 двадцатиугольников, сделав 1699 разрезов. Вот один из способов: разрежем квадрат на 100 прямоугольников (99 разрезов) и каждый прямоугольник за 16 разрезов превратим в двадцатиугольник, отрезая от углов треугольники (1600 разрезов). Всего будет 1699 разрезов.

Ответ. Можно получить ровно 100 двадцатиугольников, сделав 1699 разрезов, а сделав меньшее число разрезов, 100 двадцатиугольников получить нельзя.

Точно так же можно узнать, какое наименьшее число разрезов нужно сделать, чтобы получить ровно $k$‍‍ $l$‍‍-угольников.

Точное решение этой задачи прислали Д. Григорьев из Ленинграда и В. Лившиц из Запорожья.