Multiply, divide, and floor

Let n be a positive integer and x any real number. If you multiply x by n, then divide by n, of course you get x back.

Now suppose you multiply x by n, round down, then divide by n, and round down again. Do you get x back?

Not necessarily. The last step rounds down to an integer, so you couldn’t possibly get x back unless x was an integer to begin with.

However, you do get back x rounded down to the nearest integer. In symbols,

\left\lfloor \frac{\lfloor nx \rfloor}{n} \right\rfloor = \lfloor x \rfloor

Here ⌊y⌋ is the floor of y, the greatest integer less than or equal to y. I found this via Problem 5 here.

The equation says that, in a limited sense, multiplication and division commute with taking floors. But you do have to assume n is an integer, and it’s important that you multiply first, then divide. The corresponding equation where you divide first doesn’t always hold.

The relationship above may not seem so surprising if you haven’t worked with floors, but generally floors and ceilings don’t play so nicely with other operations. The most tedious chapter of Concrete Mathematics is probably the one devoted to manipulating expressions with floors and ceilings. Once you expect these manipulations to be difficult, which they usually are, you find it remarkable that something would work out so simply.

I don’t know of an immediate application for this identity, though I vaguely recall wanting to use something like this and concluding that it probably wasn’t true.

 

Leave a Reply

Your email address will not be published.