Деревянную линейку, длина которой выражается целым числом сантиметров, разрезают на куски. За один ход можно взять один или несколько кусков линейки, положить их друг на друга и разрезать каждый из них на две части, длины которых выражаются целым числом сантиметров.
а) Можно ли за четыре хода разрезать линейку длиной 16 см на куски длиной 1 см?
б) Можно ли за пять ходов разрезать линейку длиной 100 см на куски длиной 1 см?
в) Какое наименьшее число ходов нужно сделать, чтобы разрезать линейку длиной 200 см на куски длиной 1 см?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Один ход разрезает каждый выбранный кусок максимум на два. Поэтому после t ходов частей не больше 2t. Для линейки длиной L, разделяемой на единичные части, необходимо 2t≥L.
n=4
L=16
Шаг 2. Выбираем степени двойки по убыванию, начиная с наибольшей, строго меньшей L. На каждом ходе от всех кусков, которые длиннее выбранной степени двойки, отрезаем эту одинаковую целую длину. После этого каждый кусок не длиннее выбранной степени. На следующем ходе степень уменьшается вдвое, и каждый кусок снова требует не больше одного разреза. Последняя степень равна единице. Получаем ровно ⌈log2L⌉ ходов и все единичные части.
Шаг 3. Да. Построенный пример удовлетворяет всем условиям.
Шаг 1. Один ход разрезает каждый выбранный кусок максимум на два. Поэтому после t ходов частей не больше 2t. Для линейки длиной L, разделяемой на единичные части, необходимо 2t≥L.
n=5
L=100
Шаг 2. Нет. Полученное необходимое ограничение исключает такую возможность.
Шаг 1. Один ход разрезает каждый выбранный кусок максимум на два. Поэтому после t ходов частей не больше 2t. Для линейки длиной L, разделяемой на единичные части, необходимо 2t≥L.
Шаг 2. Выбираем степени двойки по убыванию, начиная с наибольшей, строго меньшей L. На каждом ходе от всех кусков, которые длиннее выбранной степени двойки, отрезаем эту одинаковую целую длину. После этого каждый кусок не длиннее выбранной степени. На следующем ходе степень уменьшается вдвое, и каждый кусок снова требует не больше одного разреза. Последняя степень равна единице. Получаем ровно ⌈log2L⌉ ходов и все единичные части.