Одновременное разрезание линеек

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Ограничение числа частей
  2. Построение с общими разрезами

    Сначала: Ограничение числа частей

  3. Ответ: да

    Сначала: Построение с общими разрезами

  4. Ограничение числа частей

    Сначала: Ответ: да

  5. Ответ: нет

    Сначала: Ограничение числа частей

  6. Ограничение числа частей

    Сначала: Ответ: нет

  7. Построение с общими разрезами

    Сначала: Ограничение числа частей

  8. Ответ

    Сначала: Построение с общими разрезами

Разобранный пример

Деревянную линейку, длина которой выражается целым числом сантиметров, разрезают на куски. За один ход можно взять один или несколько кусков линейки, положить их друг на друга и разрезать каждый из них на две части, длины которых выражаются целым числом сантиметров.

а) Можно ли за четыре хода разрезать линейку длиной 16 см на куски длиной 1 см?

б) Можно ли за пять ходов разрезать линейку длиной 100 см на куски длиной 1 см?

в) Какое наименьшее число ходов нужно сделать, чтобы разрезать линейку длиной 200 см на куски длиной 1 см?

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Один ход разрезает каждый выбранный кусок максимум на два. Поэтому после tt ходов частей не больше 2t2^{t}. Для линейки длиной LL, разделяемой на единичные части, необходимо 2t≥L2^{t}\geq L.
n=4n=4
L=16L=16
Шаг 2. Выбираем степени двойки по убыванию, начиная с наибольшей, строго меньшей LL. На каждом ходе от всех кусков, которые длиннее выбранной степени двойки, отрезаем эту одинаковую целую длину. После этого каждый кусок не длиннее выбранной степени. На следующем ходе степень уменьшается вдвое, и каждый кусок снова требует не больше одного разреза. Последняя степень равна единице. Получаем ровно ⌈log⁡2L⌉\left\lceil \log_{2}L\right\rceil ходов и все единичные части.
Шаг 3. Да. Построенный пример удовлетворяет всем условиям.
Шаг 1. Один ход разрезает каждый выбранный кусок максимум на два. Поэтому после tt ходов частей не больше 2t2^{t}. Для линейки длиной LL, разделяемой на единичные части, необходимо 2t≥L2^{t}\geq L.
n=5n=5
L=100L=100
Шаг 2. Нет. Полученное необходимое ограничение исключает такую возможность.
Шаг 1. Один ход разрезает каждый выбранный кусок максимум на два. Поэтому после tt ходов частей не больше 2t2^{t}. Для линейки длиной LL, разделяемой на единичные части, необходимо 2t≥L2^{t}\geq L.
Шаг 2. Выбираем степени двойки по убыванию, начиная с наибольшей, строго меньшей LL. На каждом ходе от всех кусков, которые длиннее выбранной степени двойки, отрезаем эту одинаковую целую длину. После этого каждый кусок не длиннее выбранной степени. На следующем ходе степень уменьшается вдвое, и каждый кусок снова требует не больше одного разреза. Последняя степень равна единице. Получаем ровно ⌈log⁡2L⌉\left\lceil \log_{2}L\right\rceil ходов и все единичные части.
T=(128;64;32;16;8;4;2;1)\mathcal T=\left(128;64;32;16;8;4;2;1\right)
Шаг 3. Записываем вычисленное значение.
88

Открыть задачу целиком

Попробовать самостоятельно