3
$\begingroup$

Suppose x,y $ \in \mathbb{Z}^+ $

Prove $\lceil x/y \rceil = \lfloor (x-1)/y \rfloor + 1$

I was considering using the definition of floor and ceiling to prove this. But this does not seem like a valid proof to me as I assume the right hand side is already equal to the left hand side.

This is what I have so far:

Let n$ \in \mathbb{Z} $

$\lceil x/y \rceil = n \iff n-1 < x/y \leq n $

$\lfloor (x-1)/y \rfloor = n -1 \iff n-1 \leq (x-1)/y < n $
Then $\lfloor (x-1)/y \rfloor +1 = n \iff n-1 \leq (x-1)/y < n + 1 $

Then both sides are equivalent.

Would a better way be to prove using a contradiction by assuming both sides are not equal?

$\endgroup$
  • $\begingroup$ What does $n$ have to do with all this? $\endgroup$ – barak manos Nov 30 '14 at 9:31
  • $\begingroup$ n is the result of the floor and ceiling function. eg. $ \lceil 5/2\rceil = 3 $ So n = 3. $\endgroup$ – onesevenfour Nov 30 '14 at 9:32
  • $\begingroup$ I don't see it anywhere in the statement to prove. $\endgroup$ – barak manos Nov 30 '14 at 9:33
  • $\begingroup$ I guess I should put it in my proof part. edited. $\endgroup$ – onesevenfour Nov 30 '14 at 9:34
3
$\begingroup$

If $y$ divides $x$ then:

  • $\lceil\frac{x}{y}\rceil=\frac{x}{y}$
  • $\lfloor\frac{x-1}{y}\rfloor=\frac{x}{y}-1$

Hence $\lceil\frac{x}{y}\rceil=\lfloor\frac{x-1}{y}\rfloor+1$


If $y$ does not divide $x$ then:

  • $\lceil\frac{x}{y}\rceil=\lfloor\frac{x}{y}\rfloor+1$
  • $\lfloor\frac{x-1}{y}\rfloor=\lfloor\frac{x}{y}\rfloor$

Hence $\lceil\frac{x}{y}\rceil=\lfloor\frac{x-1}{y}\rfloor+1$

$\endgroup$
  • $\begingroup$ I'm confused as to how you obtained the y does not x case. Did you use the definition of floor and ceiling? Also, wouldn't any positive integer divide another positive integer? $\endgroup$ – onesevenfour Nov 30 '14 at 9:50
  • $\begingroup$ @onesevenfour: 1. There are two statements there, which one are you confused about? 2. When I say "divide", I mean "divide without a remainder" (what else could it mean? the only number that does not divide other numbers is $0$). $\endgroup$ – barak manos Nov 30 '14 at 9:52
1
$\begingroup$

starting from line 2, the inequality can be rewritten as

\begin{equation*} n-1+1/y \leq x/y < n+1/y \end{equation*} since x,y are integers, the left inequality is equivalent to

\begin{equation*} n-1 < x/y \end{equation*}

and the right inequality is equivalent to \begin{equation*} x/y \leq n \end{equation*}

$\endgroup$
  • $\begingroup$ I get this proof, but does the case $\lfloor (x-1)/y \rfloor \neq n -1$ need to be considered? $\endgroup$ – onesevenfour Nov 30 '14 at 9:54
  • $\begingroup$ I edited it to be more clear. this shows that the right hand sides of the first two lines are equivalent. therefore the left hand sides are as well $\endgroup$ – Dunham Nov 30 '14 at 10:14
1
$\begingroup$

I might want to use a property of integer arithmetic $a \lt b \iff a+1 \le b$, as in:

$\qquad\;\;\lceil x/y \rceil = n $

$ \iff n-1 \lt x/y \leq n $

$ \iff (n-1)y \lt x \leq ny $

$\iff (n-1)y \le x-1 \lt ny$

$\iff n-1 \le (x-1)/y \lt n $

$\iff \lfloor(x-1)/y\rfloor =n-1$

$\iff \lfloor(x-1)/y\rfloor +1=n$

so $\lceil x/y \rceil = \lfloor(x-1)/y\rfloor$ + 1

$\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.