Задание 19 ЕГЭ профиль: Наименьшее число ходов

19.37.1.1.2 Числа и их свойства › Разрезание и переливание

Егор делит линейку на части. За одно действие он может отрезать от любого количества линеек равные части, имеющие целую длину.

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

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

в) За какое наименьшее количество ходов Егор может разделить линейку длиной в 300 см на части по 1 см?

Источник: ЕГЭ 2023, досрочная волна, Дальний Восток
Ответ и решение
  1. За один ход от каждой линейки отрезается не больше одной части, поэтому каждая линейка превращается не больше чем в две, и число линеек за ход увеличивается не больше чем вдвое. После kk ходов линеек не больше 2k2^k.

    Авторский приём: в учебниках перечня этот шаг полностью не изложен.

а) Линейка 1616 см за 44 хода

  1. Да: каждым ходом отрезаем половину от всех линеек: 1616 \to 88 \to 44 \to 22 \to 11 см; после 44 ходов получится 24=162^{4}=16 частей по 11 см.

Ответ а): да\text{да}

б) Линейка 100100 см за 55 ходов

  1. Нет: после 55 ходов частей не больше 25=32<1002^{5}=32<100, а нужно 100100 частей.

Ответ б): нет\text{нет}

в) Наименьшее число ходов для 300 см

  1. Нужно 300300 частей, а 28=256<3002^8=256<300, поэтому ходов не меньше 99.

  2. Девяти ходов хватает: каждый раз отрезаем от всех линеек, длиннее отрезаемой части, по части длиной в половину наибольшей (с округлением вниз). Длины частей (и их количество):

    отрезаем 150: 150×2отрезаем 75: 75×4отрезаем 37: 38×4, 37×4отрезаем 19: 19×12, 18×4отрезаем 9: 10×12, 9×20отрезаем 5: 5×44, 4×20отрезаем 2: 3×44, 2×84отрезаем 1: 2×44, 1×212отрезаем 1: 1×300\begin{gathered}\text{отрезаем }150:\ 150\times 2\\\text{отрезаем }75:\ 75\times 4\\\text{отрезаем }37:\ 38\times 4,\ 37\times 4\\\text{отрезаем }19:\ 19\times 12,\ 18\times 4\\\text{отрезаем }9:\ 10\times 12,\ 9\times 20\\\text{отрезаем }5:\ 5\times 44,\ 4\times 20\\\text{отрезаем }2:\ 3\times 44,\ 2\times 84\\\text{отрезаем }1:\ 2\times 44,\ 1\times 212\\\text{отрезаем }1:\ 1\times 300\end{gathered}

Ответ в): 99

Ответ: а) да; б) нет; в) 9\text{а) }\text{да};\ \text{б) }\text{нет};\ \text{в) }9