Задача 35467

Темы:    [ Средние величины ] [ Процессы и операции ] [ Полуинварианты ] [ Индукция (прочее) ]

Сложность: 4- Классы: 8,9,10

Условие

Даны 10 чисел – одна единица и 9 нулей. Разрешается выбирать два числа и заменять каждое из них их средним арифметическим.
Какое наименьшее число может оказаться на месте единицы?

Решение

  Докажем индукцией по k следующее утверждение: если в некоторый момент среди чисел имеется ровно k отличных от нуля, то каждое из этих чисел не меньше 2^1–k.
  База. Для  k = 1  это верно, так как после первой же нетривиальной операции появятся по крайней мере два ненулевых числа, а в дальнейшем число ненулевых чисел не уменьшается.
  Шаг индукции. Пусть в некоторый момент имеется  k + 1  ненулевое число. Рассмотрим последовательность операций, в результате которой эти числа появились. В этой последовательности операций найдем последний момент, когда было ровно k ненулевых чисел. По предположению индукции каждое из этих чисел не меньше чем 2^1–k. При следующей операции один ноль и одно ненулевое число заменили на их среднее. После этого каждое из этих чисел стало не меньше чем 2^–k. В дальнейшем в результате операций только с ненулевыми числами минимум ненулевых чисел не увеличивается.

  Поскольку у нас всего 10 чисел, то каждое из них не меньше чем  2^–9 = ¹/₅₁₂.
  С другой стороны, нетрудно привести пример выполнения операций, при котором из единицы получается ¹/₅₁₂. Заменим единицу и один из нулей на ½ и ½, затем заменим ½ и другой ноль на ¼ и ¼ и т.д.; в конечном итоге получаем из единицы ¹/512.

Ответ

¹/₅₁₂.

Источники и прецеденты использования

web-сайт

задача