Деревянную линейку, длина которой выражается целым числом сантиметров, разрезают на куски. За один ход можно взять один или несколько кусков линейки, положить их друг на друга и разрезать каждый из них на две части, длины которых выражаются целым числом сантиметров.
а) Можно ли за четыре хода разрезать линейку длиной 16 см на куски
длиной 1 см?
б) Можно ли за пять ходов разрезать линейку длиной 100 см на куски
длиной 1 см?
в) Какое наименьшее число ходов нужно сделать, чтобы разрезать линейку длиной 200 см на куски длиной 1 см?
Задание с развёрнутым ответом. Запишите решение и сравните его с разбором.
Ответ: а) да; б) нет; в) 8 ходов.
Решение
За один ход каждый выбранный кусок разрезают только на две части. Поэтому число кусков за ход может увеличиться не более чем вдвое. Если до хода было $P$ кусков, после него не больше $2P$. Начинаем с одного куска, значит, после $h$ ходов имеем не больше $2^h$ кусков. Это нижняя граница нужного количества ходов; затем отдельно нужно построить подходящие разрезы.
а) Линейку 16 см можно каждый раз делить пополам. После первого хода два куска по 8 см. Их складываем и разрезаем на половины — четыре куска по 4 см. Затем аналогично:
$$
1\text{ кусок по }16
\to2\text{ по }8
\to4\text{ по }4
\to8\text{ по }2
\to16\text{ по }1.
$$
Всего четыре хода; все длины целые. Ответ: да.
б) Чтобы получить из 100 см куски по 1 см, нужно ровно 100 кусков. После пяти ходов максимум:
$$
2^5=2\cdot2\cdot2\cdot2\cdot2=32<100.
$$
Поэтому ответ: нет.
в) Из 200 см нужно получить 200 единичных кусков. Сравним с последовательным удвоением:
$$
2^6=64,\qquad2^7=128,\qquad2^8=256;
\qquad128<200\le256.
$$
Семи ходов не хватит. Докажем, что восьми достаточно, причём разрезы можно делать одной прямой по стопке выбранных кусков.
Ход 1: разрезаем 200 см пополам, получаем два куска по 100 см.
Ход 2: складываем оба куска и режем на 50 и 50 см; получаем четыре куска по 50 см.
Ход 3: складываем четыре куска и режем пополам; получаем восемь кусков по 25 см.
Ход 4: складываем восемь кусков, совмещая их левые края, и режем на расстоянии 12 см от края. Каждый кусок 25 см разделится на 12 и 13 см. Получаем восемь кусков по 12 см и восемь по 13 см.
Ход 5: складываем все эти куски с общим левым краем и режем на расстоянии 6 см. Каждый 12-сантиметровый даёт два куска по 6, каждый 13-сантиметровый — по 6 и 7. Поэтому:
$$
8\cdot2+8=24\text{ куска по }6,\qquad8\text{ кусков по }7.
$$
Ход 6: режем стопку на расстоянии 3 см. Куски по 6 превращаются в два по 3; куски по 7 — в 3 и 4. Получаем:
$$
24\cdot2+8=56\text{ кусков по }3,\qquad8\text{ кусков по }4.
$$
Ход 7: режем эти куски на расстоянии 2 см. Каждый кусок 3 даёт 2 и 1, каждый кусок 4 — два куска по 2:
$$
56+8\cdot2=72\text{ куска по }2,\qquad56\text{ кусков по }1.
$$
Ход 8: единичные куски откладываем, а 72 куска по 2 см складываем и режем пополам. Новых единичных кусков $72\cdot2=144$, вместе с отложенными:
$$
144+56=200.
$$
Все восемь разрезов разрешены, у каждой части целая положительная длина. Следовательно, минимум — восемь ходов.
Ответ: а) да; б) нет; в) 8 ходов.