TAOCP
Excise 1.2.4-35
$ \lfloor \frac{ (x + m) }{n} \rfloor = \lfloor \frac{ \lfloor x \rfloor +m }{n} \rfloor $, where $x$ is real, $m$ and $n$ are integers, $n >0$
Proof:
Obviously $\lfloor(x+m)/n \rfloor \geq \lfloor(\lfloor x \rfloor + m)/n \rfloor $, the only case that it is not equal is $(\lfloor x \rfloor +m)/n $and $(x+m)/n$ lies on different sides of an integer $k$, which means
$$1 > k -(\lfloor x \rfloor + m ) / n > 0 $$
and
$$ (x+m)/n - k > 0 $$ ......(1)
furthermore, $\lfloor x \rfloor + m $is integer, thus
$$k - (\lfloor x \rfloor + m)/n \geq 1/n $$......(2)
from (1) and (2)
$(x+m)/n -k + k - (\lfloor x \rfloor + m)/n = (x- \lfloor x \rfloor)/n > 1/n$ which is impossible. so only equal relation is valid.
No comments:
Post a Comment