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

[avva]

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

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

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

Comments

[pussbigeyes.livejournal.com]

По-моему, процесс должен сходиться к среднему арифметическому - центру масс системы точек. Поскольку каждая операция не меняет его местоположения.

[ro-che.livejournal.com]

Меняет. Поскольку масса теряется.

[pussbigeyes.livejournal.com]

Масса новой точки равна сумме масс точек, ее образовавших.

[ro-che.livejournal.com]

Вот-вот. Здесь это не выполняется (подумайте, почему).

[pussbigeyes.livejournal.com]

Лучше Вы объясните.

[mm-aa.livejournal.com]

(3 + 5 + 7) / 3 = 5
((3 + 5) / 2 + 7) / 2 = 5,5

[pussbigeyes.livejournal.com]

Не так в лоб. Количество точек считаем неизменным. http://avva.livejournal.com/2024677.html?thread=58008805#t58008805

[ro-che.livejournal.com]

Точки всегда заменяются на среднее арифметическое.
Если бы массы учитывались, работало бы правило рычага.

[pussbigeyes.livejournal.com]

Не понимаю. Вместо двух точек с единичным весом и координатами x_1 и x_2 возникают две точки с единичным весом с координатой (x_1+x_2)/2.

[ro-che.livejournal.com]

Возникает одна. Прочтите условие.

[pussbigeyes.livejournal.com]

Понял, согласен.