2
$\begingroup$

Given x is a real number and c is a natural number. Prove that:

floor( floor(x) / c ) = floor( x / c )

When x > 0, I can prove it by let x = n + z where 0 < z < 1.
Then rhs = floor( n/c + z/c ) which equals to floor( floor(x) ) since z/c -> 0.
However, when x < 0, it's wrong when letting x = -( n + z ). Because it always give me a smaller negative number. Is my logic wrong here? Any hint?

Thanks,
Chan

$\endgroup$
  • 1
    $\begingroup$ I suspect that you want $x=-n+z$ (no parentheses around $n+z$) as, for instance, $\text{floor}(-1.5)=-2$. $\endgroup$ – Isaac Feb 4 '11 at 6:34
  • $\begingroup$ @Issac: Thanks, so if x = -1.67 then I would rewrite it as: -2 + 0.33? $\endgroup$ – Chan Feb 4 '11 at 6:41
1
$\begingroup$

You can see it here:

$\endgroup$
  • 1
    $\begingroup$ @Chandru1: Thanks but you spoiled me :(! $\endgroup$ – Chan Feb 4 '11 at 6:42
  • $\begingroup$ @chan: Sorry chan. $\endgroup$ – anonymous Feb 4 '11 at 7:24
  • $\begingroup$ This post no longer exists. $\endgroup$ – franklin Feb 18 '19 at 17:50
2
$\begingroup$

This is the special case $\rm\ m = 1\ $ in a proof I presented here. See that thread for more on the universal viewpoint that explains the simplicity of this proof. For convenience, here is the proof.

LEMMA $\rm\: \ \lfloor x/(mn)\rfloor\ =\ \lfloor{\lfloor x/m\rfloor}/n\rfloor\ \ $ for $\rm\ \ n > 0$

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

$\rm\quad\quad\quad\quad\quad\iff\quad\ \ k\ \le\ \:{\lfloor x/m\rfloor}/n$

$\rm\quad\quad\quad\quad\quad\iff\ \ nk\ \le\ \ \lfloor x/m\rfloor$

$\rm\quad\quad\quad\quad\quad\iff\ \ nk\ \le\:\ \ \ x/m$

$\rm\quad\quad\quad\quad\quad\iff\ \ \ \ k\ \le\:\ \ \ x/(mn)$

$\rm\quad\quad\quad\quad\quad\iff\ \ \ \ k\ \le\ \ \lfloor x/(mn)\rfloor $

Compare the above trivial proof to more traditional proofs, e.g. the special case $\rm\ m = 1\ $ here.

$\endgroup$
  • $\begingroup$ Many thanks for a great solution. Very clever and succinct ;) ! $\endgroup$ – Chan Feb 4 '11 at 15:34
0
$\begingroup$
  1. Start with equation ⌊⌊a⌋/b⌋=c
  2. replace outermost floor with (c ≤ ⌊a⌋/b)
  3. multiply by b (cb ≤ ⌊a⌋)
  4. this is the same as (cb ≤ a)
  5. (I left out a constraint on the right (easier for me))
$\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.