# Thread: Simplification Of Floor and Ceiling functions..

1. ## Simplification Of Floor and Ceiling functions..

Not sure if this is the right place to post, but here goes...

We have been asked to deduce an expression given certain constraints. Now I have deduced a correct expression (i believe) but have been unable to reduce it to the required expression, due to my in experience with the floor and ceiling functions.

My expression for M (given n):
let,
s = floor(sqrt(n))
A = (n - s(s-1) - s) / s

then,
M = 2s + ceiling(A)

The required expression for M:
M = ceiling(2*squrt(n))

any help would be greatly appreciated!!

2. Hello eli_jordan
Originally Posted by eli_jordan
Not sure if this is the right place to post, but here goes...

We have been asked to deduce an expression given certain constraints. Now I have deduced a correct expression (i believe) but have been unable to reduce it to the required expression, due to my in experience with the floor and ceiling functions.

My expression for M (given n):
let,
s = floor(sqrt(n))
A = (n - s(s-1) - s) / s ??

then,
M = 2s + ceiling(A)

The required expression for M:
M = ceiling(2*squrt(n))

any help would be greatly appreciated!!
Are you sure you have this right? The expression you have for $A$ simplifies to

$A = \frac{n-s^2}{s}= 1 - \frac{s}{n}$

Then, $n = 3 \Rightarrow s = 1, A = \tfrac23, M=2s +\lceil{A}\rceil = 3$, but $M = \lceil\,2\sqrt{n}\,\rceil = 4$

So the two expressions you have for $M$ give different values for $n = 3$.

3. thanks for that observation... seems i had it wrong. so, i'll paraphrase the question... in hope of some hints/help :-)

so basically we are a point on a number line, with a velocity. initially both velocity and position are zero... the number line is of length n. in each move we can either increase our velocity by one, decrease it by one, or remain the same... then move that many steps along the line. The aim is to reach the end (n steps) in the minimum number of moves, with a velocity of zero at the end. So for example if n=7, then the sequence of moves is [++0-0-].

we have to show that the minimum number of moves is
M = ceiling(2*sqrt(n))

4. ## Floor and ceiling functions

Hello eli_jordan
Originally Posted by eli_jordan
thanks for that observation... seems i had it wrong. so, i'll paraphrase the question... in hope of some hints/help :-)

so basically we are a point on a number line, with a velocity. initially both velocity and position are zero... the number line is of length n. in each move we can either increase our velocity by one, decrease it by one, or remain the same... then move that many steps along the line. The aim is to reach the end (n steps) in the minimum number of moves, with a velocity of zero at the end. So for example if n=7, then the sequence of moves is [++0-0-].

we have to show that the minimum number of moves is
M = ceiling(2*sqrt(n))
Here's the outline of the proof:

(1) If the maximum velocity achieved is $v$, the minimum number of steps required to achieve this and return to zero is $2v$.

(2) Thus the minimum distance moved is $1 + 2 + ... + v + (v-1) + (v-2) + ... + 1 = v^2$.

(3) If $n = m^2, m \in \mathbb{N}$, then $v = m$ and thus the minimum number of steps is $2m = 2\sqrt{n}$.

(4) If $n = m^2 + k, 0< k \le m$, then $v = m$ and the number of steps required is $2m+1$.

(5) If $n = m^2 + k, m< k \le 2m$, then $v = m$ and the number of steps required is $2m+2$.

(6) Then use $(m+\tfrac12)^2 = m^2 + m + \tfrac14$ to show that in (4) $2m + 1 = \lceil\,2\sqrt{n}\,\rceil$ and in (5) $2m + 2 = \lceil\,2\sqrt{n}\,\rceil$

Can you fill in the gaps?

5. thanks alot for that... your a smart guy!

i sat down again today trying to figure it out... and actually did get to the expressions you have at 4 and 5... but my path was slightly different... I thought i was wrong, because i couldnt reduce it to the required formula...

i did find a couple of identities that i thought would help.. and from what you have said it seems they would, but I still cant get step six out... the identities if found are in the pic below...

also... just another very quick question, are the two following expressions equivalent?

6. Hello eli_jordan
Originally Posted by eli_jordan
thanks alot for that... your a smart guy!

i sat down again today trying to figure it out... and actually did get to the expressions you have at 4 and 5... but my path was slightly different... I thought i was wrong, because i couldnt reduce it to the required formula...

i did find a couple of identities that i thought would help.. and from what you have said it seems they would, but I still cant get step six out... the identities if found are in the pic below...

(6) $0

$\Rightarrow m^2

$\Rightarrow m<\sqrt{n}

$\Rightarrow 2m<2\sqrt{n}<2m+1$

$\Rightarrow \lceil\,2\sqrt{n}\,\rceil = 2m+1$

Similarly, $k>m\Rightarrow m^2 + k > m^2+m+\tfrac14=(m+\tfrac12)^2$, since $k \in \mathbb{N}$

... etc

In the identities you have found, it looks very much as though you can replace $s$ by $m$, and get the same result.

also... just another very quick question, are the two following expressions equivalent?

No, since $E2=\lceil2\sqrt{2x-n}\rceil+E1$