Simplification Of Floor and Ceiling functions..

**eli_jordan** · April 27th 2009, 10:29 PM

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!!

**Grandad** · April 28th 2009, 03:04 AM

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

Grandad

**eli_jordan** · April 28th 2009, 05:39 AM

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))

**Grandad** · April 29th 2009, 12:02 AM

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?

Grandad

**eli_jordan** · April 29th 2009, 12:52 AM

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?

**Grandad** · April 29th 2009, 04:39 AM

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<k \le m \Rightarrow m^2 + k < m^2+m +\tfrac14=(m+\tfrac12)^2$

$\Rightarrow m^2<n< (m+\tfrac12)^2$

$\Rightarrow m<\sqrt{n}<m+\tfrac12$

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

Grandad

Thread: Simplification Of Floor and Ceiling functions..

LinkBack

Thread Tools

Display

Simplification Of Floor and Ceiling functions..

Floor and ceiling functions

Similar Math Help Forum Discussions

unusual integral involving ceiling and floor functions

[SOLVED] Ceiling and Floor

ceiling and floor functions

Floor and Ceiling stuff.

Help with floor and ceiling functions

Search Tags