TAOCP 1.2.4 Exercise 7

Let $x$ and $y$ be arbitrary real numbers.

taocpmathematicsalgorithmsvolume-1math-simple

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 7. [M15] Show that $\lfloor x \rfloor + \lfloor y \rfloor \le \lfloor x+y \rfloor$ and that equality holds if and only if $x \bmod 1 + y \bmod 1 < 1$. Does a similar formula hold for ceilings?

Verified: no
Solve time: 5m31s

Solution

Let $x$ and $y$ be arbitrary real numbers. By definition, $x = \lfloor x \rfloor + (x \bmod 1)$ and $y = \lfloor y \rfloor + (y \bmod 1)$, by equation (4). Then

$$ x + y = \lfloor x \rfloor + \lfloor y \rfloor + (x \bmod 1 + y \bmod 1). $$

Let $f = x \bmod 1 + y \bmod 1$. Since $0 \le x \bmod 1 < 1$ and $0 \le y \bmod 1 < 1$ by equation (2), we have $0 \le f < 2$. Therefore

$$ \lfloor x+y \rfloor = \lfloor \lfloor x \rfloor + \lfloor y \rfloor + f \rfloor. $$

Since $\lfloor x \rfloor$ and $\lfloor y \rfloor$ are integers, we can separate the integer part from $f$:

$$ \lfloor x+y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + \lfloor f \rfloor. $$

Now, $f = x \bmod 1 + y \bmod 1 < 2$, so $\lfloor f \rfloor$ is either $0$ or $1$. Hence

$$ \lfloor x \rfloor + \lfloor y \rfloor \le \lfloor x+y \rfloor, $$

with equality if and only if $\lfloor f \rfloor = 0$, that is, if and only if

$$ x \bmod 1 + y \bmod 1 < 1. $$

For the analogous formula for ceilings, write $x = \lceil x \rceil - (1 - x \bmod 1)$ and $y = \lceil y \rceil - (1 - y \bmod 1)$. Then

$$ x + y = \lceil x \rceil + \lceil y \rceil - \bigl(2 - (x \bmod 1 + y \bmod 1)\bigr) = \lceil x \rceil + \lceil y \rceil - (2 - f). $$

We have $0 \le 2 - f \le 2$, so

$$ \lceil x+y \rceil = \lceil \lceil x \rceil + \lceil y \rceil - (2 - f) \rceil = \lceil x \rceil + \lceil y \rceil - \lfloor 2 - f \rfloor. $$

Since $0 \le 2 - f < 2$, $\lfloor 2 - f \rfloor$ is either $1$ or $0$, depending on whether $f \ge 1$ or $f < 1$. Therefore

$$ \lceil x+y \rceil = \lceil x \rceil + \lceil y \rceil - 1 \quad \text{if } f \ge 1, $$

and

$$ \lceil x+y \rceil = \lceil x \rceil + \lceil y \rceil \quad \text{if } f < 1. $$

Equivalently,

$$ \lceil x+y \rceil \le \lceil x \rceil + \lceil y \rceil, $$

with equality if and only if $x \bmod 1 + y \bmod 1 < 1$.

This completes the proof.

∎