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

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

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

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

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

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

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

  2. Если же каждым ходом разрезать пополам все куски длиннее 11 см (кусок длины ll на [l2]\left[\frac l2\right] и l−[l2]l-\left[\frac l2\right]), то наибольшая длина LL превращается в L−[L2]L-\left[\frac L2\right], то есть в половину, округлённую вверх.

а) 1616 см за 44 хода

  1. Да: 16→8→…16\to8\to\ldots каждым ходом режем все куски пополам; 24=162^{4}=16.

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

б) 100100 см за 55 ходов

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

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

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

  1. Нужно 200200 кусков, а после 77 ходов их не больше 27=128<2002^{7}=128<200, поэтому ходов не меньше 88. За 88 ходов можно: наибольшая длина меняется так: 200→100→50→25→13→7→4→2→1200\to 100\to 50\to 25\to 13\to 7\to 4\to 2\to 1.

Ответ в): 88

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