does this equation hold for all positive integers
floor( z / (x*y) ) = floor( floor(z / x) / y )
if so, how to prove it?
i have already tested it on randomly generated numbers. also, i have previously used it in a problem and it worked fine
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
does this equation hold for all positive integers
floor( z / (x*y) ) = floor( floor(z / x) / y )
if so, how to prove it?
i have already tested it on randomly generated numbers. also, i have previously used it in a problem and it worked fine
Name |
---|
It's Wrong for Z=3.5 X=1 Y=3.5
floor(3.5/3.5)=floor(1)=1
floor(floor(3.5/1)/3.5)=floor(3/3.5)=0
1!=0
He meant for all positive integers :D
your right.I'm sorry.
I am not good at mathematics, but I think I got some idea about it. Instead of giving a rigorous proof. I will show some facts about floor.
The floor(a/b) returns r where a = r*b+c such that c < b
Now, about floor(z/(x*y) return r where z = r*(x*y)+c where c < (x*y)
This can be written as z = (r*x+p)*y+q where q = c-floor(c/y)*y. so p will always less then x too.
Now, going backward r = floor(floor(z/x)/y).
so simple :D thank you
it's easy to prove that
for any real x and integer a and b, a > 0.
thank you!
Here is my thought.
There are z bread items. To make one pizza we require exactly x bread items. And to satisfy a hungry person, he needs exactly y pizzas.
Then using z bread items, we can make floor(z/x) pizzas. Since each person needs y pizzas, we can satisfy floor(floor(z/x)/y).
Now, thinking other way, to satisfy p people, we need p * y pizzas, which means we need p * y * x bread items. So, with z bread items, p = floor(z / (y*x)) people can be satisfied.
very neat!
floor(z/(xy)) = p = total people satisfied
z = pxy + r = total bread items, r < xy,
z = pxy + (remaining_pizzas * x + remaining_breads)
but remaining_pizzas < y, otherwise we could satisfy one more people by using y pizzas from remaining pizzas (and contradicting our assumption that only p people were satisfied), also remaining_breads < x.
floor(z/x) = (py + remaining_pizzas)
Now,
floor(floor(z/x)/y) = py
to prove floor(floor(z/y)/x) = floor(z/(xy)), swap roles of x and y and write eqn as
z = pxy + (remaining_pizzas * y + remaining_breads)