Решение: Разрезание линейки на сантиметры
Деревянную линейку, длина которой выражается целым числом сантиметров, разрезают на куски. За один ход можно взять один или несколько кусков линейки, положить их друг на друга и разрезать каждый из них на две части, длины которых выражаются целым числом сантиметров. Исследуйте возможность разрезания линейки длиной 16 см за четыре хода и линейки длиной 100 см за пять ходов на куски длиной 1 см, а также найдите наименьшее число ходов для линейки длиной 200 см.
Решение по шагам
5 шаговЗа один ход каждый имеющийся кусок можно разделить не более чем на два куска. Поэтому после $k$ ходов из одной исходной линейки можно получить не более $2^k$ кусков.
$$N_k \leq 2^k$$Для линейки длиной 16 см четыре хода возможны: сначала получаем два куска по 8 см, затем четыре куска по 4 см, затем восемь кусков по 2 см и, наконец, шестнадцать кусков по 1 см.
$$16 \to 2\cdot 8 \to 4\cdot 4 \to 8\cdot 2 \to 16\cdot 1$$Для линейки длиной 100 см за пять ходов можно получить не более $2^5=32$ кусков, а требуется 100 кусков длиной 1 см. Следовательно, это невозможно.
Для линейки длиной 200 см семь ходов недостаточно, поскольку $2^7=128<200$. Значит, необходимо не менее восьми ходов.
Восьми ходов достаточно. Общее утверждение: любой кусок целой длины $n\leq 2^k$ можно разрезать за $k$ ходов на единичные куски. На первом ходу разделим его на куски длиной $\lfloor n/2\rfloor$ и $\lceil n/2\rceil$; каждая из этих длин не превосходит $2^{k-1}$. По индукции каждый из полученных кусков можно разделить на единичные за оставшиеся $k-1$ ходов. При $n=200$ и $k=8$ условие $200\leq 256$ выполнено.
а) Да, за 4 хода. б) Нет, за 5 ходов невозможно. в) Наименьшее число ходов — 8.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать, что за один ход можно получить только один новый кусок.
Не использовать ограничение $2^k$ на максимальное число кусков.
Для пункта в) доказать только необходимость восьми ходов, но не показать, что восьми ходов действительно достаточно.