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

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)

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.