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

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Jun 18th 2011, 03:34 AM
godelproof
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
• Jun 18th 2011, 04:05 AM
godelproof
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"
• Jun 18th 2011, 06:45 AM
bjhopper
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.
• Jun 18th 2011, 07:10 AM
godelproof
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by bjhopper
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...
• Jun 19th 2011, 07:59 PM
godelproof
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by godelproof
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} (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.
• Jun 19th 2011, 09:56 PM
godelproof
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by bjhopper
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
• Jun 19th 2011, 11:29 PM
godelproof
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} $\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)
• Jun 20th 2011, 01:23 PM
Wilmer
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
• Jun 20th 2011, 05:48 PM
godelproof
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by Wilmer
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)
• Jun 21st 2011, 12:24 AM
Sudharaka
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by godelproof
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} (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}

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.

.
• Jun 21st 2011, 01:35 AM
godelproof
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by Sudharaka
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!(Cool) See the attachment!
• Jun 21st 2011, 06:42 AM
Wilmer
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by godelproof
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.
• Jun 21st 2011, 08:00 AM
godelproof
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by Wilmer
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(Giggle)).

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

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!(Nod)

-----------------------------------------------
Edit: red letters
• Jun 21st 2011, 06:02 PM
Sudharaka
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by godelproof
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!(Cool) See the attachment!

Yeah I see. Didn't thought about the case where M carrying the walker backwards. (Giggle)
• Jun 23rd 2011, 08:34 AM
Sudharaka
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by godelproof
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!(Cool) 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$ ?
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last