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

  • Thread starter jaw088
  • Start date
  • #1
2
0

Main Question or Discussion Point

Hi,

I'm trying to proof that:
[tex]\left\lfloor \frac{\left\lfloor x \right\rfloor}{y} \right\rfloor= \left\lfloor \frac{x}{y} \right\rfloor[/tex] 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:

[tex] \lfloor x \rfloor \le x < \lfloor x \rfloor + 1[/tex]
[tex] \frac{\lfloor x \rfloor}{y} \le \frac{x}{y} < \lfloor \frac{x}{y} \rfloor + \frac{1}{y} [/tex]
[tex] \left\lfloor \frac{\lfloor x \rfloor}{y} \right\rfloor \le \left\lfloor \frac{x}{y} \right\rfloor [/tex]

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

Any ideas?

Thanks for your help,
John
 

Answers and Replies

  • #2
quadraphonics
Don't you also need x and y to be positive for this to work?
 
  • #3
2
0
Yes, x and y are both positive.

Sorry about that.

Even more specifically, in the application I'm using it, y >= 2.
 
Last edited:
  • #4
exk
119
0
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 [itex]
\left \lfloor \lfloor x \rfloor \rfloor} \right\rfloor < \left\lfloor x \right\rfloor
[/itex]
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.
 
  • #5
5
0
I was thing that if you set
[tex]\left\lfloor\ x \right\rfloor+a=x[/tex]

where [tex]0 \leq a < 1[/tex]

then with substitution into

[tex]\left\lfloor \frac{\left\lfloor x \right\rfloor}{y} \right\rfloor= \left\lfloor \frac{x}{y} \right\rfloor[/tex]

you would get

[tex]\left\lfloor \frac{\left\lfloor x \right\rfloor}{y} \right\rfloor= \left\lfloor \frac{\left\lfloor\ x \right\rfloor+a}{y} \right\rfloor[/tex]

switch it up a bit

[tex]\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[/tex]

since a is bounded in the interval [tex]0 \leq a < 1[/tex] (by definition) than the the the second term [tex]\frac{a}{y}[/tex] will always be a smaller decimal than needed to raise the value of the floor function. basicly what i mean by that is
[tex]\left\lfloor \left\lfloor\ x \right\rfloor +a\right\rfloor - \left\lfloor\ x \right\rfloor \neq 1[/tex]
because obviously
[tex]\left\lfloor \left\lfloor\ x \right\rfloor +a\right\rfloor - \left\lfloor\ x \right\rfloor = 0[/tex]
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
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 [itex]0< \epsilon < a < 1[/itex] and use [itex]y = \lfloor x \rfloor + \epsilon[/itex]. Then, we have

[tex]\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[/tex]

but

[tex]\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[/tex]

So, assuming y is an integer, I'd break it into three cases: [itex]y<\lfloor x \rfloor[/itex], [itex],y=\lfloor x \rfloor[/itex] and [itex]y>\lfloor x \rfloor[/itex]. The second and third cases are easy to see, but what about the first case?
 
Last edited by a moderator:

Related Threads for: Floor(x)/y = floor(x/y), y in Z

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
1
Views
2K
Replies
4
Views
603
Replies
10
Views
6K
Replies
4
Views
3K
  • Last Post
Replies
4
Views
3K
Replies
5
Views
791
Top