Ответ:максимальную "сложность" имеет число ((2⁵¹+ 1)/3)/2⁵⁰. Докажем, что среди чисел видаm/2^k, гдеm= 1, 3, 5,..., 2^k− 1, максимальную "сложность" (равную 2k) имеет число, у которогоm=m₀(k) = (2^{k + 1}+ (−1)^k)/3. Мы будем доказывать это утверждение индукцией поk. База индукции.k= 1. Очевидно, "сложность" числа 1/2 равна двум. Шаг индукции.Допустим, что наше утверждение доказано дляk. Докажем его дляk+ 1. Заметим сначала, что сложность любого числа видаm/2^{k + 1}не превосходит 2(k+ 1). Действительно, еслиm< 2^k, то это число может быть получено делением пополам числаm/2^k(всего не более 2k+ 1 < 2(k+ 1) операций), а еслиm> 2^k, то это число может быть получено следующим образом: сначала получим число (2^k+1 − m)/2^k, затем разделим его пополам, затем вычтем из единицы (всего не более 2k+ 1 + 1 = 2(k+ 1) операций). Докажем теперь, что "сложность" числаm₀(k+ 1)/2^{(k + 1)}равна 2k+ 2. Действительно, так какm₀(k+ 1)/2^{(k + 1)}> 1/2, то последняя операция при получении этого числа — вычитание из единицы, а предпоследняя — деление пополам. Но такой последовательностью операций оно получается именно из числаm₀(k)/2^k. Следовательно, "сложность" числаm₀(k+ 1)/2^{k + 1}на два больше "сложности" числаm₀(k)/2^k, т. е. равна 2k+ 2, ч. т. д.

Ответ задачи отсутствует