ID: 00008997
Деревянную линейку, длина которой выражается целым числом сантиметров, разрезают на куски. За один ход можно взять один или несколько кусков линейки, положить их друг на друга и разрезать каждый из них на две части, длины которых выражаются целым числом сантиметров.
а) Можно ли за четыре хода разрезать линейку длиной $16$, $\text{см}$ на куски длиной $1$, $\text{см}$?
б) Можно ли за пять ходов разрезать линейку длиной $100$, $\text{см}$ на куски длиной $1$, $\text{см}$?
в) Какое наименьшее число ходов нужно сделать, чтобы разрезать линейку длиной $200$, $\text{см}$ на куски длиной $1$, $\text{см}$?
Источник: ФИПИ
Что происходит: за один ход берём один или несколько кусков, складываем стопкой и одним разрезом делим каждый на две части. Главное наблюдение: за ход каждый взятый кусок превращается в два, поэтому число кусков может увеличиться самое большее вдвое.
Отсюда простая оценка: в начале один кусок, и после $t$ ходов кусков не больше $2^{t}$.
Пункт а). Линейку $16$ см разрезать за $4$ хода на куски по $1$ см — это $16$ кусков. Так как $2^{4}=16$, надо каждый ход ровно удваивать, деля пополам: $16\to 8+8$; стопкой режем обе восьмёрки $\to$ четыре куска по $4$; $\to$ восемь по $2$; $\to$ шестнадцать по $1$. Уложились в $4$ хода. Значит — да.
Пункт б). Линейку $100$ см за $5$ ходов на $100$ кусков по $1$ см. Но за $5$ ходов кусков не больше $2^{5}=32$, а это меньше $100$. Значит — нет.
Пункт в). Линейку $200$ см надо разрезать на $200$ кусков по $1$ см. По оценке за $t$ ходов кусков не больше $2^{t}$. Так как $2^{7}=128\lt 200$, а $2^{8}=256\geqslant 200$, меньше $8$ ходов не хватит: $t\geqslant 8$.
Восьми ходов достаточно. Каждый ход будем складывать в стопку все куски длиннее $1$ см и разрезать каждый как можно ровнее пополам. Тогда длины кусков уменьшаются примерно вдвое за ход: после $8$ таких делений самый длинный кусок станет не длиннее $200/2^{8}\lt 1$, то есть все куски будут по $1$ см. В конце все куски единичные, а их суммарная длина $200$ — значит кусков ровно $200$. Наименьшее число ходов — 8.
а) да; б) нет; в) $8$.