Freigeben über

Puzzle: floor() function

  • Artikel

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

  • Anonymous
    June 27, 2006
    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)
  • Anonymous
    June 27, 2006
    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.
  • Anonymous
    June 28, 2006
    Very nice and elegant solution!
  • Anonymous
    June 29, 2006
    Nice puzzle; I remember having it at a contest when I was in the 6th or 7th grade.