Results 1 to 6 of 6

Math Help - Simplification Of Floor and Ceiling functions..

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    6

    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!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello eli_jordan
    Quote Originally Posted by eli_jordan View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2009
    Posts
    6
    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))
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Floor and ceiling functions

    Hello eli_jordan
    Quote Originally Posted by eli_jordan View Post
    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
    Last edited by Grandad; April 29th 2009 at 12:13 AM. Reason: Refinement to solution
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2009
    Posts
    6
    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?

    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello eli_jordan
    Quote Originally Posted by eli_jordan View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: April 18th 2011, 10:36 AM
  2. [SOLVED] Ceiling and Floor
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: November 14th 2010, 05:47 PM
  3. ceiling and floor functions
    Posted in the LaTeX Help Forum
    Replies: 1
    Last Post: October 21st 2010, 04:24 PM
  4. Floor and Ceiling stuff.
    Posted in the Calculus Forum
    Replies: 5
    Last Post: October 20th 2009, 03:42 PM
  5. Help with floor and ceiling functions
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 9th 2009, 10:30 PM

Search Tags


/mathhelpforum @mathhelpforum