13
$\begingroup$

I had a heated discussion with my co-worker today, and was wondering if someone here could shed some light on this situation. The post is a bit lengthy, but I wanted to put all my intuition down in writing so you all only need to help as minimally as possible.


I live in a town called Mathelia, and every day I commute from my workplace at $x=0$ to my house at $x=1$. I've been starting my commute home at $t=0$, and this gets me home at $t=2$, since there's quite a bit of traffic.

My friend told me that the traffic lulls down over time, and if I were to leave after $t=0$, I might be able to commute a less amount of time. He's right, in fact, and if I leave at $t=1$, I end up at home at roughly $t=2.5$, saving $0.5$ time from my commute.

Theorem: I will never be able to arrive home before $t=2$.

Proof: Let's say that I arrive home at some time $t<2$. Then, at some point I would have coincided in position and time with the "ghost car" that left exactly at $t=0$. Since the position and time are the same, the time remaining for the rest of the journey must be the same, and thus I must arrive home at $t=2$.

My question is this: is it possible to leave at a time $t>0$ and still arrive home at $t=2$?


I make the following assumptions. Let's assume we have some traffic function $f(x,t) > 0$ which gives us the traffic $f$ (in miles/hour; $f$ really tells us the speed we can travel, with high $f$ being low traffic and vice versa) at every point $0 \leq x \leq 1$ and $0 \leq t$. We assume that $f$ is continuous and differentiable everywhere in this region.

My first thought was that if we allow $f(x,t) = 0$ for some $x$ and $t$, we could let $f(x,t) = 0$ for $t \leq 1$, and then have the $t > 1$ portion complete continuity and differentiability. This would mean that I would go literally nowhere for the first hour, at which point leaving at $t=1$ would make me coincident with the "ghost car" immediately.

But since $f(x,t) > 0$, I don't know how to approach this problem. I think there's something weird going on, because if we know that $f(x_1, t_1) = c$, this value of $c$ tells us which "path" we take on the surface $f$. If $c$ is large, we then have small increases in $t$ with large increases in $x$; if $c$ is small, we then have small increases in $x$ with large increases in $t$. This makes me feel like the entire system can be described by just one parameter: $t_0$, or when you start the journey.

I reason that everything from there should be deterministic: you know $x_0 = 0$ and $t_0$, so you know the initial value of $f$. Depending on $f$, the values for $x$ and $t$ change ($f$ will tell you the local value of $\frac{dx}{dt}$, I think), and you can work out a new value for $f$.

So, the question is are there multiple paths that intersect the state $x=1, t=2$?

I think there's maybe a system of ODEs I can write, but I don't know how to translate "given $f$, is there a path where $t_0 > 0 \text{ and } (x = 1, t = 2) \text{ is part of the solution curve}$" into actual mathematics.

This is about when I actually left work for my commute home, and I typed this up.


UPDATE

After thinking about this some more, I think what I'm modeling looks something like:

$$\frac{dx}{dt} = f(x,t), x(t_0)=0$$

As long as we know $f$ and $t_0$, we should be able to find the curve $x(t)$ which gives us our position at any time $t$. Then we need to find $t_f$ such that $x(t_f) = 1$.

The question then becomes: can we find multiple $t_0$ such that $t_f = 2$? Maybe someone well-versed can answer if this is ever possible, or how we might choose $f$ such that this is possible.

UPDATE #$2$

Let me make my question much more explicit without the background information.

I have a function $f(x,t)$ which gives you the speed you're allowed to travel at a position $x$ and a time $t$ ($0 \leq x \leq 1$, $0 \leq t$).

We know the following:

  • If you leave at $t = 0$ from $x = 0$, you will arrive at $x = 1$ at $t = 2$.
  • If you leave at $t = \delta$ from $x = 0$, you will never be able to arrive before $t = 2$.

The second bullet indicates that there might be some $\delta$ which allows you to arrive exactly at $t = 2$.

My question is how, given $f(x,t)$, can we determine whether or not such a $\delta$ exists?

Might it be true that for no $f(x,t)$ is this satisfied?

$\endgroup$
  • 3
    $\begingroup$ +1 for a real world word problem, and not something made up to demonstrate how to do mathematics $\endgroup$ – theREALyumdub Apr 27 '16 at 23:54
  • $\begingroup$ Interesting stuff. Maybe someone can mathematically quantify this. $\endgroup$ – Tyler Hilton Apr 28 '16 at 0:05
  • 2
    $\begingroup$ @theREALyumdub I find that the most interesting problems are the ones you think up randomly and don't immediately know how to solve. ;) $\endgroup$ – anonymouse Apr 28 '16 at 0:23
  • $\begingroup$ If there's a detour in the middle of you path to home and you decide whether to use it or not based on the given traffic at the time, it may very well be that your decision might not be globally optimal and starting at some $t>0$ might be better. $\endgroup$ – BigbearZzz Apr 28 '16 at 2:13
  • $\begingroup$ +1 Love a real problem for once! I used to live in Northern Virginia, so I personally spent a LOT of time sitting in a car thinking about just this problem. $\endgroup$ – user237392 Apr 28 '16 at 4:28
2
$\begingroup$

Let $\delta >0$ be the delay in your departure time from work. Also, we can model your remaining commute time $T$ as a function of the current time and your current position $(t,x_t): T(t,x_t)$. We will assume that $x_t$ is continuous (no teleportation allowed!) and monotonically increasing (no backtracking).

Your coworkers' conjecture (let's call it $H$) is that:

$$\exists \delta >0: \delta+T(\delta,0)<T(0,0)=2$$

This assumes that the two routes are independent (i.e., waiting to leave a little later lets you use an entirely different road). However, if we are using the same road, then $H$ implies a contradiction.

Let $x_t$ be the position of a car that leaves when $\delta=0$ and $y_t$ be the position of a car delayed by some $\delta>0$ such that $H$ is true (your two "shadow" cars). Then we get

$$ \delta+T(\delta,0)<T(0,0) \implies \exists t: x_t=y_t$$

This result is due to the fact that the paths $x_t,y_t$, are monotonically increasing and continuous:

Let $q=\delta+T(\delta,0)<2$

$$x_0=y_0=0, \;\;x_q=y_2=1 \implies \exists s\in [0,2]: x_s>y_s$$

Also, $$ \delta>0 \implies \exists s\in [0,2]: x_s<y_s$$

Taken together, we can see that:

$$\exists a,b\in [0,2]: y_a-x_a <0,\; y_b-x_b>0$$

The last step indicates that the function $z_t=y_t-x_t$ (which is continuous by virtue of $x_t,y_t$ being continuous) attains both positive and negative values over the domain $t\in[0,2]$.

By the Intermediate Value Theorem

$$\exists m\in[0,2]: z_m=0 \implies x_m=y_m$$

Now comes the contradiction:

$$x_m=y_m \implies T(m,x_m)=T(m,y_m) \implies x_{m+T(m,x_m)}=y_{m+T(m,y_m)}$$

In words, this says that if $x$ and $y$ ever meet, they will arrive home at the same time. Therefore, for all $\delta$ satisfying $H$, we have derived the following result:

$$\delta+T(\delta,0)=T(0,0) \;\forall \delta>0:H$$

This directly contradicts $H$, hence $\neg H$ is true:

$$\forall \delta>0 \;\;\delta+T(\delta,0)\geq T(0,0)$$

Paraphrasing Seinfeld, we could call this the No Secret Fast Lane Theorem ;-)


Existence of $\delta$ given $f(x,t)$

Let $f(x,t)$ be the speed function of position and time. Then we have:

$$x'=f(x,t)$$

This is a rather general differential equation. Not much more to be said until it gets made specific. Now, lets assume you can solve this differential equation to get $x(t;\delta)$. Then you need to verify the following:

$$ \exists (\delta,t)\in[0,2]: x(t;\delta)=x(t;0)$$

Again, without getting specific, we can't go much further. However, this is the general test for if such a $\delta$ exists given a general $f(x,t)$


Simple Traffic Model

The OP has provided a nice proof that smoothness of $x_t$ implies $\delta + T(\delta,0)>T(0,0)$. If we relax the smoothness requirement, we can achieve $\delta + T(\delta,0)=T(0,0)$ for some $\delta>0$. Below is a simple traffic model for a road starting at $x=0$ and ending at $x=1$.

Let $a>0,b \geq 1, c\leq a/b$

$$f(x,t)= \left\{ \begin{array}{lcc} a & x \leq ct \\ \\ a/b,& x>ct \\ \end{array} \right.$$

What is $T(t,x)$ here? It depends on the values of $a,b$ and $c$: Now, $b=1$ or $c<\frac{a}{b}$ will lead to scenarios where we never catch up, either because the traffic speed is constant, or because we will end up matching the ghost car' speed before we catch it.

Also, $a<c$ cannot happen by definition. Hence, we are left with the final case of $b>1,c=\frac{a}{b}$.

Case: $b>1,c=\frac{a}{b}$

If $x<ct$, then we we need to find how long it will take to hit the lower speed traffic (if ever), before we get home $(x=1)$:

$$x+a\Delta t_{x,t} = c(t+\Delta t_{x,t}) \implies \Delta t_{x,t} = \frac{ct-x}{a-c}$$

Our position at this point will be $x^*=x+a\Delta t_{x,t}$. If $x^*>1$, then $\Delta t_{x,t} = \frac{1-x}{a}$, so we can combine these requirements into:

$$\Delta t_{x,t}= \left\{ \begin{array}{lcc} \min\left\{\frac{1-x}{a}, \frac{ct-x}{a-c}\right\} & x \leq ct \\ \\ 0& x>ct \\ \end{array} \right.$$

Our remaining time will be:

$$T(t+\Delta t_{x,t},x^*)=\frac{1-x^*}{a/b}$$

Therefore, our total time is:

$$ T(t,x)=\Delta t_{x,t} + \frac{1-(x+a\Delta t_{x,t})}{a/b}$$

Lets calculate the arrival time for our ghost car:

$$T(0,0)=\frac{b}{a}$$

Now, the arrival time for our "delayed" car is:

$$\delta + T(\delta,0) = \delta+\min\left\{\frac{1}{a}, \frac{c\delta}{a-c}\right\}+\frac{1-a\min\left\{\frac{1}{a}, \frac{c\delta}{a-c}\right\}}{a/b}$$

Applying our assumptions, we get:

$$\delta + T(\delta,0) = \delta+\min\left\{\frac{1}{a}, \frac{\delta}{b-1}\right\}+\frac{1-a\min\left\{\frac{1}{a}, \frac{\delta}{b-1}\right\}}{a/b}$$ We need to demonstrate

$$\exists \delta>0: \delta + T(\delta,0) = \delta+\min\left\{\frac{1}{a}, \frac{\delta}{b-1}\right\}+\frac{1-a\min\left\{\frac{1}{a}, \frac{\delta}{b-1}\right\}}{a/b} = \frac{b}{a}$$

Scenario 1: $\frac{\delta}{b-1} > \frac{1}{a}$

$$T(\delta,0)=\delta+\frac{1}{a}+\frac{1-a\frac{1}{a}}{a/b} = \delta+\frac{1}{a}$$

Now

$$\frac{\delta}{b-1}>\frac{1}{a}\implies \delta > \frac{b-1}{a} \implies \delta + \frac{1}{a} > \frac{b}{a}$$

So, we can see that we will never meet up with other ghost car if $\delta > \frac{b-1}{a}$

Scenario 2: $\frac{\delta}{b-1} \leq \frac{1}{a}$

$$T(\delta,0)=\delta+\frac{\delta}{b-1}+\frac{1-a\frac{\delta}{b-1}}{a/b}=\frac{b}{a}$$

So, for $\delta \leq \frac{b-1}{a}$ we will catch up with the ghost car, provided that the ghost car is at the very end of the slow part of the traffic! (i.e, clear sailing behind the ghost car).

$\endgroup$
  • $\begingroup$ Thanks for the answer! Essentially you've shown that delaying your departure time will never let you arrive earlier; however, my question is really for which functions $f$ (or, what property does $f$ have) can it be at all possible for $\delta + T(\delta, 0) = T(0,0)$? I can definitely think of a function $f$ where no value $\delta$ works, so what I'm interested in is figuring out what properties $f$ must have for this solution to exist, or perhaps that a solution will never exist. $\endgroup$ – anonymouse Apr 28 '16 at 15:50
  • $\begingroup$ @SSS any $f$ that results in the two trajectories meeting at some point will result in this condition. There are an infinite number of them. $\endgroup$ – user237392 Apr 28 '16 at 15:52
  • 1
    $\begingroup$ @SSS one example: basically, you can work backwards from my equation $\delta + T(\delta, 0) = T(0,0)$: If $T(t,x_t)$ is a decreasing function of $t$ forall $x_t$, then you can catch up. $\endgroup$ – user237392 Apr 28 '16 at 16:02
  • 1
    $\begingroup$ @SSS to answer your question, if you know the speed function $f(x,t)$ this will allow you to derive $T(t,x_t)$ and you can decide. $\endgroup$ – user237392 Apr 28 '16 at 16:05
  • 1
    $\begingroup$ @SSS yep, now you just need to explain this stuff to your coworker ;-) $\endgroup$ – user237392 Apr 29 '16 at 15:56
0
$\begingroup$

You're over-thinking it. The time you arrive home on a given day, with given patterns for other cars, is a non-decreasing function of $t_0$, the time you leave work. The fact that it is non-decreasing follows from your "ghost car" argument. However there will be intervals which result in the same time. For example if you hit a red light, it doesn't matter whether you arrive just after it turned red or just before it turned green. You wind up in the same spot behind the light, and you will get home at the same time.

That said your speculation time would probably be better used in not thinking of this as a straight line "always following the same path" problem, but rather in thinking of it in terms of which route is best. Which makes the problem greatly more complicated. However the need for real time feedback from many paths that you are not currently on will suggest looking for a source of such data that other people are collecting. This in turn could lead you to the pragmatic approximation of installing Waze and following its directions.

Have good luck commuting!

$\endgroup$
  • $\begingroup$ I don't see why this is intuitively true: I can imagine a situation where I leave at $t=0$ and have quite a bit of traffic all the way through when I reach home at $t=2$, and another case where I leave at $t=1$ and have almost no traffic until I coincide with my "ghost car," hit the traffic that he would have hit, and now I arrive home at the same time. Why is this case mathematically not possible? And red lights introduce a discontinuity in our traffic function, but you make a fair point. $\endgroup$ – anonymouse Apr 28 '16 at 0:01
  • $\begingroup$ @SSS Initial conditions could be problematic. Although traffic is busy and is 'lulling' down doesn't the business both on how rapidly it lulls down and how busy it is lulling down from? Why not liken the situation to a bullet being shot through a liquid that is steadily getting less viscous (for unknown reasons!). If you know the rate of reduction of viscosity and the initial viscosity then you would have a better idea of how long it would take for the bullet to reach it's target. What we do know is that your velocity home would be less than that of the bullet. $\endgroup$ – user328032 Apr 28 '16 at 2:14
0
$\begingroup$

Define the distance from home, starting from time $t=t_0$, as $x_{t_0}(t)$. Then, for case 1, you have $x_{0}(0)=1$, and $x_{0}(2)=0$, and for case 2 you have $x_{1}(0)=1$ (and $x_{1}(1)=0$) and $x_{1}(2.5)=0$.

Now, $x'_{t_0}(t)\leq0$ should be obvious. So your distance function is a decreasing (not strictly decreasing) function of time. You also know, that if $x_{a}(t)=x_{b}(t)$, then $x'_{a}(t)=x'_{b}(t)$, because your speed only depends on your current position and time, not on when you started.

Now, define a new function, $d(t)=x_{0}(t)-x_{1}(t)$, the distance between two commuters, one starting at $t=0$ and one starting at $t=1$. From what we have already written, we know that $d(0)=0$, $d(1)=x_0(1)$ (which will be between 0 and 1), and $d(2.5)=0$.

We can calculate $d'(t)=x'_0(t)-x_1'(t)$, which could be positive or negative. However, if $d(t)=0$, then $d'(t)=0$, and so both commuters stay together if they meet. It is not possible for $d$ to change sign.

$\endgroup$
  • $\begingroup$ Thanks for the answer! Maybe I should make it more explicit: the $x_1(2.5)=0$ constraint isn't part of the problem, it's just an example showing that the commute time might go down if you leave later, such as well after rush hour. Essentially what you've said is that if my car and the "ghost car" meet, we'll arrive home at the same time. I agree with this result, but the question is really for which functions of $f$ is it even possible to catch up to the "ghost car"? $\endgroup$ – anonymouse Apr 28 '16 at 15:49
  • $\begingroup$ Any time you have a red light there is the opportunity, otherwise with a smooth velocity (in time and space) you can only get arbitrarily close. But velocity profiles are not "smooth", your two commuters can meet if one is stopped at a red light. For an explicit function $f$, I think you want something that is decreasing in $x$ more rapidly than it is growing in $t$. For a simple enough $f$ (such as maybe $\exp(-x/t)$ or maybe something else) you may even be able to solve for $d$. Interesting question! $\endgroup$ – David Apr 29 '16 at 9:24
0
$\begingroup$

In real life, you can never tie the ghost car, because cars on a road come in an order! As you travel down the road you might catch up to the ghost car, but since the ghost car started first it will always be ahead of or tied with you, which translates into being ahead in a one-lane road.

Setting that aside, we see in a real-life model there's a very easy way to catch the ghost car: if it ever stops. In fact, for every time gap there exists a function that allows you to tie, which can be very easily constructed by having the ghost car go half way, then stop and wait for you to catch up, and then you both continue.

But what you really want to know if how do you tell if there exists such a $\delta$ for $f(x,t)$ which is a much more difficult question. There are functions for which no such gap exists, any monotonic increasing (in both variables) function will work as the ghost car is always traveling faster than you are. In order to determine if you catch up, you need to find an $a,b$ such that $$\int_0^b f(x(t,0),t)dt=\int_a^b f(x(t,a),t)dt$$ these integrals tell you exactly where the two cars are at time $b$ when the delayed car started at time $a$. The function $x(t,s)$ tells you where you are at time $t$ if you started at time $s$ and can be found by integrating in a similar manner.

There is no way to abstractly answer the question of if such an equality holds, and I expect ad hoc methods would be necessary to answer a particular function, but this seems like a not intractable question if $x$ depends on $t$ in a nice way (which it should). Using computer evaluation and numerical approximation methods, finding such a pair $(a,b)$ shouldn't be too hard for the computer.

$\endgroup$
  • $\begingroup$ If you look at the answer I posted, we can make the strong(ish) statement that as long as $\frac{\partial f}{\partial x}$ is continuous, we can find no such $\delta$! If this condition is relaxed, I agree with you in thinking numerical approximation is the only real way to approach this. $\endgroup$ – anonymouse Apr 28 '16 at 20:20
  • $\begingroup$ @SSS Im pretty sure you're wrong. See my comment $\endgroup$ – Stella Biderman Apr 28 '16 at 20:25
0
$\begingroup$

We will never tie$^*$ the ghost car.

$^*$As long as $\frac{\partial f}{\partial x}$ is continuous.


$f(x,t)$ gives us the speed we can travel at the position $x$ and time $t$. We can then write the first-order differential equation:

$$\frac{dx}{dt} = f(x,t)$$

We have two curves that we care about: the ghost car, where the initial condition is $x(0) = 0$, and the comparison car, where the initial condition is $x(\delta) = 0$.

We know that if our comparison car intersects the ghost car at any point along its trajectory, the comparison car will then follow exactly the same path as the ghost car and arrive home at the same time.

Let's say that the comparison car and the ghost car intersect at $x = x_i, t = t_i$

Our differential equation then becomes:

$$\frac{dx}{dt} = f(x,t), \ x(t_i) = x_i$$

As long as $f(x,t)$ is continuous (given) and $\frac{\partial f}{\partial x}$ is continuous (assumed), our existence and uniqueness theorems hold for this first-order ODE.

Thus, there exists exactly one solution that obeys $f(x,t)$ and passes through the point $(t_i, x_i)$, namely the path of the ghost car.

Since we know previously that we cannot beat the ghost car, and now we have shown that there is no path intersecting the ghost car, we conclude that setting $x(\delta) = 0$ for $\delta > 0$ will result in us arriving home after the ghost car.


The ultimate conclusion is while leaving after rush hour might decrease your commute time, you will never arrive home before the ghost car.

$\endgroup$
  • $\begingroup$ I'm no expert at differential equations, but this is clearly wrong. For one thing, the function that is constant and equal to $0$ will allow this to occur. Secondly, you can have a function that smoothly hits $0$ so that it is $C^\infty$ and yet is zero outside of an open interval which provides more counter examples. Maybe you mean to say that the derivative is nonnegative? $\endgroup$ – Stella Biderman Apr 28 '16 at 20:23
  • $\begingroup$ The constraint is that $f(x,t) > 0$ for all $x$ and $t$. I didn't repeat that constraint in the answer, but it was posted in the OP. $\endgroup$ – anonymouse Apr 28 '16 at 20:26
  • $\begingroup$ Oh I missed that. Yes, in that case I agree you cannot catch up. $\endgroup$ – Stella Biderman Apr 28 '16 at 20:26
  • $\begingroup$ Just to double check, is the rest of my logic applied properly? $\endgroup$ – anonymouse Apr 28 '16 at 20:30
  • $\begingroup$ yes, that looks right to me, though you're missing a sentence or three where you use the fact that the derivative is nonnegative. $\endgroup$ – Stella Biderman Apr 28 '16 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.