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

[avva]

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

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

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

Comments

[white-lee.livejournal.com]

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

[avva.livejournal.com]

:)

[egle.livejournal.com]

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

[avva.livejournal.com]

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

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

[esperador.livejournal.com]

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

[renatm.livejournal.com]

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

[pigmeich.livejournal.com]

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

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

[pussbigeyes.livejournal.com]

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

[ro-che.livejournal.com]

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

[dmpogo.livejournal.com]

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

[spamsink.livejournal.com]

Расстояние между точками не более 1/1000 (на самом деле 1/1024) - значит, первые 10 двоичных цифр координаты у них совпадают. Операция "среднее арифметическое" дает точку с координатой, совпадающей с одной из исходных точек по N+1 двоичным цифрам, если исходные до того совпадали по N.

[neatfires.livejournal.com]

Можно попытаться начать с двух точек, находящихся друг к другу на расстоянии меньше 1/1000, и показать, что если вывернуть алгоритм наизнанку, т.е. "удваивать" точки, то при любой(?) последовательности шагов в конечном итоге каждую из 22 точек можно будет поставить в любом месте на отрезке.

[nmoroz.livejournal.com]

Я бы сказал, что не получится даже найти такое распределение точек, при котором 2 конечные будут на расстоянии больше 1/2^20.

[dmpogo.livejournal.com]

А если только 4 точки, то не больше 1/4 ?

[nmoroz.livejournal.com]

Получается так. Но это в случае (который я считаю крайним), когда все точки, кроме одной, на одном конце, а эта одна точка - на другом конце.
В этом случае наиболее выгодным для нас путём можно привести к тому, что расстояние между последними двумя будет 1/2^N, где N - число ходов.
Другими словами, для данного условия задачи с ограничением конечного расстояния в 1/1000 можно было ограничиться и 12 точками (возможно свести к 1/1024 между последними).

[lagu.livejournal.com]

Есть решение :)

[avva.livejournal.com]

Хорошо, но не рассказывайте пока :-)

[big-hunter.livejournal.com]

Решение есть. Буду перепроверять, а то как-то просто. Когда можно рассказать?

[avva.livejournal.com]

Напишите у себя и дайте ссылку? Я пока не буду смотреть :)

[janatem.livejournal.com]

Пока не думал, но есть уверенность, что 1/1000 можно заменить на 1/1024 = 2^(-(количество операций)/2). ;)

[rymis.livejournal.com]

Я мог ошибиться в расчетах, но решение там (http://rymis.livejournal.com/20969.html) :)

[nadja-s.livejournal.com]

Если я правильно поняла, одиннадцатую пару вы выбираете так, чтобы расстояние было не больше 1/21. А как все-таки вы десятую пару выбираете (насчет знака понятно)?

...и две точки расстояние между которыми не меньше [l/(M-1)]

Это не совсем так, потому что точки могут совпадать - например, все. Но я пока не поняла, как это используется в вашем решении - так что, может, это и неважно.

[arborea.livejournal.com]

Говорят, задачка не Алона, а Д.В. Фомина :)

[flaass.livejournal.com]

Легко могу поверить. Небось, и решение где-нибудь выложено?