fresher96's blog

question related to floor function
By fresher96, history, 9 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

it's easy to prove that for any real x and integer a and b, a > 0.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    very neat!

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    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)

    → Reply