4
$\begingroup$

I'm trying to prove rigorously the following:

$\lfloor x/a/b \rfloor$ = $\lfloor \lfloor x/a \rfloor /b \rfloor$ for $a,b>1$

So far I haven't gotten far. It's enough to prove this instead

$\lfloor z/c \rfloor$ = $\lfloor \lfloor z \rfloor /c \rfloor$ for $c>1$

since we can just put $z=\lfloor x/a \rfloor$ and $c=b$.

$\endgroup$
  • 1
    $\begingroup$ Just to say, it's not homework. $\endgroup$ – hermionestranger Jul 19 '12 at 12:10
  • $\begingroup$ hint: Start with $x=qa+r$ and $q=q'b+r'$ ($0\le r <a$ and $0\le r' <b$) then $$x=q'ab+(ar'+r)\ \ \text{with $\ 0\le ar'+r < a(b-1)+a$}$$ $\endgroup$ – Raymond Manzoni Jul 19 '12 at 12:20
  • 3
    $\begingroup$ @hermionestranger You might also like to note that in the statement of the problem, we require $a$ and $b$ to be integers, as the result is not true otherwise. $\endgroup$ – Old John Jul 19 '12 at 12:25
  • $\begingroup$ @OldJohn Actually, you just need $b$ to be an integer. $\endgroup$ – Thomas Andrews Jul 19 '12 at 13:13
  • $\begingroup$ Also, $b>1$ is stricter than needed; $b=1$ trivially works, too. $\endgroup$ – celtschk Jul 19 '12 at 15:42
6
$\begingroup$

This theorem is not true if $b$ is not an integer. Take $x=b=1.5$ and take $a=1$.

If $b$ is an integer, this follows from the rule $$\left\lfloor \frac{y}{b}\right\rfloor = \left\lfloor \frac{\lfloor y \rfloor}b\right\rfloor$$

Setting $y=\frac x a$.

Showing this rule, then, suffices.

Let $y = \lfloor y \rfloor + \{y\}$, where $0\leq \{y\} < 1$.

Use division algorithm to write $\lfloor y \rfloor = qb + r$ with $0\leq r <b$.

The $\frac{\lfloor y \rfloor} b = q + \frac{r}{b}$, and $0\leq \frac{r}{b} <1$, so

$$\left\lfloor \frac{\lfloor y \rfloor}b\right\rfloor = q$$

On the other hand, since $[y]< (q+1)b$, since $0\leq\{y\}<1$, then $y = [y]+\{y\}<(q+1)b$.

So $q \leq \frac y b < q+1$ and again $$\left\lfloor \frac{y}{b}\right\rfloor = q $$

$\endgroup$
3
$\begingroup$

This is best done universally, i.e. using the universal definition of floor

$\rm\qquad\qquad\qquad\qquad\ \ \ k\,\le\, \lfloor x\rfloor \color{#c00}{\iff} k\,\le\, x,\quad {\rm for\ all}\,\ k\in\Bbb Z$

Lemma $\rm\qquad\quad\color{#0a0}{\lfloor r/n\rfloor}\, =\, \lfloor{\lfloor r\rfloor}/n\rfloor\ \ $ for $\rm\ \ 0<n\in\Bbb Z,\,\ r\in\Bbb R$

Proof $\rm\quad\quad\quad\quad\quad \ \ \ k\ \le \lfloor{\lfloor r\rfloor}/n\rfloor$

$\rm\quad\quad\quad\quad\quad\color{#c00}\iff\quad k\ \le\ \:{\lfloor r\rfloor}/n$

$\rm\quad\quad\quad\quad\quad\iff\ \ nk\ \le\ \ \lfloor r\rfloor\qquad\!\! by\,\ n>0$

$\rm\quad\quad\quad\quad\quad\color{#c00}\iff\ \ nk\ \le\,\ \ \ r\qquad\, by\,\ n\in\Bbb Z$

$\rm\quad\quad\quad\quad\quad\iff\ \ \ \ k\ \le\:\ \ \ r/n\quad by\,\ n>0 $

$\rm\quad\quad\quad\quad\quad\color{#c00}\iff\ \ \ \ k\ \le\ \ \color{#0a0}{\lfloor r/n\rfloor}\quad {\bf QED} $

Yours is special case $\rm\ r = x/a,\,\ n = b.$

$\endgroup$
  • 1
    $\begingroup$ +1 for the nice proof technique $\;\langle \forall k :: k \leq E \iff k \leq F \rangle \iff E = F\;$ (assuming $\;k,E,F\;$ are all integers, or all reals). That was unknown to me, and in retrospect blindingly obvious. This should have been the accepted answer. Thanks! $\endgroup$ – Marnix Klooster Jan 23 '14 at 20:31
  • $\begingroup$ I just found Dijkstra's EWD1315, which states that such proofs are known as "proofs by indirect equality". $\endgroup$ – Marnix Klooster Jan 30 '14 at 20:10
  • 1
    $\begingroup$ @Marnix I've never heard that term before. Perhaps it is specific to computer science. If you want to view it more generally one can use ideas from category theory, viz. that ceiling,floor are left,right adjoints to the inclusion $\,\Bbb Z\subset \Bbb R,\,$ and Yoneda's Lemma. Such viewpoints are mentioned numerous times here. $\endgroup$ – Bill Dubuque Jan 30 '14 at 20:33
1
$\begingroup$

Let $\lfloor x/a \rfloor$ = c(say)=>x=ca+d 0≤d

Let $\lfloor c/b \rfloor$=e(say)=>c=be+f 0≤f

=>x=ca+d=(be+f)a+d=abe+af+d.

$\frac{x}{a}$=be+f+ $\frac{d}{a}$

$\frac{\frac{x}{a}}{b}$=e+$\frac{f}{b}$+$\frac{d}{ab}$

=>$\lfloor x/a/b \rfloor$ = e = $\lfloor c/b \rfloor$ = $\lfloor \lfloor x/a \rfloor /b \rfloor$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.