0
$\begingroup$

This is expanding on this question: Show that if $n$ and $k$ are positive integers, then $\lceil \frac{n}{k} \rceil = \lfloor \frac{n - 1}{k} \rfloor + 1$ as I'm unclear on how to solve this statement...

I'm not clear on the answer provided in the textbook, and I'm not able to solve it, this is how far I get: There are unique integer $b$ and real number $r$, with $0 \leq r \lt 1$ such that $\frac{n}{k} = b + r$, therefore $n = k(b+r)$, and $n-1 = k(b+r) -1$, so $\frac{n-1}{k} = b + r - \frac{1}{k}$

Case i) $\lceil \frac{n}{k} \rceil = b + r$ when $r = 0$

Then $b = \lfloor b + 0 - \frac{1}{k}\rfloor + 1$, since $b$ is an integer

$b = b + \lfloor -\frac{1}{k} \rfloor + 1$, since $k$ is an integer, definition of $\lfloor - \frac{1}{k} \rfloor = -1 $, therefore $b = b$

Case ii)$\lceil \frac{n}{k} \rceil =b +1$ when $0 \lt r \lt 1$

Then $b+1 = \lfloor b + r - \frac{1}{k}\rfloor + 1$, and this is where I get stuck. Since $b$ is an integer $b + 1 = b + \lfloor r - \frac{1}{k} \rfloor + 1$

$\endgroup$
1
$\begingroup$

Ok, I think I can apply the division algorithm in this fashion: If $n$ and $k$ are positive integers then there are unique integers $q$ and $r$, with $0 \leq r \lt k$, such that $n = kq + r$. Let $n - 1 = kq + r -1$ divide both equations by $k$ such that

$\frac{n}{k} = q + \frac{r}{k}$ and $\frac{n-1}{k} = q +\frac{r-1}{k}$

Case i) $r =0$ as per above. $q = q$

Case ii) $r \gt 0$

LHS: $\lceil \frac{n}{k}\rceil = \lceil q + \frac{r}{k}\rceil = q + 1$

RHS: $\lfloor \frac{n-1}{k}\rfloor + 1 = \lfloor q + \frac{r-1}{k}\rfloor + 1 = q + \lfloor \frac{r-1}{k}\rfloor + 1 = q + 0 + 1 = $LHS

Since r is greater than 0 and an integer it must be an integer between 1 and $k-1$, therefore $\lfloor \frac{r-1}{k} \rfloor$ will always evaluate to 0

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.