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

[avva]

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

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

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

Comments

[white-lee.livejournal.com]

От Левой или от Правой? :)

[avva.livejournal.com]

Почему? Не вижу очевидности. Вы не можете избавиться от всех остальных точек, кроме двух совпадающих - только от всех остальных, кроме одной, а потом придется "разменять".

(я все еще не читаю комментарии, и вообще это не я ;))

[esperador.livejournal.com]

Выбираем всегда крайние. А доказательство... сразу не готов дать.

[white-lee.livejournal.com]

Да, я вообще такой.

[avva.livejournal.com]

:)

[renatm.livejournal.com]

Готов дать контрпример :)

[esperador.livejournal.com]

Давай :)

[renatm.livejournal.com]

Но только программно-сгенерированный:
0.0126651814325
0.0259102145451
0.0383922849208
0.0749229407636
0.0934171575060
0.0989715262307
0.1243934446242
0.1387066255684
0.1645558030946
0.1837519455550
0.1895504623554
0.3204443494980
0.4076357310709
0.4746238593707
0.5454878383740
0.5549790948210
0.7159031952879
0.8455153050325
0.8976104007080
0.9229407635731
0.9808648945585
0.9960631122776
Ответ получается 0.0055848872341

[egle.livejournal.com]

Ой, да, я тоже зависла на этой "ноге" ;)

[esperador.livejournal.com]

Сорри, был не прав.
Интуиция подвела. :)

[esperador.livejournal.com]

Да, уже понял. :)

[esperador.livejournal.com]

А вот интересно, с этим примером вообще возможно выполнить условие?

[migmit.vox.com (from livejournal.com)]

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

[pigmeich.livejournal.com]

Что-то мне подсказывает что надо всунуть принцип Дирихле на множестве всех точек, что мы можем получить данными преобразованиями.

Делать не буду, ибо лень.

[dalvadorez.livejournal.com]

можно, мне кажется..
Досокращаться до 2 точек там и сям (две в нуле, две в 1), а потом взять их попарно - получим две последние точки в 0.5, с нулевым расстоянием.

[pussbigeyes.livejournal.com]

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

[ro-che.livejournal.com]

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

[nadja-s.livejournal.com]

Разве они не в одну слипнутся на 20-м шаге?

[pussbigeyes.livejournal.com]

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

[avzel.livejournal.com]

А я не понял, почему это контрпример. 12 нулей и 10 единиц после 10 операций над крайними точками дают 2 нуля и 10 по 1/2, потом 2 по 1/4 и 8 по 1/2, и т.д., пока не получим две одинаковые точки (по 31/64, если я не ошибаюсь).

[ro-che.livejournal.com]

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

[pussbigeyes.livejournal.com]

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

[mm-aa.livejournal.com]

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

[ro-che.livejournal.com]

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

[dmpogo.livejournal.com]

Хм, сразу хочется найти подсказку в условии. Откуда может взятся число 1000 ? Похоже на 2^10, какие-то деления отрезка пополам.