Every morning, Herbosquon II walks 3 miles to school. He lives in Kansas, so we don't have to worry about silly obstructions and buildings - Herbosquon walks straight from point A (his house) to point B (Dennis Rodman's School for Unfortunately Named Children). However, Herbosquon has a problem. 50% of the time, when he goes on his walk, there is an invisible wall at a random point between his house and the school extending for a mile in both directions, perpendicular to his path.
Herbosqon's no dummy - he knows walking straight and having to take a 2-mile detour half the time can't be the most efficient way to do things. What is the best strategy for him to take to minimize his walking distance?
Well, let's simplify our problem a bit. We're looking at a path between two points, $A$ and $B$.
Instead of considering paths between $A$ and $B$, let's consider an equivalent problem: Set the $x$-axis as the line intersecting $A$ and $B$, and set $A$ as the origin. Basically, just rotating the whole problem until the points above are at the same height and shifting it until $A$ is at $(0,0)$. And, consider that any solution to this problem will be totally symmetric - i.e., it will not cross the $x$-axis multiple times (because that would be inefficient) and if we have a solution path in quadrant $1$ we can just reflect it for one in quadrant $4$.
So, now we're just looking at a path between $(0,0)$ and $(3,0)$ (remember - $3$ miles away), subject to our 'invisible wall' rule. Let's call such a path $p(x)$. We want to minimize the length of the walk, so let's calculate the length.
First, on a wall day - If you follow a path $p(x)$, you to $(l,p(l))$ before hitting the wall, and you will then have to travel $1-p(x)$ to get over the wall, and after that, simply a straight line to $B$ of length $\sqrt{1-(3-l)^2}$. Using the formula for arc-length, the length of your path is therefore:
$$\int_0^l \sqrt{1+p'(x)^2}dx+1-p(l)+\sqrt{1-(3-l)^2}$$
So the expected length on a wall day is:
$$\frac{1}{3} \int_0^3 \left(\int_0^u \sqrt{1+p'(x)^2}dx+1-p(u)+\sqrt{1-(3-u)^2}\right)du$$
Now, on a non-wall day, the length is simply the length of our path $\int_0^3 \sqrt{1+p'(x)^2}dx$, and since half of our days are wall-days, we have an average path length of:
\begin{align}
\frac1{6}\int_0^3\left(\int_0^u\sqrt{1+\left(p'(x)\right)^2}dx+1-p(u)+\\
\sqrt{1+(3-u)^2}+3\sqrt{1+\left(p'(u)\right)^2}\right)du
\end{align}
I will leave the details of the simplification to the reader (Hint: Change the order of integration), because it is quite tedious, but this integral can be simplified into this:
$$F(p)=\frac{1}{6}\int_0^3 (6-x)\sqrt{1+p'(x)^2}+1-p(x)+\sqrt{1+(3-x)^2}$$
This is great! Now, we finally have a short expression that we are trying to find a minimal $p(x)$ for. Just for reference, if $p(x)=0$, the straight path, we have $F(p)\approx3.69211$. So, how can we find a function that minimizes this integral? Well, here is where something called the Euler-Lagrange Equation comes in. The Euler-Lagrange equation deals with functionals, functions that take other functions as arguments. For example, we could define $L(f)=f(x)^2+f(x)$. It states that for a functional:
$$S(\boldsymbol q) = \int_a^b L(t,\boldsymbol q(t),\boldsymbol q'(t))\, \mathrm{d}t$$
That we can minimize our function $q(t)$ by solving the ODE:
$$L_q(t,q(t),\dot{q}(t))-\frac{\mathrm{d}}{\mathrm{d}t}L_{q'}(t,q(t),\dot{q}(t)) = 0$$
Where $L_q$ and $L_{q'}$ denote the partial derivatives of $L$ with respect to $q$ and $q'$, respectively. In our example, we have:
$$L(x,p(x),p'(x))= (6-x)\sqrt{1+p'(x)^2}+1-p(x)+\sqrt{1+(3-x)^2}$$
Now we can calculate our partial derivatives:
$${\displaystyle {\frac {\partial F(x,p,p')}{\partial y'}}={\frac {(6-x)y'(x)}{\sqrt {1+y'(x)^{2}}}}\quad {\text{and}}\quad {\frac {\partial F(x,p,p')}{\partial p}}=0}$$
Meaning that the ODE we are solving is:
$$\frac{\mathrm{d}}{\mathrm{d}x}\frac {(6-x)y'(x)}{\sqrt {1+y'(x)^{2}}}=-1$$
We can integrate both sides, re-arrange and integrate again to find:
$$p(x)=c_1-\cfrac{1}{3}(2 c_0+x+6) (c_0+2 x-6) \sqrt{\cfrac{1}{(c_0+6)(6-2x-c_0)}}$$
And since $p(0)=0$ and $p(3)=0$, we can solve directly for our constants. Actually, it's incredibly tedious, so we'll let Mathematica handle it for us. This is the most simplified form of $p(x)$ it could get out:
$$\frac{-3 \sqrt{163+9 \sqrt{57}}-\frac{2 i \sqrt{6
\left(\sqrt{57}-20\right)-\left(\sqrt{57}-27\right) x} \left(\left(\sqrt{57}-27\right)
x-6 \left(1+\sqrt{57}\right)\right)}{\sqrt{57}-27}}{6 \sqrt{42}}$$
So it seems Herbosquon has found his optimal curve, but will probably suffer an aneurysm on the way to school trying to calculate his next step. The curve looks like this:
Which, intuitively, seems to check the boxes. Herbosquon will only have to walk an average of $3.64827$ miles a day, saving him just around 100 feet a day! Over the course of $12$ years of schooling, Herbosquon will have saved himself the distance to space, or 25 $F1$ laps! Happy walking, Herbosquon.
No comments:
Post a Comment