Is Floor(x)/y Always Equal to Floor(x/y) When y Is an Integer?

[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?

Thanks for your help,
John

 

[quadraphonics]

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

 

[jaw088]

Yes, x and y are both positive.

Sorry about that.

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

 

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

There is your contradiction, proving that the two statements are equal.

 

[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. basically 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.

 

[quadraphonics]

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?