задачка (математическое)

[avva]

Задачка от Ноги Алона (рассказал А., его студент):

Даны 22 точки в промежутке [0,1] (необязательно различные). Вы 20 раз повторяете следующую операцию: выбираете две из них и заменяете обе на точку, лежащую ровно посредине между ними. После 20 таких ходов остается всего две точки. Доказать: вы всегда сможете выбрать ходы так, чтобы между двумя оставшимися точками расстояние было не больше 1/1000.

Решения я не знаю. Комментарии скрывать не буду, и даже читать пока не буду, потому что хочу сам подумать.

Comments

[nadja-s.livejournal.com]

Кстати, и как l_n оценивать снизу, тоже не понимаю (то, что я написала, неправильно). Ведь если мы удаляем 2 соседние точки, которые на максимальном расстоянии (как вы предлагаете делать; ну, вернее, вы предлагаете на том, которое больше среднего, но для определенности возьмем максимальное тогда), то расстояние может лихо уменьшиться, а не на [l/(M-1)]. Например, если 4 точки: 0, 0.98, 0.99, 1, то мы удалим 0 и 0.98, останутся 0.99 и 1, и между ними совсем маленькое расстояние.