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

Printable View

Show 40 post(s) from this thread on one page
Page 2 of 2 First 12
• Jun 25th 2011, 12:42 AM
godelproof
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by Sudharaka
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?

By the way, how did you write, $\displaystyle 2{a}_{2}\leq{a}_{1}+m$?

Hi Sudharaka my friend!

If m is very large, it can ignore A3 and first carry A1 forwards, drop him before A2 and A3, then turn back to catch A2 and carry A2 forwards, and drop him before A3 but behind A1, and turn back to carry A3 to Y when A1 and A2 just arrive at Y, too. So it is NOT A MUST that motorist first carries A3 backwards on his way to meet A1. What the conjecture asserts, is this: A feasible plan (whether M carries A3 backwards or not) exists $\displaystyle \Longleftrightarrow$ the speeds of A1, A2 and M are such that if M goes straight to A1 and pick A1 up to catch A2, he's able to catch A2 before or just when A2 arrives at Y $\displaystyle \Longleftrightarrow$ $\displaystyle 2{a}_{2}\leq{a}_{1}+m$. (So speed of A3 is irrelevant)

Quote:

Originally Posted by Sudharaka
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?

No. There you just showed that this particular plan won't work. Consider another plan: the motorist meet and carry A3 backwards and drop him a little behind A2, go forwards to pick up A2 and carry him backwards a little behind A3, and go forwards to pick up A3 and carry him a little behind A2, so on and so forth, meanwhile expecting A1 to catch up? Is this and countless other plans feasible, iff the red lettered plan in quotation is feasible? This is what the conjecture asserts!

Anyway I've proved it. The argument is long and involves many subtleties (for example, one is if you can catch A2 before he reaches Y as the conjecture requires, how do you know you can then make the three arrive at Y simultaneously?).

For cases involving 4 and more people, I have made no progress. I guess either they ARE indeed too complicated to handle, or require some really deep insights.
• Jun 25th 2011, 01:23 AM
Sudharaka
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by godelproof
Hi Sudharaka my friend!

If m is very large, it can ignore A3 and first carry A1 forwards, drop him before A2 and A3, then turn back to catch A2 and carry A2 forwards, and drop him before A3 but behind A1, and turn back to carry A3 to Y when A1 and A2 just arrive at Y, too. So it is NOT A MUST that motorist first carries A3 backwards on his way to meet A1. What the conjecture asserts, is this: A feasible plan (whether M carries A3 backwards or not) exists $\displaystyle \Longleftrightarrow$ the speeds of A1, A2 and M are such that if M goes straight to A1 and pick A1 up to catch A2, he's able to catch A2 before or just when A2 arrives at Y $\displaystyle \Longleftrightarrow$ $\displaystyle 2{a}_{2}\leq{a}_{1}+m$. (So speed of A3 is irrelevant)

No. There you just showed that this particular plan won't work. Consider another plan: the motorist meet and carry A3 backwards and drop him a little behind A2, go forwards to pick up A2 and carry him backwards a little behind A3, and go forwards to pick up A3 and carry him a little behind A2, so on and so forth, meanwhile expecting A1 to catch up? Is this and countless other plans feasible, iff the red lettered plan in quotation is feasible? This is what the conjecture asserts!

Anyway I've proved it. The argument is long and involves many subtleties (for example, one is if you can catch A2 before he reaches Y as the conjecture requires, how do you know you can then make the three arrive at Y simultaneously?).

For cases involving 4 and more people, I have made no progress. I guess either they ARE indeed too complicated to handle, or require some really deep insights.

Yeah I understand all you have explained. It seems that the problem is far more complicated and has many possibilities than I have thought. There is another question that I like to know. How do you know that your conjecture is the only constraint that this system has to follow. Maybe for the existence of a feasibility plan there need to be other constraints also.
• Jun 25th 2011, 04:20 AM
godelproof
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by Sudharaka
Yeah I understand all you have explained. It seems that the problem is far more complicated and has many possibilities than I have thought. There is another question that I like to know. How do you know that your conjecture is the only constraint that this system has to follow. Maybe for the existence of a feasibility plan there need to be other constraints also.

Ok, I think what you wanted me to show is this: $\displaystyle 2{a}_{2}\leq{a}_{1}+m$, $\displaystyle m>{a}_{3}>{a}_{2}>{a}_{1}$ $\displaystyle \Longrightarrow$ configuration $\displaystyle ({a}_{1}, {a}_{2}, {a}_{3}, m, L)$ is feasible. Where no other constraints are required, right? (the constraint $\displaystyle m>{a}_{3}$ is trivial, otherwise no feasible solution can possibly exist. Think about it for a moment and you should understand why).
----------------------------------------------------------------------
Lemma 1: Let XY=L. If $\displaystyle m>{a}_{3}>{a}_{2}>{a}_{1}$ are such that if M goes straight to A1 and carry him to catch A2 before (just when) A2 arrives at Y, then $\displaystyle 2{a}_{2}<(=){a}_{1}+m$. The converse is also true.

Proof: The algebraic is easy and straightforward. L cancels out in the end.

Lemma 2: Let XY=L. If A1, A2, A3 and M all start at X simultaneously, $\displaystyle m>{a}_{3}>{a}_{2}>{a}_{1}$, then a plan exists for M to guarantee A1, A2 and A3 arrive at Y simultaneously, for any $\displaystyle L>0$.

(Prove for this is long and tedious hence I will not post it. Think about it for a moment and you should be able to convince yourself it's correct!(Nod))
------------------------------------------------------------------------------

Now a proof for the red lettered statement.

Proof: (1) If $\displaystyle 2{a}_{2}={a}_{1}+m$, then by lemma 1 M carries A1 and catches A2 just at Y. If on its way to A1, M had left A3 alone, then A3 would have walked pass Y by now (because $\displaystyle {a}_{3}>{a}_{2}$); on the other hand, if on its way to A1, M had carried A3 and dropped him when it picked up A1, then A3 wouldn't have arrived at Y by now (because $\displaystyle {a}_{3}<m$). So there must be a point where M can drop A3 on its way to A1 so that A3 arrives at Y exactly the moment A2 and M(A1) arrive at Y (i.e., "by now").

(2) If $\displaystyle 2{a}_{2}<{a}_{1}+m$, then by lemma 1 M carries A1 and catches A2 before Y. Let this point be Z. Then same argument as in (1) with Y replaced by Z shows there must be a point where M can drop A3 on its way to A1 so that A3 arrives at Z exactly the moment A2 and M(A1) arrive at Z. Now the three walkers can arrive at Y simultaneously by lemma 2. Q.E.D.
• Jun 25th 2011, 06:04 AM
Wilmer
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by godelproof
and a question for you two too, Wilmer and BJH!
True or false:
If $\displaystyle {A}_{1}, {A}_{2}, {A}_{3}$ and M all start out at X at the same time, then
$\displaystyle {a}_{1}<{a}_{2}<{a}_{3}<m$ $\displaystyle \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)

Concerning this: (M can't carry a walker to a point before X)

BUT BUT if this happens to be the case in some scenario, then all you need to do
is have M go back and forth (forward 1 hour, backward 1 hour) until sufficient time
has elapsed.

Say M=10 and is 10 East of X with C; say for C to end up at Y at same time as A and B,
C needs to be backed up by M for 3 hours, thus "behind X" by 20.
Then M can "waste" these 3 hours by going back 10, forward 10, back 10...
Get my point?
• Jun 25th 2011, 07:15 AM
godelproof
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Well, let me show the other side of the argument as well, i.e., let me show that:
Given $\displaystyle m>{a}_{3}>{a}_{2}>{a}_{1}$. Configuration $\displaystyle ({a}_{1}, {a}_{2}, {a}_{3}, m, L)$ is feasible $\displaystyle \Longrightarrow$ $\displaystyle 2{a}_{2}\leq{a}_{1}+m$.

Proof: I prove it by contradiction. Suppose $\displaystyle 2{a}_{2}>{a}_{1}+m$. Let $\displaystyle {t}_{1}=\frac{L}{m+{a}_{1}}$. Clearly, it takes M at least $\displaystyle {t}_{1}$ to meet A1. But in any feasible plan, M must meet A1 (otherwise A1 will always fall behind A2 and A3). By argument in #18 then, M must carry A2 backwards some distance before M meets A1 (because it takes M at least $\displaystyle {t}_{1}$ to meet A1. If M didn't carry A2 backwards before M meets A1, A2 would have advanced to some point where M can never catch him when M meets A1).

Let $\displaystyle {t}_{2}=\frac{L}{{a}_{2}+m}$ and Z be the point $\displaystyle {a}_{2}{t}_{2}$ away from X. Let $\displaystyle {L}_{12}=({a}_{2}-{a}_{1}){t}_{2}$. By the above analysis, (1) distance between A1 and A2 must be less than $\displaystyle {L}_{12}$ when M drops A2 on it and goes for A1. But don't forget that A3 is even faster than A2! So (2) distance between A1 and A3 must be less than $\displaystyle {L}_{12}$ when M drops A3 and goes for A1, too! But if $\displaystyle 2{a}_{2}>{a}_{1}+m$, then we can show (1) and (2) can't be satisfied at the same time! (Consider M carries A3 back and meets A2; carries A3 behind A2 a little, then goes forwards to catch A2 and carries A2 back to meet A3 again. Some tedious but straightforward algebraic shows now distance between A1 and A2(A3,M) will be even larger than $\displaystyle {L}_{12}$, if $\displaystyle 2{a}_{2}>{a}_{1}+m$. See the solved problem here http://www.mathhelpforum.com/math-he...on-183369.html ). So a feasible plan must be impossible. Q.E.D.
• Jun 25th 2011, 07:35 AM
godelproof
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by Wilmer
Concerning this: (M can't carry a walker to a point before X)

BUT BUT if this happens to be the case in some scenario, then all you need to do
is have M go back and forth (forward 1 hour, backward 1 hour) until sufficient time
has elapsed.

Say M=10 and is 10 East of X with C; say for C to end up at Y at same time as A and B,
C needs to be backed up by M for 3 hours, thus "behind X" by 20.
Then M can "waste" these 3 hours by going back 10, forward 10, back 10...
Get my point?

In your example, if a walker is allowed to be carried west of X, then when 3 hours have passed both M and C are at a point 20 west of X. On the other hand, if M just "waste" those three hours by going back and forth, then when 3 hours have passed both M and C are just at X. They are not equivilent.
• Jun 26th 2011, 05:18 AM
Wilmer
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Ya...bad example...but you get the point, right?
If C is placed such that he'll get to Y before A and B,
say 3 hours before, then C can simply "stop" for 3 hours.
If the problem states that C cannot "stop", then the
same result can be accomplished by "wasting" the 3 hours.
• Jun 26th 2011, 05:59 AM
godelproof
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by Wilmer
Ya...bad example...but you get the point, right?
If C is placed such that he'll get to Y before A and B,
say 3 hours before, then C can simply "stop" for 3 hours.
If the problem states that C cannot "stop", then the
same result can be accomplished by "wasting" the 3 hours.

Of course: C can always "stop" with the help of M.
But while C "stops" this way, M can't go anywhere. On the other hand, if the problem states C can voluntarily stop, then M can go anywhere or even pick up other walkers while C stops. These cases are still different.
• Jun 26th 2011, 06:12 AM
Wilmer
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by godelproof
Of course: C can always "stop" with the help of M.
But while C "stops" this way, M can't go anywhere. On the other hand, if the problem states C can voluntarily stop, then M can go anywhere or even pick up other walkers while C stops. These cases are still different.

Boy, you're good at "finding if's!".
I originally stated that the position everybody is in is the situation
where MINIMUM time exists, so M not needed any more!
• Jun 26th 2011, 07:12 AM
godelproof
Re: The motorcyclist's problem reformed: feasibility in the general case (Hard!!!)
Quote:

Originally Posted by Wilmer
Boy, you're good at "finding if's!".
I originally stated that the position everybody is in is the situation
where MINIMUM time exists, so M not needed any more!

What i meant by "with the help of M" is that when C "stops", he needs M to be there with him carrying him back and forth.
Show 40 post(s) from this thread on one page
Page 2 of 2 First 12