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

  • 0
    @Issac: Thanks, so if `x = -1.67` then I would $r$ew$r$ite it as: `-2 + 0.33`?2019-02-18

3 Answers 3

0
  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))
  • 0
    i think i am wrong, should just be (cb ≤ a < cb+1)2017-08-25
2

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.

  • 0
    Many thanks for a great solution. Very clever and succinct ;) !2011-02-04
1

You can see it here: