Rounding Percents: how far from 100?

Question

Given n positive, rational numbers $a_1, a_2...a_n$ where $\sum_{i=1}^{n} a_i = 100$, what is the tightest limit we can put on the difference of (the sum of each number rounded to the nearest integer) and (100)?

In other words, what is the tightest bound, in terms of n, for:

$|(\sum_{i=1}^{n} ||a_i||) - 100|$

What happens when you take the floor of each term instead?

$| (\sum_{i=1}^{n} \lfloor a_i \rfloor ) - 100 |$

I stumbled across this problem while trying to round percents. You could say that the bound differs from 100 by at most n, since at most there are n numbers with decimals, each decimal can be at most arbitrarily close to 1. But is there a tighter limit?

In the rounded case, you can construct numbers that all end in 0.5 for an even n and show that, since they all round in the same direction, they will differ from 100 by at most n/2. (Is that correct?)

But I'm at a loss for the floor case. I'm not sure if the requirement that rational numbers add to an integer reduces the bound.

Answer 1

For floors, the optimal bound is $n-1$.

To see why it is a bound, notice that $a_i \leq 1+\lfloor a_i \rfloor$ for every $i$, so that $\sum_{i=1}^{n-1} a_i \leq n-1+\sum_{i=1}^{n-1}\lfloor a_i \rfloor$, and hence $a_n=100-\bigg(\sum_{i=1}^{n-1} a_i\bigg) \geq B$ where $B=100-(n-1+\sum_{i=1}^{n-1}\lfloor a_i \rfloor)$. Now $B$ is an integer, so $a_n\geq B$ implies $\lfloor a_n \rfloor \geq B$, which means that $\sum_{i=1}^{n-1}\lfloor a_i \rfloor \geq 100-(n-1)$. On the other side, we clearly have $\sum_{i=1}^{n}\lfloor a_i \rfloor \leq \sum_{i=1}^{n} a_i=100$. This proves the bound.

To see why the bound is optimal, let $\varepsilon\in(0,\frac{1}{n-1})$ and $a_i=1-\varepsilon$ for $i<n$, and $a_n=(100-(n-1))+(n-1)\varepsilon$.

Answer 2

For the nearest integer variation, the optimal bound is $\lfloor\frac{n}2\rfloor\wedge100:=\min\{\lfloor\frac{n}2\rfloor,100\}$. First note that $|x-[x]|\le\frac12$ (here $[x]$ is what you refer to as $||x||$) for any $x\in\mathbb R$. Thus $$\left|\sum_{i=1}^n[a_i]-100\right|\le\sum_{i=1}^n|[a_i]-a_i|\le\frac{n}2,$$ and then since $\sum_{i=1}^n[a_i]-100$ is an integer we can replace $\frac{n}2$ with $\lfloor\frac{n}2\rfloor$.

For $0<x<\frac12$, we have $[x]=0\le2x$, and for $x\ge\frac12$ we have $0<[x]\le x+\frac12\le2x$, so we always have $0\le[x]\le2x$ for $x>0$. This implies $0\le\sum_{i=1}^n[a_i]\le200$. Combining this with the above yields $$\left|\sum_{i=1}^n[a_i]-100\right|\le\left\lfloor\frac{n}2\right\rfloor\wedge100$$ as claimed. We show now this is optimal. If $n\le200$, set $a_i=\frac12$ for $i<n$ and $a_n=100-\frac{n-1}2$. Clearly $[a_i]=1$ for $i<n$, and $$[a_n]=\begin{cases}100-\frac{n-1}2&\text{if $n$ is odd,}\\ 100-\frac{n}2+1&\text{if $n$ is even.} \end{cases}$$ Hence $\sum_{i=1}^n[a_i]=100+\frac{n-1}2$ if $n$ is even, $100+\frac{n}2$ if $n$ is odd, and in either case we have $\left|\sum_{i=1}^n[a_i]-100\right|=\lfloor\frac{n}2\rfloor$. If $n>200$ then put $a_i=\frac{100}n$ for all $i$, so $[a_i]=0$ and $\left|\sum_{i=1}^n[a_i]-100\right|=100$. This completes the proof.

For the floors, follow Ewan Delanoy's answer, but note that through the same kind of tricks you should end up with $(n-1)\wedge100$.