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

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

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

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

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

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

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

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

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

  1. Да: каждым ходом отрезаем половину от всех линеек: 3232 \to 1616 \to 88 \to 44 \to 22 \to 11 см; после 55 ходов получится 25=322^{5}=32 части по 11 см.

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

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

  1. Нет: после 44 ходов частей не больше 24=16<502^{4}=16<50, а нужно 5050 частей.

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

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

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

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

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

Ответ в): 99

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