Find the difference of ceiling functions

Question

For $k \geq 1, 1 \leq r \leq k, t \geq 1, x \geq 1$, is there a lower bound or upper bound on:

$$\left\lceil \dfrac{k(t+x)}{r} \right\rceil - \left\lceil \dfrac{k(t)}{r} \right\rceil$$

edit: all the variables $k,r,t,x$ are integers

Answer 1

We can find non-negative integer $p,q,v,w$ so that \begin{align*} kt&=pr+v\qquad 0\leq v<r\\ kx&=qr+w\qquad 0\leq w<r \end{align*}

We obtain \begin{align*} \color{blue}{\left\lceil\frac{k(t+x)}{r}\right\rceil-\left\lceil\frac{kt}{r}\right\rceil} &=\left\lceil\frac{pr+v+qr+w}{r}\right\rceil-\left\lceil\frac{pr+v}{r}\right\rceil\\ &=p+q+\left\lceil\frac{v+w}{r}\right\rceil-p-\left\lceil\frac{v}{r}\right\rceil\\ &=q+\left\lceil\frac{v+w}{r}\right\rceil-\left\lceil\frac{v}{r}\right\rceil\\ &\,\,\color{blue}{=\begin{cases} q&w=0\\ q+1&w>0,v=0\\ q&w>0,v>0,v+w\leq r\\ q+1&v+w>r \end{cases}} \end{align*}

Answer 2

Of course $0$ is a lower bound. There is no upper bound because increasing $x$ can make the difference as large as you want. We can improve the lower bound by noting that the lower bound has to be at $x=1$. We are then asking how low $$\left\lceil \dfrac{k(t+1)}{r} \right\rceil - \left\lceil \dfrac{k(t)}{r} \right\rceil=\left\lceil \dfrac{kt+k}{r} \right\rceil - \left\lceil \dfrac{k}{r} \right\rceil$$ can be. We know $\frac {kt}r \gt 1$ from the given conditions so the difference is at least $1$. We can make the difference $1$ if we want, so that is the greatest lower bound. An example would be $t=1.01,k=2.01,r=2$ Then we have $$\left\lceil \dfrac{kt+k}{r} \right\rceil - \left\lceil \dfrac{k}{r} \right\rceil=\left\lceil \dfrac{1.01\cdot 2.01+2.01}{2} \right\rceil - \left\lceil \dfrac{2.01}{2} \right\rceil=\left\lceil \frac {4.0401}2\right\rceil-\left\lceil \frac {2.01}2\right\rceil=3-2=1$$

Added: given that the variables are integers, we can still achieve a difference of $1$ as long as $x=1$ Just take $k=r,t=1$ and the first item is $2$ and the second is $1$.

Answer 3

The remainder theorem says that for any two positive integers, $q$ and $n$ you can divide $n$ by $q$ and get two unique integers $d$ and $s$ so that $n = dq + s$ and $0 \le s <q$.

So let $kt = Mr +s$ and let $kx = Nr + w$.

Then $\lceil \frac {k(t+x)}r \rceil = \lceil M + N + \frac {s+w}r\rceil= M + N + \lceil \frac {s+w}r\rceil $.

And $\lceil \frac {kt}r \rceil = \lceil M + \frac sr \rceil = M +\lceil \frac sr \rceil$.

And $\lceil \frac {k(t+x)}r \rceil-\lceil \frac {kt}r \rceil =N +\lceil \frac {s+w}r\rceil- \lceil \frac sr \rceil$

Because $0 \le s,w < r$ $0 \le \frac sr < 1$ and $0 \le \frac {s+w}r < 2$.

So $\lceil \frac sr \rceil = 0$ or $1$ and $\lceil \frac {s+w}r\rceil = 0, 1$ or $2$ and $\lceil \frac {k(t+x)}r \rceil-\lceil \frac {kt}r \rceil =N +\lceil \frac {s+w}r\rceil- \lceil \frac sr \rceil= N$ or $N+1$ or $N+2$.

There is no upper bound as we can make $N$ as large as wish by making $x$ as large as we wish.

We can make $N$ as low as $0$ by making $kx < r$ and $s+w < 1$

Example: Let $r = 5; k = 2$ and $t=3$.

We can get $\lceil \frac {k(t+x)}r \rceil-\lceil \frac {kt}r \rceil = 0$ by selection $kx = 2x < 5$ and REMAINDER $2x \div 5 < 4$. So... let $x = 1$ then

$\lceil \frac {k(t+x)}r \rceil-\lceil \frac {kt}r \rceil =$

$\lceil \frac {2(3+1)}5 \rceil-\lceil \frac {2\cdot3}5 \rceil =$

$\lceil \frac 85\rceil - \lceil \frac 65 \rceil = 2 - 2 = 0$.

And we want pick $N$ as large as we we want we can get $\lceil \frac {k(t+x)}r \rceil-\lceil \frac {kt}r \rceil \ge N$ by letting $\frac {kx}r \ge N$ i.e.$x \ge \frac {rN}k$.

So if $x = \frac 52 10^{1000}= 5^{1001}2^{999}$ we get:

$\lceil \frac {k(t+x)}r \rceil-\lceil \frac {kt}r \rceil=$

$\lceil \frac {2(3+5^{1001}2^{999})}5 \rceil-\lceil \frac {2\cdot3}5 \rceil=$

$\lceil \frac 65 + 10^{1000}\rceil - \lceil \frac 65 \rceil =$

$(10^{1000} + 2) - 2 = 10^{1000}$.