ID: 00022406
Источник: ФИПИ
Разберёмся, как быстро растёт число кусков. За один ход мы берём несколько кусков, складываем стопкой и каждый разрезаем надвое. Если взяли $m$ кусков, то из них получилось $2m$ — то есть число кусков выросло на $m$. Но взять можно не больше, чем есть сейчас, поэтому за один ход количество кусков в лучшем случае удваивается. Значит после $n$ ходов кусков не больше $2^n$ — это главное ограничение.
а) Линейку 16 см надо разрезать на 16 кусков по 1 см. $2^4=16$ — как раз хватает, если каждый ход удваивать: $16\to$ два по 8 $\to$ четыре по 4 $\to$ восемь по 2 $\to$ шестнадцать по 1. Ровно 4 хода. Значит да, можно.
б) Линейку 100 см надо разрезать на 100 кусков по 1 см. За 5 ходов кусков не больше $2^5=32$, а нужно 100 — не хватает. Значит за пять ходов нельзя.
в) Нужно получить 300 кусков по 1 см. За $n$ ходов кусков не больше $2^n$, поэтому нужно $2^n\ge 300$. Поскольку $2^8=256<300$, а $2^9=512\ge 300$, меньше 9 ходов не хватит. А 9 ходов хватает: на каждом ходу разрежем каждый кусок длиннее 1 см примерно пополам, и самый длинный кусок будет уменьшаться так: $300\to150\to75\to38\to19\to10\to5\to3\to2\to1$ — ровно 9 шагов до кусков в 1 см. Значит наименьшее число ходов равно 9.