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

• 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.