Isn't $\lceil \frac{xy}{z}\rceil =\lfloor \frac{xy+y-1}{z}\rfloor$ for any positive integers $x,y,z$?

72 Views Asked by At

I was pretty sure that:

$$\left\lceil\frac{xy}{z}\right\rceil = \left\lfloor\frac{xy+y-1}{z}\right\rfloor$$

for positive integers $x,y,z$.

But I'm getting wrong results testing it in Python 3:

from math import ceil

x = 40000000000000000
y = 400000000000000070
z = 80000000000000014

print(ceil(x*y/z))  # 200000000000000000
print((x*y+y-1)//z) # 200000000000000004
#

Does anyone here have a clue where I've gone wrong?

1

There are 1 best solutions below

0
On

The formula is obviously false: for $z=1$ and $y\ne 1$ we have $xy \ne xy+y-1$.

As you a observed in a comment, the correct formula is $$\left\lceil\frac{xy}{z}\right\rceil = \left\lfloor\frac{x y+z-1}{z}\right\rfloor$$

for positive integers $x$, $y$ and $z$.

It can be proved as follows:

Call $n = \left\lceil\frac{xy}{z}\right\rceil$, then

$$n-1<\frac{xy}{z}\le n$$ $$n z-z<x y\le n z$$

Since $nz-z$ and $xy$ are integers, we have $$n z-z+1\le x y\le n z$$ $$nz \le xy+z-1 \le nz+z-1 < nz+z$$ $$n \le \frac{xy+z-1}{z} < n+1$$ so $$\left\lfloor\frac{x y+z-1}{z}\right\rfloor = n$$