3
$\begingroup$

In connection with a problem I've asked I have noticed the inequality $$\left\lceil\frac{a+b}2\right\rceil \le \left\lceil\frac{a}2\right\rceil + \left\lceil\frac{b}2\right\rceil$$ for $a,b\in\mathbb Z$.

Unless I am missing something, we could prove in a similar way $$\left\lceil\frac{a_1+a_2+\dots+a_k}k\right\rceil \le \left\lceil\frac{a_1}k\right\rceil + \left\lceil\frac{a_2}k\right\rceil + \dots + \left\lceil\frac{a_k}k\right\rceil.$$ Again, only for integer values of $a_1,a_2,\dots,a_k$. EDIT: As the answerers pointed out, this is in fact true for real numbers, not only for integers.

Is there a simple proof for this inequality? (Ideally without considering too many separated cases.)

Can this inequality be strengthened in some way?

$\endgroup$
2
  • 1
    $\begingroup$ The statement is also true for real numbers $a_1, \ldots, a_k$, as my proof below shows. $\endgroup$
    – P. Koymans
    Dec 29, 2017 at 10:53
  • $\begingroup$ @P.Koymans Yes, I've noticed this after your answer. I remember that I thought I had a counterexample when thinking about the $k=2$ version, but since I tried various versions back then (some of them with floor function) I have probably mixed up something. Thanks for your answer! $\endgroup$ Dec 29, 2017 at 10:55

2 Answers 2

6
$\begingroup$

Note that by definition $\lceil x \rceil$ is the smallest integer $n$ such that $n \geq x$. Now in order to show that $$ \lceil \frac{a_1 + a_2 + \cdots + a_k}{k} \rceil \leq \lceil \frac{a_1}{k} \rceil + \lceil \frac{a_2}{k} \rceil + \cdots + \lceil \frac{a_k}{k} \rceil, $$ we merely have to show that $$ \frac{a_1 + a_2 + \cdots + a_k}{k} \leq \lceil \frac{a_1}{k} \rceil + \lceil \frac{a_2}{k} \rceil + \cdots + \lceil \frac{a_k}{k} \rceil, $$ since the RHS is an integer. But this is straightforward.

$\endgroup$
1
  • $\begingroup$ This is much better indeed. Good job Peter :) $\endgroup$ Dec 29, 2017 at 11:15
2
$\begingroup$

Fix $k>0$ and $a_1,\ldots,a_k \in \mathbf{R}$. Then, there exist unique $b_1,\ldots,b_k \in \mathbf{Z}$ and $c_1,\ldots,c_k \in [0,k)$ such that $a_i=kb_i+c_i$. Hence the inequality reduces to $$ \left\lceil \sum_{i\le k}\frac{c_i}{k}\right\rceil \le \sum_{i\le k}\left\lceil \frac{c_i}{k} \right\rceil $$ Let $x$ be the number of $i\le k$ such that $c_i\neq 0$. Then the inequality can be rewritten as $$ \left\lceil \sum_{i\le k, \,c_i \neq 0}\frac{c_i}{k}\right\rceil \le x. $$ This is true because $$ \left\lceil \sum_{i\le k, \,c_i \neq 0}\frac{c_i}{k}\right\rceil \le \left\lceil \frac{x\cdot k}{k}\right\rceil \le x. $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .