Не могу сдержаться
Все-таки я выпускник "Прикладной математики". Задачка от avva. Решение у меня было в LaTeX, сконвертировано с помощью tth 3.8.
1 Постановка задачи
Даны 22 точки в промежутке [0,1] (необязательно различные). Вы 20 раз повторяете следующую операцию: выбираете две из них и заменяете обе на точку, лежащую ровно посредине между ними. После 20 таких ходов остается всего две точки. Доказать: вы всегда сможете выбрать ходы так, чтобы между двумя оставшимися точками расстояние было не больше [1/1000].
2 Решение
Пусть есть некоторое разбиение точек на 2 группы по 11: xi и yi. Эти точки будут в процессе замены сходится к точкам:
X =
x1
210
+
x2
210
+
x3
29
+
x4
28
+ ... +
x11
2
Y =
y1
210
+
y2
210
+
y3
29
+
y4
28
+ ... +
y11
2
Тогда:
X-Y =
x11 - y11
2
+ ... +
x2-y2
210
+
x1-y1
210
Заметим, что при разбиении отрезка длины l на неравные части M точками, всегда можно найти две точки расстояние между которыми не больше [l/(M-1)] и две точки расстояние между которыми не меньше [l/(M-1)]. Пусть l - максимальное расстояние между нашими точками, очевидно l <= 1. Тогда:
X-Y <=
l
42
+ ... +
x2-y2
210
+
x1-y1
210
При этом l могла уменьшиться на [l/21]. Проделаем следующую итерацию:
X-Y <=
l
42
-
19
76·20
+ ... +
x2-y2
210
+
x1-y1
210
Продолжая этот процесс получим:
|X-Y| <= C·l
Заменив l на максимальное ее значение (1) будем действовать следующим образом. Пока сумма последовательности больше 0 вычитаем следующее значение, а в противном случае прибавляем его. Получим (для расчетов я использовал sympy, но можно посчитать и руками):
|X-Y| <= 11722373/84557168640 ~= 0.0001386325155931805807446676587
Таким образом, мы получили величину меньшую [1/1000].
1 Постановка задачи
Даны 22 точки в промежутке [0,1] (необязательно различные). Вы 20 раз повторяете следующую операцию: выбираете две из них и заменяете обе на точку, лежащую ровно посредине между ними. После 20 таких ходов остается всего две точки. Доказать: вы всегда сможете выбрать ходы так, чтобы между двумя оставшимися точками расстояние было не больше [1/1000].
2 Решение
Пусть есть некоторое разбиение точек на 2 группы по 11: xi и yi. Эти точки будут в процессе замены сходится к точкам:
X =
x1
210
+
x2
210
+
x3
29
+
x4
28
+ ... +
x11
2
Y =
y1
210
+
y2
210
+
y3
29
+
y4
28
+ ... +
y11
2
Тогда:
X-Y =
x11 - y11
2
+ ... +
x2-y2
210
+
x1-y1
210
Заметим, что при разбиении отрезка длины l на неравные части M точками, всегда можно найти две точки расстояние между которыми не больше [l/(M-1)] и две точки расстояние между которыми не меньше [l/(M-1)]. Пусть l - максимальное расстояние между нашими точками, очевидно l <= 1. Тогда:
X-Y <=
l
42
+ ... +
x2-y2
210
+
x1-y1
210
При этом l могла уменьшиться на [l/21]. Проделаем следующую итерацию:
X-Y <=
l
42
-
19
76·20
+ ... +
x2-y2
210
+
x1-y1
210
Продолжая этот процесс получим:
|X-Y| <= C·l
Заменив l на максимальное ее значение (1) будем действовать следующим образом. Пока сумма последовательности больше 0 вычитаем следующее значение, а в противном случае прибавляем его. Получим (для расчетов я использовал sympy, но можно посчитать и руками):
|X-Y| <= 11722373/84557168640 ~= 0.0001386325155931805807446676587
Таким образом, мы получили величину меньшую [1/1000].