Page 1 of 2 12 LastLast
Results 1 to 15 of 25

Math Help - The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

  1. #1
    Member
    Joined
    May 2009
    Posts
    146

    The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    n walkers  {A}_{i} start at the same time from X to Y with speeds {a}_{i}, i=1,2,...,n.\ {a}_{i}\neq{a}_{j}, if i\neq j. At the same time, a motorcyclist M starts at Y to carry them. The motorcyclist's speed is m and it can go forwards or backwards. However, the motorcycle can only carry only one walker at a time, although it can choose to drop the walker on it at any time. The motorcylist's goal is to find a plan that allows all the n walkers to arrive at Y at the same time (i.e., a feasible plan). The problem and some definitions are illustrated in the attachment.

    Now in case of n walkers, define B^{n+2}\in {\mathbb{R}}_{++}^{n+2} to be the set of feasible configurations (i.e., configurations for which a feasible plan exists). Then after a little thought we know B^{3}={\mathbb{R}}_{++}^{3}, B^{4}={\mathbb{R}}_{++}^{4}.

    Question 1: What is B^{5} ?
    Question 2: What is {B}^{n} ? ( n>5) (But I really doubt there exists a closed-form expression for {B}^{n} in terms of {a}_{i}, m, L and n! What do you think?)

    ------------------------------------------------------------------
    for the original problem (which asks you to find a feasible plan that takes least time) and some progresses made there please refer to http://www.mathhelpforum.com/math-he...es-182882.html
    Attached Thumbnails Attached Thumbnails The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)-illustration.jpg  
    Last edited by godelproof; June 18th 2011 at 03:49 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2009
    Posts
    146

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    The following 3 properties of B^{n+2} should be easy to prove:

    1) If (a1,a2,...,an,m,L) \in B^{n+2}, then(ra1,ra2,...,ran,rm,rL) \in B^{n+2}, for any r>0. (This means that B^{n+2} is homogenous of degree one. Hence we may fix one component of the configuration to 1)

    2) If (a1,a2,...,an,m,L) \in B^{n+2}, then(ra1,ra2,...,ran,rm,L) \in B^{n+2}, for any r>0. (So we can further fix one more component to 1)

    3) If (a1,a2,...,an,m,L) \in B^{n+2}, then (a1,a2,...,an,bm,L) \in B^{n+2}, for any b>1.

    -----------------------------------------------------------------
    and I suspect the following 2 are also corret (cannot prove them though):

    4) If (a1,a2,...,an,m,L) \in B^{n+2}, then (da1,a2,...,an,m,L) \in B^{n+2}, for some d<1, where we assume a1>ai, for i=2,3,...,n

    5) Any (a1,a2,...,an,m,L) \in {\mathbb{R}}_{++}^{n+2}, there exists k large enough such that (a1,a2,...,an,km,L) \in B^{n+2}.
    -------------------------------------------------------------------
    A B^{n+2} that satisfies 1)~5) may indeed be strange...

    --------------------------------------------------------------------
    Edit: 1) and 5) are added. Corrected (ra1,ra2,...,ran,m,L) in 2) for (ra1,ra2,...,ran,rm,L). "any d<1" in property 4) is changed to "some d<1"
    Last edited by godelproof; June 18th 2011 at 08:29 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Nov 2007
    From
    Trumbull Ct
    Posts
    904
    Thanks
    27

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    Hi godelproof,
    What do you say is the least time in hours to get the walkers over the finish line at the same time of day.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2009
    Posts
    146

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    Quote Originally Posted by bjhopper View Post
    Hi godelproof,
    What do you say is the least time in hours to get the walkers over the finish line at the same time of day.
    Hi, I believe I've discussed that in http://www.mathhelpforum.com/math-he...es-182882.html, at #10 there. This least time is given there as T_{min}. But that formular is correct only if m is large enough. And the general case? We don't know yet...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2009
    Posts
    146

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    Quote Originally Posted by godelproof View Post
    Question 1: What is B^{5} ?
    Question 2: What is {B}^{n} ? ( n>5) (But I really doubt there exists a closed-form expression for {B}^{n} in terms of {a}_{i}, m, L and n! What do you think?)
    I'll post my opinions for Q1. Check to see if there's any problem...
    -------------------------------------------------------------------
    Consider the configuration ({a}_{1},\ {a}_{2},\ {a}_{3},m,L). Without loss of generality, let {a}_{3}>{a}_{2}>{a}_{1}. Let {a}_{3}<m (otherwise no feasible plan exists).

    Conjecture: Let the motorcycle go straight to {A}_{1} and carry him forward to catch {A}_{2}. A feasible plan exists if and only if the motorcycle is able to catch {A}_{2} before or just when she reaches Y.

    Is the above conjecture true?

    If it is, then {\mathbb{B}}^{5} looks like this:
    {\mathbb{B}}^{5}={ ({a}_{1},{a}_{2},{a}_{3},m,L)|m>{a}_{3}>{a}_{2}>{a  }_{1},\ 2{a}_{2}\leq{a}_{1}+m}.

    An illustration is given below for m=10. For any m, just shift the the blue lines up or down.
    Attached Thumbnails Attached Thumbnails The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)-m-10.jpg  
    Last edited by godelproof; June 20th 2011 at 07:32 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    May 2009
    Posts
    146

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    Quote Originally Posted by bjhopper View Post
    Hi godelproof,
    What do you say is the least time in hours to get the walkers over the finish line at the same time of day.
    least time takes about 4.5 hours
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2009
    Posts
    146

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    and a question for you two too, Wilmer and BJH!

    True or false:

    If {A}_{1}, {A}_{2}, {A}_{3} and M all start out at X at the same time, then
    {a}_{1}<{a}_{2}<{a}_{3}<m \Longrightarrow a plan can be found to get the three walkers to Y simultaneously. (M can't carry a walker to a point before X)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,099
    Thanks
    67

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    TRUE; 179 fully integer cases (including pick-ups and drop-offs) keeping distance XY < 1000.

    Smallest case: XY = 132; m = 6, a = 1, b = 2, c = 3 ; total time = 42
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    May 2009
    Posts
    146

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    Quote Originally Posted by Wilmer View Post
    TRUE; 179 fully integer cases (including pick-ups and drop-offs) keeping distance XY < 1000.

    Smallest case: XY = 132; m = 6, a = 1, b = 2, c = 3 ; total time = 42
    No, that begs the question! For ANY a, b, c and m starting at X, as long as a<b<c<m, a plan exists:

    XY=7 m=10.5 a=1 b=2 c=10 plan exists
    XY=1 m=100.5 a=1 b=99 c=100 plan exists
    XY=3 m=3.14 a=3 b=3.1 c=3.11 plan exists
    ect...

    True or false?
    -----------------------------------------------------------------
    Interestingly, although you've only considered integer solutions, for any noninteger configuration and solutions, we can always multiply them by some large integer and transform it to a problem with integer solutions! (See property 1) in #2). What does this mean? It means the problem has a solution iff when you multiply its configuration by some large integer, it has an integer solution! Amazing!!!

    -----------------------------------------------------------------
    And here's a challenge for everybody:
    m=50, a=10, b=45, c=48, XY=whatever you like; a b c at X, m at Y
    Can you find a plan? (noninteger plans are allowable)

    (If you can find a plan for this, my conjecture in #5 would be incorrect)
    Last edited by godelproof; June 20th 2011 at 10:59 PM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Dec 2009
    From
    1111
    Posts
    872
    Thanks
    3

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    Quote Originally Posted by godelproof View Post
    I'll post my opinions for Q1. Check to see if there's any problem...
    -------------------------------------------------------------------
    Consider the configuration ({a}_{1},\ {a}_{2},\ {a}_{3},m,L). Without loss of generality, let {a}_{3}>{a}_{2}>{a}_{1}. Let {a}_{3}<m (otherwise no feasible plan exists).

    Conjecture: Let the motorcycle go straight to {A}_{1} and carry him forward to catch {A}_{2}. A feasible plan exists if and only if the motorcycle is able to catch {A}_{2} before or just when she reaches Y.

    If the motorcycle just catches A_2; by that time A3 has already finished the journey since, {a}_{2}<a_3

    Is the above conjecture true?

    If it is, then {\mathbb{B}}^{5} looks like this:
    {\mathbb{B}}^{5}={ ({a}_{1},{a}_{2},{a}_{3},m,L)|m>{a}_{3}>{a}_{2}>{a  }_{1},\ 2{a}_{2}\leq{a}_{1}+m}.

    An illustration is given below for m=10. For any m, just shift the the blue lines up or down.
    .
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    May 2009
    Posts
    146

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    Quote Originally Posted by Sudharaka View Post
    If the motorcycle just catches ; by that time A3 has already finished the journey since {a}_{2}<{a}_{3}
    Not true, my friend! On its way to meet {A}_{1}, M will meet {A}_{3} first. M then carry him backward for some distance, drop him somewhere before M meets {A}_{1}. And M then carries {A}_{1} to catch {A}_{2} at destination Y, while {A}_{3} just arrive there at the same time too! See the attachment!
    Attached Thumbnails Attached Thumbnails The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)-just-arrive.jpg  
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,099
    Thanks
    67

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    Quote Originally Posted by godelproof View Post
    No, that begs the question! For ANY a, b, c and m starting at X, as long as a<b<c<m, a plan exists:
    Didn't realise you meant "ANY"...
    So a case like a=1, b=2, c=9, m=10 (everybody at X) could be one of the "ANY"!
    Looks like possible this way (but not 100% sure):
    1: M carries A for u hours; A continues, M returns
    2: M meets C after v hours, then carries C back for w hours ; (u+v+w hours so far)
    3: M drops off C, picks up B and carries B for x hours; B continues, M returns
    4: M meets C after y hours, then carries C to Y taking z hours ; (u+v+w+x+y+z hours so far)
    5: A and B and C arrive at Y at same time
    I get a headache just thinking of it!!

    By the way, you posted your "challenge" as an "edit": so will only be seen if someone happens
    to be looking at the "edited" post.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    May 2009
    Posts
    146

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    Quote Originally Posted by Wilmer View Post
    Didn't realise you meant "ANY"...
    So a case like a=1, b=2, c=9, m=10 (everybody at X) could be one of the "ANY"!
    Looks like possible this way (but not 100% sure):
    1: M carries A for u hours; A continues, M returns
    2: M meets C after v hours, then carries C back for w hours ; (u+v+w hours so far)
    3: M drops off C, picks up B and carries B for x hours; B continues, M returns
    4: M meets C after y hours, then carries C to Y taking z hours ; (u+v+w+x+y+z hours so far)
    5: A and B and C arrive at Y at same time
    I get a headache just thinking of it!!

    By the way, you posted your "challenge" as an "edit": so will only be seen if someone happens
    to be looking at the "edited" post.
    Haha, I appologize! I didn't mean to make you headache~ It's true for ANY 0<a<b<c<m, I proved it. But I will not post the proof (So to save you from another headache).

    Why I ask you this? Because I can use this knowledge to prove my conjecture in #5. Now I've proved it to be true. But unless someone challenges me, I will not post the proof, either.

    As for my challenge question, the answer is you can't find a solution for any XY
    ---------------------------------------------------------------------------

    So we now know {B}^{5} is as stated in #5. What is {B}^{n} (n>5)? Well, perhaps that question just goes beyond my ability to answer... but would love to see someone come and work it out!

    -----------------------------------------------
    Edit: red letters
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Dec 2009
    From
    1111
    Posts
    872
    Thanks
    3

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    Quote Originally Posted by godelproof View Post
    Not true, my friend! On its way to meet {A}_{1}, M will meet {A}_{3} first. M then carry him backward for some distance, drop him somewhere before M meets {A}_{1}. And M then carries {A}_{1} to catch {A}_{2} at destination Y, while {A}_{3} just arrive there at the same time too! See the attachment!
    Yeah I see. Didn't thought about the case where M carrying the walker backwards.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member
    Joined
    Dec 2009
    From
    1111
    Posts
    872
    Thanks
    3

    Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)

    Quote Originally Posted by godelproof View Post
    Not true, my friend! On its way to meet {A}_{1}, M will meet {A}_{3} first. M then carry him backward for some distance, drop him somewhere before M meets {A}_{1}. And M then carries {A}_{1} to catch {A}_{2} at destination Y, while {A}_{3} just arrive there at the same time too! See the attachment!
    Hi godelproof,

    So the motorist will meet A3 and carry him backwards on his way to meet A1. This is a must; if not your conjecture is useless. Agreed? After that he will carry A1 forwards. Suppose he cannot meet A2, then obviously A2 will reach the destination Y before the motorist and A1. Is this the proof of your conjecture? By the way, how did you write, 2{a}_{2}\leq{a}_{1}+m ?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Special "Motorcyclist-walkers" case.
    Posted in the Advanced Math Topics Forum
    Replies: 12
    Last Post: June 29th 2011, 07:19 AM
  2. A general case of polynomial long division?
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: August 30th 2010, 03:58 PM
  3. Is there a method for finding the general solution in this case?
    Posted in the Differential Equations Forum
    Replies: 6
    Last Post: August 13th 2009, 12:59 AM
  4. HARD - derivation of general solution to K Backward Equation
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: April 3rd 2007, 06:30 AM

Search Tags


/mathhelpforum @mathhelpforum