Sum of Ceilings not less than Ceiling of Sum
Jump to navigation
Jump to search
Theorem
Let $\ceiling x$ be the ceiling function.
Then:
- $\ceiling x + \ceiling y \ge \ceiling {x + y}$
The equality holds:
- $\ceiling x + \ceiling y = \ceiling {x + y}$
if and only if either:
- $x \in \Z$ or $y \in \Z$
or:
- $x \bmod 1 + y \bmod 1 > 1$
where $x \bmod 1$ denotes the modulo operation.
Proof
From the definition of the modulo operation, we have that:
- $x = \floor x + \paren {x \bmod 1}$
from which we obtain:
- $x = \ceiling x - \sqbrk {x \notin \Z} + \paren {x \bmod 1}$
where $\sqbrk {x \notin \Z}$ uses Iverson's convention.
\(\ds \ceiling {x + y}\) | \(=\) | \(\ds \ceiling {\floor x + \paren {x \bmod 1} + \floor y + \paren {y \bmod 1} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \ceiling {\ceiling x - \sqbrk {x \notin \Z} + \paren {x \bmod 1} + \ceiling y - \sqbrk {y \notin \Z} + \paren {y \bmod 1} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \ceiling x + \ceiling y + \ceiling {\paren {x \bmod 1} + \paren {y \bmod 1} } - \sqbrk {x \notin \Z} - \sqbrk {y \notin \Z}\) | Ceiling of Number plus Integer |
We have that:
- $x \notin \Z \implies x \bmod 1 > 0$
As $0 \le x \bmod 1 < 1$ it follows that:
- $\sqbrk {x \notin \Z} \ge x \bmod 1$
Hence the inequality.
The equality holds if and only if:
- $\ceiling {\paren {x \bmod 1} + \paren {y \bmod 1} } = \sqbrk {x \notin \Z} + \sqbrk {y \notin \Z}$
that is, if and only if one of the following holds:
- $x \in \Z$, in which case $x \bmod 1 = 0$
- $y \in \Z$, in which case $y \bmod 1 = 0$
- both $x, y \in \Z$, in which case $\paren {x \bmod 1} + \paren {y \bmod 1} = 0$
- both $x, y \notin \Z$ and $\paren {x \bmod 1} + \paren {y \bmod 1} > 1$.
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $7$