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

1. Apr 26, 2008

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

2. Apr 27, 2008

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

3. Apr 27, 2008

### jaw088

Yes, x and y are both positive.

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

Last edited: Apr 27, 2008
4. Apr 27, 2008

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

5. May 4, 2008

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

6. May 4, 2008

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$$
$$\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?