Beach Path math question

437 Views Asked by At

Anyone who has walked on the beach knows that walking speed is dependent upon how far away from the ocean one walks. If you walk on the wet sand you can walk much more quickly than if you walked on the dry sand. I have a question that discusses this principal.

On a Cartesian $xy$ plane limited by: Domain: {$x|0 \le x \le 1$} Range: {$y|0 \le y \le 1$} you start at the point ($0,0$) and you would like to travel on a defined path to ($1,1$) in the shortest amount of time. This sounds simple just take the path $y=x$ because it is the shortest path so it will take the shortest amount of time, but there is a catch. Your forward speed $\frac{dS}{dt}$ is equal to ($1−\frac{3}{4}y$). With this constraint in mind the path $y=x$ would not be the fastest path. What is the fastest path. I am open to questions about the problem itself if I have not been clear. Thank you.

3

There are 3 best solutions below

2
On

For your particular problem, there might be a simple solution in terms of e.g. Snell's law, as Hagen suggests in the comments above. But let me tell you a bit about how to solve these kinds of problems generally.

The general technique for solving this kind of optimization problem is the Calculus of Variations. The basic idea is this: you are looking at all paths $y(x)$ from $y(0)=0$ to $y(1)=1$, and trying to find the one that minimizes the total travel time $$T(\gamma)=\int_0^1 \frac{\sqrt{1+y'^2}}{1-\frac{3}{4} y}dx.$$

(We can assume that the path is a graph over $x$, since it is obviously a bad idea to double back.)

How do you do this? Well, suppose you have a best path $y$. Now consider perturbing the path by moving every point along it by some offset vector $\delta y(x)$. Since the endpoints of the path are fixed, you must have $\delta y(0) = \delta y(1) = 0$. For every scalar $\epsilon$, the perturbed curve $y + \epsilon \delta y$ must take longer to travel than $y$, since $y$ is the best path. In other words, for every $\delta y$, $\epsilon=0$ is a critical point of the scalar function $$F(\epsilon) = T(y+\epsilon\delta y)$$ so $$\frac{d}{d\epsilon} T(y+\epsilon\delta y)\Bigg\vert_{\epsilon=0} = 0.$$

For now we can write $T$ more generally as $\int_0^1 g(y,y')\,dx$. Taking the above derivative we get $$\int_0^1 \left(g_y \delta y + g_{y'} (\delta y)'\right)\,dx=0.$$ The trick now is that you can get rid of dependence on $(\delta \gamma)'$ by integrating by parts: $$\int_0^1 \frac{d}{dx} \left(g_{y'}\delta y\right)\,dx = \int_0^1 \left(\frac{d}{dx}g_{y'}\right)\delta y\,dx + \int_0^1 g_{y'}(\delta y)'\,dx$$ and the left-hand is zero since $\delta\gamma(1) = \delta\gamma(0) = 0.$ Plugging in we get the equation $$\int_0^1 \left(g_y - \frac{d}{dx}g_{y'}\right)\delta y\,dx = 0.$$ The key step is that the above has to hold for every perturbation $\delta y$. The only way the above is always zero, for any $\delta y$ including those perturbations that are zero except for arbitrarily small neighborhoods of any point on $[0,1]$, is if the stuff in parentheses, which doesn't depend on $\delta y$, is zero: $$\frac{d}{dx} g_{y'} = g_y,$$ an ordinary differential equation called the Euler-Lagrange equations of your variational problem.

Now $$\frac{d}{dx}\left(y' g_{y'}\right) = y''g_{y'} + y' \frac{d}{dx}g_{y'},$$ and plugging in the Euler-Lagrange equation we get $$\frac{d}{dx}\left(y' g_{y'}\right) = y''g_{y'} + y' g_y = \frac{d}{dx}g.$$

Integrating both sides by $x$ gives us $$y' g_{y'} = C + g$$ for some constant $C$. For our particular $g$, $$\frac{y'^2}{\left(1-\frac{3}{4}y\right)\sqrt{1+y'^2}} = C + \frac{\sqrt{1+y'^2}}{1-\frac{3}{4} y}.$$ Clearing out the denominator, things simplify to $$1 = -C\left(1-\frac{3}{4}y\right)\sqrt{1+y'^2}$$ or, since $y'\geq 0$, $$y' = \sqrt{\frac{1}{C^2\left(1-\frac{3}{4}y\right)^2}-1}.$$

This is now a separable first-order ODE; solving it and using the initial conditions $y(0)=0$ gives you a one-parameter family of curves from $(0,0)$ to $(1,1)$, and you can find the shortest by differentiating $T(\gamma)$ as a function of $C$ and finding the optimal $C$.

5
On

Taking my cue from Hagen von Eitzen, and looking at Snell's law, you find that at every point of the curve, the sine of the angle between a tangent and the $y$ direction will be proportional to the speed, i.e. proportional to $1-\frac34y$. What you need is that proportionality factor, which I'll call $a$. To treat $x$ and $y$ direction independently, it makes sense to look at the tangens instead of the sine, since that is the ratio of $x$ movement per $y$ movement:

\begin{align*} \frac{\mathrm dx}{\mathrm dS} = \sin\theta &= a\left(1-\frac34y\right) \\ \frac{\mathrm dx}{\mathrm dy} = \tan\theta &= \frac{\sin\theta}{\sqrt{1-\sin^2\theta}} \\ x(1) = \int_0^1\tan\theta\,\mathrm dy &= \frac{4\left(\sqrt{1-\frac1{16}a^2}-\sqrt{1-a^2}\right)}{3a} \end{align*}

Now you want to choose $a$ such that this value becomes $1$. You will find that it does for

$$ a= \frac4{\sqrt{17}} $$

With that, you can describe your curve using any of the following equations:

\begin{align*} x(\tilde y) &= \int_0^{\tilde y}\tan\theta\,\mathrm dy = \frac{\sqrt{1 + 24\tilde y - 9\tilde y^2} - 1}{3} \\ y(x) &= \frac{4-\sqrt{16 - 6x - 9x^2}}{3} \\ 0 &= x^2+\frac23x+y^2-\frac83y \\ \frac{17}{9} &= \left(x+\frac13\right)^2 + \left(y-\frac43\right)^2 \end{align*}

So your curve is a segment of a circle of radius $\frac{\sqrt{17}}3$ with center at $(-\frac13,\frac43)$ just as studiosus indicated.

Plot of this curve

If you prefer to express things in terms of your time $t$, I've been able to obtain a formula for that as well:

\begin{align*} x(t) &= \frac{8\left(1+\sqrt{17}\right)\left(e^{\frac32t}-1\right)} {3\left(8+\left(9+\sqrt{17}\right)e^{\frac32t}\right)} \\ y(t) &= \frac43\left(1-\frac{\left(17+\sqrt{17}\right)e^{\frac34t}} {8+\left(9+\sqrt{17}\right)e^{\frac32t}}\right) \\ t_1 &= \frac23\log\frac{8\left(4+\sqrt{17}\right)}{-19+5\sqrt{17}} \approx 2.463 \end{align*}

This time $t_1$ is the time at which the point $(1,1)$ is reached.

0
On

This is a very cute problem. Here is a solution using hyperbolic geometry which explains the suggestion you got at Mathoverflow. Take the formula $$ T(\gamma)=\int_0^1 \frac{\sqrt{1+(y')^2}}{1- \frac{3}{4}y}dx $$ as in user7530s answer. Now, let's make the change of variables: $$ u= \frac{3}{4}x, v= 1- \frac{3}{4}y. $$ Note that this change of variables is a Euclidean similarity (it contracts all distances by the same amount). The integral becomes $$ T(\gamma)= \frac{3}{4}\int_0^{3/4} \frac{\sqrt{1+(v')^2}}{v}du $$ Declare $t=u$ (time parameter). Then this integral (I am ignoring the constant factor in front) is the hyperbolic arc-length of the curve $\gamma$ with respect to the Riemannian metric $$ \frac{du^2 + dv^2}{v^2} $$ on the upper half-plane $H=\{(u,v): v>0\}$.

Your goal is to minimize $T$ over all paths $\gamma$ connecting the two given points. It is well-known that minimizers of lengths are hyperbolic geodesics which are arcs of circles perpendicular to the $v$-axis. See for instance J.Anderson "Hyperbolic Geometry".

Converting back to $xy$-coordinates, we see that the minimizing path is arc of circle through the points $(1,1), (0,0)$ and with center $p$ on the line $y=\frac{4}{3}$. Elementary computation then gives you that $p=(-\frac{1}{3}, \frac{4}{3})$ and the radius of the circle is $\frac{\sqrt{17}}{3}$.