Puzzle: floor() function


Proof that:


floor(x * n) = floor(x) + floor(x + 1/n) + floor(x + 2/n) + ... + floor(x + (n-1)/n)


Note: x is real, and n is integer.


Comments (4)

  1. First of all,  I thing there is a typo, n should be a positive integer since n=0 it doesn’t make sense and for n < 0 the equality is not true.

    There is an integer k, 0 <= k < n such that

    (1)          floor(x) + k/n <= x < floor(x) + (k+1)/n  .      

    The intuitive solution is that if we divide the interval [ floor(x), floor(x)+1 ) into n subintervals, then we can find an subinterval that contains x – if somebody wants the rigorous proof I can provide it 🙂 .

    By multiplying n to both sides of the inequality (1) we have

    (2)         n* floor(x) + k <= x * n < n * floor(x) + k + 1

    Therefore,

    (3)         floor(x * n) = n * floor(x) + k.

    Let’s consider i an integer, 0 <= i < n – k .

    Adding i/n to both sides of the inequality (1) gives us:

    (4) floor(x) + k/n + i/n <= x + i/n < floor(x) + (k+1)/n + i / n  .

    Since 0 <= i < n – k, and 0 <= k < n; therefore,

    (5) floor(x) <= floor(x) + k/n + i/n  

    and

    (6) floor(x) + (k+1)/n + i / n  <= floor(x)  + 1.

    Using (4) , (5) and (6) we have floor(x)  <= x + i/n <= floor(x)  + 1 which provides  

    (7) floor(x + i/n) = floor(x).

    Similarly , for the integer i, with n –k <= i < n, we have

    (8) floor(x)  + 1 <= floor(x) + k/n + i/n <= x + i/n < floor(x) + (k+1)/n + i / n  <= floor(x) + 2, which provides

    (9) floor(x + i/n) = floor(x) + 1.

    Considering i=0 to n-1 into (7) and (9) we have

    (10) floor(x) + floor(x + 1/n) + … + floor(x + (n-1)/n) =

               (n – k) * floor(x) + k * (floor(x) + 1) = n * floor(x) + k.

    Now, from (10) and (3) follows the equality required:

    floor(x * n) = floor(x) + floor(x + 1/n) + floor(x + 2/n) + … + floor(x + (n-1)/n)

  2. AdiOltean says:

    Good proof (and thx for the note on n being positive)

    There is another proof which goes like this:

    Let f(x) = floor(x) + floor(x + 1/n) + floor(x + 2/n) + … + floor(x + (n-1)/n) – floor(x * n). So, if f(x) = 0, then obviously the identity above holds, so the proof is done.

    Now, we can see that f(x + 1/n) = floor(x + 1/n) + floor(x + 2/n) + … + floor(x + (n-1)/n) + floor(x + 1) – floor(x * n + 1) = f(x), so f(x) is a periodic function with period 1/n or smaller.

    On the other side, we can easily see that f(x) = 0 for x in the [0, 1/n) interval. Given that its period is 1/n or smaller, means that f(x) = 0 everywhere.

  3. Very nice and elegant solution!

  4. Stefan Ciobaca says:

    Nice puzzle; I remember having it at a contest when I was in the 6th or 7th grade.

Skip to main content