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

[avva]

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

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

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

Comments

[faceted-jacinth.livejournal.com]

Вот кстати интересно, я решил потыкаться в точную верхнюю грань и написал Программу, которая а) находит наилучший порядок объединения точек (для данных значений), б) псевдогенетическим алгоритмом (потому что градиентный спуск мне писать было в лом) ищет худшую комбинацию значений для данного количества точек.

Ну вот. Проверял на 6 (там это всё ещё не очень тормозит). Мы умеем доказывать, что можно получить 2**-3 разницы (т.е. 0.125). Из наивного примера для 22 точек (1, остальные нули) могло показаться, что на самом деле можно получить 2**-4 (0.0625). Ну, хотя бы это не так, есть милая комбинация [0, 0, 0, 0, 1/3, 1] (и симметричные), на которой нельзя получить меньше ~0.833.
Это типа локальный максимум. Как и [0, 0, 0, 0, 0, 1], кстати. Но глобальный ли - неизвестно.

Как вообще клёвые пацаны разглядывают рельефы шестимерных пространств?