# Floor(x)/y = floor(x/y), y in Z

jaw088
Hi,

I'm trying to proof that:
$$\left\lfloor \frac{\left\lfloor x \right\rfloor}{y} \right\rfloor= \left\lfloor \frac{x}{y} \right\rfloor$$ for the specific case where y is an integer.

At the recommendation of somebody who I discussed the problem with, here's how I started:

$$\lfloor x \rfloor \le x < \lfloor x \rfloor + 1$$
$$\frac{\lfloor x \rfloor}{y} \le \frac{x}{y} < \lfloor \frac{x}{y} \rfloor + \frac{1}{y}$$
$$\left\lfloor \frac{\lfloor x \rfloor}{y} \right\rfloor \le \left\lfloor \frac{x}{y} \right\rfloor$$

And from there, prove that the case of $$\left\lfloor \frac{\lfloor x \rfloor}{y} \right\rfloor < \left\lfloor \frac{x}{y} \right\rfloor$$ is impossible, leaving $$\left\lfloor \frac{\lfloor x \rfloor}{y} \right\rfloor = \left\lfloor \frac{x}{y} \right\rfloor$$

Any ideas?

John

Don't you also need x and y to be positive for this to work?

jaw088
Yes, x and y are both positive.

Even more specifically, in the application I'm using it, y >= 2.

Last edited:
exk
Well if you want to prove it's impossible you can try assuming it's possible and looking for a logical contradiction that arises.

I guess you could start by multiplying through by y and get $\left \lfloor \lfloor x \rfloor \rfloor} \right\rfloor < \left\lfloor x \right\rfloor$
Then since x is a positive integer you can say that floor(floor(x))=floor(x), this is true since floor(x) leaves the integral part and taking the floor of that is like taking the integral part of the integer leaving the integer.

beezey
I was thing that if you set
$$\left\lfloor\ x \right\rfloor+a=x$$

where $$0 \leq a < 1$$

then with substitution into

$$\left\lfloor \frac{\left\lfloor x \right\rfloor}{y} \right\rfloor= \left\lfloor \frac{x}{y} \right\rfloor$$

you would get

$$\left\lfloor \frac{\left\lfloor x \right\rfloor}{y} \right\rfloor= \left\lfloor \frac{\left\lfloor\ x \right\rfloor+a}{y} \right\rfloor$$

switch it up a bit

$$\left\lfloor \frac{\left\lfloor x \right\rfloor}{y} \right\rfloor= \left\lfloor \frac{\left\lfloor\ x \right\rfloor}{y} +\frac{a}{y}\right\rfloor$$

since a is bounded in the interval $$0 \leq a < 1$$ (by definition) than the the the second term $$\frac{a}{y}$$ will always be a smaller decimal than needed to raise the value of the floor function. basicly what i mean by that is
$$\left\lfloor \left\lfloor\ x \right\rfloor +a\right\rfloor - \left\lfloor\ x \right\rfloor \neq 1$$
because obviously
$$\left\lfloor \left\lfloor\ x \right\rfloor +a\right\rfloor - \left\lfloor\ x \right\rfloor = 0$$
the the second term will always be negligible in the equation so it can be removed giving you the equivalence. The proof seems pretty clearly stated to me except for the second to last step where i said you can phase out the second terms. I'm having a little trouble putting that step into words but intuitively i feel strongly that it works. it just needs someone more articulate than me to come along and fix it up. good luck.

Maybe some insight can be gained from considering why y needs to be an integer. If y is allowed to be a real number, we could pick some $0< \epsilon < a < 1$ and use $y = \lfloor x \rfloor + \epsilon$. Then, we have

$$\left\lfloor \frac{\left\lfloor x \right\rfloor}{y} \right\rfloor= \left\lfloor \frac{\left\lfloor x \right\rfloor}{\lfloor x \rfloor + \epsilon} \right\rfloor=0$$

but

$$\left\lfloor \frac{\left\lfloor\ x \right\rfloor+a}{y} \right\rfloor= \left\lfloor \frac{\left\lfloor x \right\rfloor+a}{\lfloor x \rfloor + \epsilon} \right\rfloor=1$$

So, assuming y is an integer, I'd break it into three cases: $y<\lfloor x \rfloor$, $,y=\lfloor x \rfloor$ and $y>\lfloor x \rfloor$. The second and third cases are easy to see, but what about the first case?

Last edited by a moderator: