Условие
Какое наибольшее число точек можно поместить на отрезке длиной 1
так, чтобы на любом отрезке длиной d, содержащемся в этом отрезке,
лежало не больше 1 + 1000d2 точек?
Решение
Докажем сначала, что 33 точки разместить таким образом нельзя.
Действительно, если на отрезке длиной 1 находятся 33 точки, то
расстояние между какими-нибудь двумя из них не превосходит 1/32.
Отрезок с концами в этих точках содержит две точки, а он должен
содержать не более
1 + 1000/322 точек, т. е. менее двух точек.
Докажем теперь, что 32 точки разместить можно. Возьмем 32 точки,
делящие отрезок на равные части (концы данного отрезка входят в
число этих 32 точек). Тогда отрезок длиной d содержит либо [31d],
либо [31d] + 1 точек. Нужно доказать, что
[31d]
1000d2.
Если 31d < 1, то
[31d] = 0 < 1000d2. Если 31d
1, то
[31d]31d(31d )2 = 961d2 < 1000d2.
римечание
[x] — целая часть числа x, т. е. наибольшее целое число,
не превосходящее x.
Источники и прецеденты использования
