22 точки от Н.Алона

[maxal]

Задачка от Ноги Алона:

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

(отсюда)

[Sonic86]

Способ выбора точек, видимо, такой: берем 2 крайние и находим середину. Ну еще можно считать, что 2 точки расположены в концах интервала, а вот как оценить пока не вижу.

[ИСН]

Там, откуда - уже приведён пример, когда эта очевидная эвристика ("ну обязано же!") не срабатывает.

[TOTAL]

Пусть $x_1+x_2+, \cdots+ x_{10}=1,$ причем $x_k$ - неотрицательны,
и пусть $k_1, \cdots, k_{10}$ - это перестановка чисел $1, \cdots, 10.$

Верно ли, что сумму $S=\pm 2^{-k_1}\cdot x_1 \pm \cdots \pm 2^{-k_{10}} \cdot x_{10}$ можно сделать по модулю не больше, чем $2^{-9}?$

Разрешается
a) выбирать какую угодно перестановку $k_1, \cdots, k_{10}$
б) перед каждым произведением $2^{-k_i} \cdot x_{i}$ ставить какой угодно знак

Если верно, то утверждение задачи про $22$ точки будет просто следствием.

[anwior]

Если правильно, что и точка 0, и точка 1 включены в условие задачи, то
доказать требуемое нельзя --- ибо это, в общем-то, неверно. Например,
20 точек находятся в позиции 0, а оставшиеся 2 точки находятся в позиции 1.
После выполнения 20 ходов растояние между двумя оставшимися точками
будет превышать значение 0, 0028.

[ИСН]

Смотря каких ходов. С такой начальной расстановкой я берусь свести его к нулю.

[anwior]

Я обрадуюсь за Вас, если Вы правы (если у Вас получится).
У меня не получается.

[neo66]

Радуйтесь! У меня получилось!

[Юстас]

Случай, когда каждая точка повторяется четное число раз, очевиден по индукции.
Прочитал решения общего случая, забавно: что называется, классическая олимпиадная задача.

[anwior]

neo66
Где решение? Когда увижу его здесь, то
а) перепроверю;
б) обрадуюсь за тебя;
в) публично извинюсь перед форумчанами (признаю себя тупицей).
И как бы там нибыло, хочу усложнить начальную позицию:
вариант 2. 19 точек в позиции 0, а 3 точки в позиции 1;
вариант 3. 18 точек в позиции 0, а 4 точки в позиции 1;
вариант 4. 17 точек в позиции 0, а 5 точек в позиции 1;
вариант 5. 16 точек в позиции 0, а 6 точек в позиции 1;
вариант 6. 15 точек в позиции 0, а 7 точек в позиции 1;
вариант 7. 14 точек в позиции 0, а 8 точек в позиции 1;
вариант 8. 13 точек в позиции 0, а 9 точек в позиции 1;
вариант 9. 12 точек в позиции 0, а 10 точек в позиции 1;
вариант 10. 11 точек в позиции 0 и 11 точек в позиции 1.

Добавление через какой-то промежуток времени
Каким то образом сообразил, что вариант 10 удовлетворяет
требуемому заключению. Про остальные варианты у меня
нет позитивных ответов.

[Юстас]

По ссылке в первом сообщении уже есть решение, так что можете не мучаться с "контрпримерами"

[anwior]

Признаю себя
САМЫМ ТУПЫМ НА ЭТОТ ДЕНЬ УЧАСТНИКОМ ФОРУМА dxdy!
И делаю это (ведь давал же слово) вовсе не с огорчением,
а даже с радостью.
А доволен то тем, что без хождения по ссылкам
самостоятельно разобрался со всеми своими вариантами и
нашел все 10 позитивных ответов.

P. S. Как бы хотелось, чтобы впредь таким же образом
поступали (когда явно не правы) все без исключения форумчане.
Дай Боже каждому частицу мужества.
22 января 2009 года.

[Руст]

Вообще задачу можно сформулировать так. Задана N точек в интервале [0,1] оценить минимальное значение
(1)

$$\sum_{i=1}^N a_ix_i$$

, где $a_i=\pm 2^{-n_i},n_i\in Z_+ (n_i\ge 0)$,
причеём сумма положительных коэффициентов равна 1, сумма отрицательных -1. Мне кажется более правильная оценка здесь $2^{2-N}$.
Интересно так же обобщение этой задачи на k-мерные нормированные пространства, предполагая, что $x_i$ из единичного шара. Здесь ответ по видимому $C_ka_k^{-N}$ и от нормы (евклидовой - $|x_i|=(\sum_{j=1}^k x_{ij}^2)^{1/2}$ или $\sum_j |x_{ij}|$ или $max_j |x_{ij}|$) зависит только коэффициент $C_k$.
Случай maxala более прост. $N=2n+2$, выберем не все возможные виды (1), а только такие $\sum_{j=1}^n 2^{-j}(x_{s(j)}-x_{s(j+n+1)})+2^{-n}(x_{s(n+1)}-x_{s(2n+2)})$
Доказательство по индукции. Выберем вначале минимальное $|x_i-x_j|$. Если имеется частичная сумма $z_l=\sum_{j=1}^l2^{-j}(x_{s(j)}-x_{s(j+n+1)})$ из оставшихся выберем $x_{s(l+1)},x_{s(l+n+2)}$ так, чтобы $|z_{l+1}|$ был минимальным. Тогда получим $|z_l|\le 2^{-l}$, последний шаг, когда коэффициенты $2^{-n}$ а не $2^{-n-1}$ не уменьшают оценку и в итоге получается оценка $2^{-n}$.

[bot]

Руст писал(а):

Вообще задачу можно сформулировать так. Задана N точек в интервале [0,1] оценить минимальное значение
(1)

$$|\sum_{i=1}^N a_ix_i|$$

, где $a_i=\pm 2^{-n_i},n_i\in Z_+ (n_i\ge 0)$,
причём сумма положительных коэффициентов равна 1, сумма отрицательных -1.

Угу, вчера вечером сначала попробовал трисекцию и поняв, что это слишком грубо, к этому же пришёл. Дальше уже не думал - заснул.