Разделы 
Дополнительно
Задача по математике - 3589
2019-06-12 
Округлением числа называется замена его одним из двух ближайших целых чисел.
Даны $n$ чисел. Докажите, что можно так округлить их, чтобы сумма любых $m$ округленных чисел ($1 \leq m \leq n$) отличалась от суммы этих же неокругленных чисел не более чем на $\frac{n + 1}{4}$.
Решение:
Пусть $x_1, x_2, \cdots, x_n$ - данные числа, занумерованные в порядке возрастания их дробных частей $\alpha_i = x_i - [x_i]$.
Округлим первые $k$ из этих чисел в меньшую сторону, а остальные - в большую; $k$ будет выбрано ниже. Легко видеть, что наибольшая ошибка при округлении будет накапливаться при вычислении одной из сумм
$x_1 + x_2 + \cdots + x_k$ или $x_{k+1} + x_{k+2} + \cdots + x_n$.
Модуль первой из ошибок равен
$\alpha_1 + \alpha_2 + \cdots + \alpha_k \leq k \alpha_k$,
а второй
$(1 - \alpha_{k+1} + \cdots + (1 - \alpha_n) \leq (n-k) (1 - \alpha_{k+1})$.
Выберем теперь $k$ так, чтобы выполнялись неравенства
$ka_k \leq \frac{n + 1}{4}$ и $(n - k) (1 - a_{k+1}) \leq \frac{n + 1}{4}$.
Для этого достаточно взять наибольшее $k$, для которого выполнено первое неравенство; тогда $\alpha_{k+1} > \frac {n+1}{(k+1)}$, поэтому выполнено и второе неравенство $1 - \alpha_{k+1} < 1 - \frac {n+1}{4 (k+1)} \leq \frac {n+1}{4(n-k)}$ (поскольку $\frac {n+1}{4(k+1)} + \frac {n+1}{4(n-k)} = \frac {(n+1)^2}{4(k+1)(n-k)} \geq 1$ при $0 < k < n$.
Для нечетного $n$ оценка погрешности, указанная в условии, точная (пример: $x_1 = x_2 = \cdots = x_n = 1/2$). Для четного $n$ ее можно несколько улучшить, заменив $\frac{n+1}{4}$ на $\frac{n+1}{4} - \frac{1}{n+1}$. (пример: $x_1 = x_2 = \cdots = x_n = \frac {n}{2(n+1)}))^{ \prime}$
Округлением числа называется замена его одним из двух ближайших целых чисел.
Даны $n$ чисел. Докажите, что можно так округлить их, чтобы сумма любых $m$ округленных чисел ($1 \leq m \leq n$) отличалась от суммы этих же неокругленных чисел не более чем на $\frac{n + 1}{4}$.
Решение:
Пусть $x_1, x_2, \cdots, x_n$ - данные числа, занумерованные в порядке возрастания их дробных частей $\alpha_i = x_i - [x_i]$.
Округлим первые $k$ из этих чисел в меньшую сторону, а остальные - в большую; $k$ будет выбрано ниже. Легко видеть, что наибольшая ошибка при округлении будет накапливаться при вычислении одной из сумм
$x_1 + x_2 + \cdots + x_k$ или $x_{k+1} + x_{k+2} + \cdots + x_n$.
Модуль первой из ошибок равен
$\alpha_1 + \alpha_2 + \cdots + \alpha_k \leq k \alpha_k$,
а второй
$(1 - \alpha_{k+1} + \cdots + (1 - \alpha_n) \leq (n-k) (1 - \alpha_{k+1})$.
Выберем теперь $k$ так, чтобы выполнялись неравенства
$ka_k \leq \frac{n + 1}{4}$ и $(n - k) (1 - a_{k+1}) \leq \frac{n + 1}{4}$.
Для этого достаточно взять наибольшее $k$, для которого выполнено первое неравенство; тогда $\alpha_{k+1} > \frac {n+1}{(k+1)}$, поэтому выполнено и второе неравенство $1 - \alpha_{k+1} < 1 - \frac {n+1}{4 (k+1)} \leq \frac {n+1}{4(n-k)}$ (поскольку $\frac {n+1}{4(k+1)} + \frac {n+1}{4(n-k)} = \frac {(n+1)^2}{4(k+1)(n-k)} \geq 1$ при $0 < k < n$.
Для нечетного $n$ оценка погрешности, указанная в условии, точная (пример: $x_1 = x_2 = \cdots = x_n = 1/2$). Для четного $n$ ее можно несколько улучшить, заменив $\frac{n+1}{4}$ на $\frac{n+1}{4} - \frac{1}{n+1}$. (пример: $x_1 = x_2 = \cdots = x_n = \frac {n}{2(n+1)}))^{ \prime}$
