8
$\begingroup$

You are running to catch a bus that is going on a horizontal road.

The bus is at point (0,0) while you are at point (s,k) where s and k are constants. The bus moves at some velocity v and you have to run to catch it. At what angle should you run in order to minimize the speed you need to run at in order to catch it?

This is a puzzle that a friend gave me that I solved and thought was super cool.

$\endgroup$
7
  • $\begingroup$ I put an edit with clarifications: 1) defining "angle," 2) direction and path of the bus, 3) (s,k) is in Q1, 4) grammar and misc stuff $\endgroup$
    – Ankit
    May 16, 2022 at 1:22
  • $\begingroup$ @Ankit one of the standard edit rejection reasons is that an edit should have been a reply (comment/answer, as appropriate) instead. Please do not edit questions with clarifications or anything else that has the possibility of changing the meaning of the question, even if you think you know what the intent of the question is, especially here where the poster is reasonably likely to respond. Instead comment and ask for clarification. $\endgroup$
    – bobble
    May 16, 2022 at 1:34
  • $\begingroup$ @bobble I am aware of that... I put the edit in cuz it would be trivial (to solve) and impossible (for the scenario to occur) otherwise $\endgroup$
    – Ankit
    May 16, 2022 at 1:47
  • 1
    $\begingroup$ I agree with bobble: you shouldn't be editing other people's questions in a way that substantially changes the question, unless there's good reason to think that OP has disappeared and so can't do it themselves. (I expect your edits did actually improve the question! But it's better practice to ask whatever clarifying questions you wish, and let the OP make whatever edits or other responses they think appropriate.) $\endgroup$
    – Gareth McCaughan
    May 16, 2022 at 19:24
  • 1
    $\begingroup$ (Yes, it's mathematical, but -- see my answer -- I think there is a way of looking at it that makes almost all the mathematical drudgework go away, which I think is sufficient for this to qualify as a puzzle rather than a textbook exercise.) $\endgroup$
    – Gareth McCaughan
    May 16, 2022 at 20:13

3 Answers 3

8
$\begingroup$

I think this is best thought of as

a problem in three dimensions, the third being time.

So, suppose

the bus starts at $(0,0,0)$ and proceeds in direction $(x,y,t)$ -- so its speed is $\frac{\sqrt{x^2+y^2}}t$ and its velocity in the plane is $(x/t,y/t)$. You start at $(s,k,0)$ but we might as well choose coordinate axes so that you start on the positive $x$-axis, and units of distance so that you start at $(1,0,0)$. Constant-velocity paths of a given speed for you form a cone based at $(1,0,0)$ with axis parallel to $(0,0,1)$; slower speed means the cone is closer to that axis.

If

you aren't moving at all then you catch the bus if and only if it is already coming straight towards you, which means that its path $\{\lambda(x,y,t)\,:\,\lambda>0\}$ passes through $\{(1,0,-)\}$, which means that $y=0$. Otherwise, the "zero-width cone" misses the bus's path, and the question is how much it needs to be expanded before that stops being true. At the point where the cone is just wide enough, the bus's path is tangent to the cone. What does that mean? The cone is $(X-1)^2+Y^2=v^2T^2$ where $v$ is your speed; its intersection with the bus's path is given by $(\lambda x-1)^2+\lambda^2y^2=v^2\lambda^2t^2$ or $(x^2+y^2-v^2t^2)\lambda^2-2x\lambda+1=0$, and tangency means that this quadratic in $\lambda$ has a double root, or equivalently that $x^2=x^2+y^2-v^2t^2$, or equivalently that $v=\pm y/t$. Here $v$ is a speed, not a velocity, and only its square matters, so we might as well take $v=y/t$. In other words, the slowest you can go without failure is the bus's speed in the direction perpendicular to the line between you and the bus, or to put it differently the bus's apparent speed as you look towards it from your starting position if you are unable to discern its motion toward you / away from you.

In this case, what direction do you need to run in?

The quadratic with a double root is $x^2\lambda^2-2x\lambda+1=0$, which is to say $(x\lambda-1)^2=0$, so $\lambda=1/x$, so the point where the bus's path meets your cone of constant speed is $(1,y/x,t/x)$, which means your path is parallel to the vector $(0,y/x,t/x)$ or equivalently to the vector $(0,y,t)$, which means that you go perpendicularly to the line joining you to the bus's starting position.

That is:

look towards the bus and run crabwise, always facing in that direction and travelling perpendicularly, so that you keep facing exactly towards the bus.

But wait, isn't there something nonsensical here?

Suppose the bus is also going perpendicularly to that line. Then this prescription says that you go parallel to the bus, at exactly the same speed as the bus, which means you never catch it. That might make sense if you actually couldn't ever catch the bus, but obviously you can if you run fast enough. So what's going on?

It's not nonsensical at all, as it turns out.

What's going on is that in this case there is no such thing as a slowest speed at which you can catch the bus. If you go just a tiny bit faster than the bus, and head just ever so slightly towards its path, then you will catch the bus after a very long time. The slower you go (while still going faster), the longer it will take; but there's no slowest successful speed because if you're at all faster than the bus then you can do it but if you're exactly the same speed as the bus the best you can do is to run parallel to it, never falling behind but also never getting any closer.

There's another awkward case. What if

the x-component of the bus's velocity is away from you? In this case, if you follow my prescription you will never reach it -- and yet, obviously, if you're much faster than the bus then you can in fact catch it. What's going on this time? Same again: this is a case where actually there is no such thing as a slowest successful speed. If you go just a tiny bit faster than the bus, then you can run at almost exactly its velocity and eventually catch it; if you go at the same speed as the bus, obviously you can't ever catch it.

So, with all details filled in, the answer is as follows.

If the bus is travelling towards your position (i.e., the component of its velocity along the line between its initial position and yours is towards you) then you should run perpendicular to that line, matching the component of the bus's velocity that's in the direction you're going; this is the slowest speed that lets you catch the bus. If not, then there is no slowest speed that lets you catch the bus; you can catch it iff you are faster than it is, and as your speed advantage approaches zero the time it takes you to catch up goes to infinity while the direction you need to go in approaches the direction in which the bus is moving.

The reason why I like this approach is that

it requires neither trigonometry nor calculus nor anything fancier than understanding quadratic equations.

Incidentally, the special case we considered earlier

(where you don't need to move at all) isn't really a special case. It's just what happens in the general case, where the perpendicular component of the bus's velocity is zero.

$\endgroup$
2
$\begingroup$

Let's start with some definitions:

  • $w$ is your speed.
  • $d$ the unit vector representing the direction of your movement, where $d = w(x, y)$, being $x$ and $y$ the components of the movement direction.
  • $G$ is the point where you meet the bus. $G = (g, 0)$. $g$ is the first component of $G$.
  • You are at $P_0 = (s, k)$.
  • $n = \sqrt{(s - g)^2 + k^2} = \sqrt{s^2 - 2gs + g^2 + k^2}$, this is the distance that you should walk and it depends on $g$.
  • $m = \sqrt{s^2 + k^2}$, this is your initial distance to the bus.
  • $t$ is the time that it takes for you and the bus meet.
  • $C$ is $(s, 0)$. I.e. the point in the road where you would go if you were to go straight to it in the nearest point (but this might miss the bus).
  • $H$ is the angle that is exactly at you in the bus-you-$G$ triangle.
  • $B$ is the angle that is exactly at the bus in the bus-you-$G$ triangle.

First, we have something very important to note:

We want to minimize your speed, not distance! It doesn't matter if you walk for zillions of light years taking an insane amount of time expressed in scientific notation or in Knuth's arrows notation before catching the bus looooong after the Big Crunch or whatever is the fate of the Universe just because the difference between your speed and the bus' speed is some infinitesimal $\epsilon$ measured in the Planck scale.

Let's solve the easiest trivial degenerate cases:

If $s = 0$ and $k = 0$, just enter the bus. Thus $w = 0$, $d$ is indefinite, but doesn't matter and $n = 0$.

Another very easy degenerate case:

If $s > 0$ and $k = 0$, just wait for the bus and do not move at all and. Then $w = 0$, $d$ is indefinite once again and $n = 0$.

The last degenerate case:

If $s \leq 0$, you are either somewhere behind the bus or at most, at its side. Move at $w = v + \epsilon$ speed to reach it eventually in the eternity after walking just for forever. Also, $d = (1, \epsilon k)$ and $n \to +\infty$.

Now, the interesting cases are those that:

$s > 0$, $k \neq 0$ and $w < v$.

We observe that:

$(0, 0)$, $G$ and $P_0$. I.e., your position, the bus position and the meeting point forms a triangle with sizes $g$, $m$ and $n$.

So what?

Let's suppose that the vertex at $G$ is obtuse.

What happens?

Then we are going towards the bus in an angle just at the minimum speed needed to not miss it. However, if instead we walk at the same velocity straight to the road, we would arrive there earlier and still ahead of the bus, which means that we could go slower instead, contradicting the idea that it was the minimum speed. Hence, $G$ can't be an obtuse angle.

Note that since we already ruled out a lot of cases:

$y \neq 0$ (otherwise, it is a degenerate case).
$k \neq 0$ (otherwise, it is a degenerate case).
$\text{sgn}(y) = -\text{sgn}(k)$ (otherwise, instead of going to get the bus, you would be going away to it).
$x^2 + y^2 = 1$ (because $d$ is a unit vector and $d = (x, y)$).
$w > 0$ (negative speed makes no sense, zero speed is degenerate).
$t > 0$ (negative time makes no sense, zero time is degenerate).
$v > 0$ (the bus isn't stopped and is moving forward).
$g > 0$ (we can't meet the bus behind its starting point, zero is degenerate).
$x \geq 0$ (because the angle at $(g, 0)$ can't be obtuse).

Let's do a few math:

$$g = tv$$ $$t = \frac{g}{v}$$ $$n = tw$$ $$w = \frac{n}{t}$$ $$w = \frac{n}{\frac{g}{v}}$$ $$w = \frac{vn}{g}$$ $$wg = vn$$ $$B = \text{atan2}(k, s) = \text{arctan}\left(\frac{s}{k}\right)$$ $$\text{tan}(B) = \frac{s}{k}$$

What if we choose an angle?

We might choose in which angle we want to meet the bus or to which direction we want to walk and adjust or velocity accordingly. $B$ is fixed and the sum of the angles must be $180°$, so we have to choose either $H$ or $G$ and the other is defined accordingly.

How can we choose an angle at $H$?

If it is right, then $m^2 + n^2 = g^2$.
If it is acute, then $m^2 + n^2 > g^2$.
If it is obtuse, then $m^2 + n^2 < g^2$.
So, let's just try the three cases and see what we get.

Also, consider that $\phi$ is some number that represents some artificial unknown algebraic area surplus, so we can turn inequations into equations.

How?

With $\phi$, we can turn all those three cases into $m^2 + n^2 = g^2 + \phi$.
If $H$ is acute, then $\phi < 0$.
If $H$ is right, then $\phi = 0$.
If $H$ is obtuse, then $\phi > 0$.

Thus:

$$m^2 + n^2 = g^2 + \phi$$ $$\sqrt{s^2 + k^2}^2 + \sqrt{s^2 - 2gs + g^2 + k^2}^2 = g^2 + \phi$$ $$s^2 + k^2 + s^2 - 2gs + g^2 + k^2 = g^2 + \phi$$ $$2s^2 + 2k^2 - 2gs = \phi$$ $$s^2 + k^2 - gs = \phi$$ $$s^2 + k^2 = gs + \phi$$ $$gs = s^2 + k^2 - \phi$$ $$g = \frac{s^2 + k^2 - \phi}{s}$$ $$n = \sqrt{s^2 - 2gs + g^2 + k^2}$$ $$n = \sqrt{s^2 - 2s^2 - 2k^2 - 2 \phi + g^2 + k^2}$$ $$n = \sqrt{g^2 - s^2 - k^2 - 2 \phi}$$ $$w = \frac{vn}{g}$$ $$w = \frac{v\sqrt{g^2 - s^2 - k^2 - 2 \phi}}{g}$$ $$w = \frac{v\sqrt{\left(\frac{s^2 + k^2 - \phi}{s}\right)^2 - s^2 - k^2 - 2 \phi}}{\frac{s^2 + k^2 - \phi}{s}}$$ $$w = \frac{sv\sqrt{\left(\frac{s^2 + k^2 - \phi}{s}\right)^2 - s^2 - k^2 - 2 \phi}}{s^2 + k^2 - \phi}$$

The resulting expression is complicated, but it only depends on the given values $s$, $k$ and $v$ and in our arbitrary variable $\phi$. Let's try to make it simpler:

$$w = \frac{sv\sqrt{\left(\frac{m^2 - \phi}{s}\right)^2 - m^2 - 2 \phi}}{m^2 - \phi}$$ $$\frac{w}{sv} = \frac{\sqrt{\left(\frac{m^2 - \phi}{s}\right)^2 - m^2 - 2 \phi}}{m^2 - \phi}$$ $$\frac{w(m^2 - \phi)}{sv} = \sqrt{\left(\frac{m^2 - \phi}{s}\right)^2 - m^2 - 2 \phi}$$ $$\left(\frac{w(m^2 - \phi)}{sv}\right)^2 = \left(\frac{m^2 - \phi}{s}\right)^2 - m^2 - 2 \phi$$ $$\frac{w^2 (m^2 - \phi)^2}{s^2 v^2} = \left(\frac{m^2 - \phi}{s}\right)^2 - m^2 - 2 \phi$$ $$\frac{w^2 (m^2 - \phi)^2}{s^2 v^2} = \frac{m^4 - 2 m^2 \phi + \phi^2}{s^2} - m^2 - 2 \phi$$ $$\frac{w^2 (m^2 - \phi)^2}{s^2 v^2} = \frac{m^4 - 2 m^2 \phi + \phi^2 - m^2 s^2 - 2 \phi s^2}{s^2}$$ $$\frac{w^2 (m^2 - \phi)^2}{v^2} = m^4 - 2 m^2 \phi + \phi^2 - m^2 s^2 - 2 \phi s^2$$ $$\frac{w^2 (m^4 - 2 m^2 \phi + \phi^2)}{v^2} = m^4 - 2 m^2 \phi + \phi^2 - m^2 s^2 - 2 \phi s^2$$ $$\frac{w^2}{v^2} = \frac{m^4 - 2 m^2 \phi + \phi^2 - m^2 s^2 - 2 \phi s^2}{m^4 - 2 m^2 \phi + \phi^2}$$ $$\frac{w}{v} = \frac{\left(m^2 - \phi\right)^2 - m^2 s^2 - 2 \phi s^2}{\left(m^2 - \phi\right)^2}$$ $$\frac{w}{v} = 1 + \frac{- m^2 s^2 - 2 \phi s^2}{\left(m^2 - \phi\right)^2}$$ $$\frac{w}{v} = 1 - \frac{m^2 s^2 + 2 \phi s^2}{\left(m^2 - \phi\right)^2}$$

CAVEAT:

I know that $\phi = 0$ and $H = 90°$. But found no way to show that formally. I may come back later to finish this.

Then, all of that would get way simpler:

$$\frac{w}{v} = 1 - \frac{m^2 s^2}{m^4}$$ $$\frac{w}{v} = 1 - \frac{s^2}{m^2}$$ $$\frac{w}{v} = 1 - \frac{s^2}{s^2 + k^2}$$ $$w = v \left(1 - \frac{s^2}{s^2 + k^2}\right)$$ $$w = v - \frac{vs^2}{s^2 + k^2}$$ $$G = 90° - B$$

Then, the direction:

$$d . (s, k) = 0$$ $$(x, y) . (s, k) = 0$$ $$sx + yk = 0$$ $$sx = -yk$$ $$x = \frac{-yk}{s}$$ $$\frac{x}{y} = -\frac{k}{s}$$ $$d = \frac{(-k, s)}{\sqrt{k^2 + s^2}}$$

Or, in layman terms:

Look to where the bus is, turn $90°$ to the side looking to somewhere in the road ahead the bus and go there. That is your direction.

Also:

$g$ is the hypotenuse of a right triangle between $H$, $B$ and $G$.

Or in other words:

$$g = m \text{ sec}(B)$$ $$g = \sqrt{s^2 + k^2} \text{ sec}(B)$$ $$g = \sqrt{s^2 + k^2} \text{ sec}\left(\text{arctan}\left(\frac{s}{k}\right)\right)$$

CAVEAT:

I am too tired, might come back later to finish this. But it is 95% done, I guess.

$\endgroup$
1
$\begingroup$

Answer

The angle which you should run is

$\tan^{-1}(\frac{1}{s})$ Pleasantly surprised how nice the answer ended up.

Here's my work:

Lower bound:

Knowing that r=d/t, it wouldn't make sense for $\theta<0$ as $\theta=0$ always requires less speed. We know this because decreasing $\theta$ past $0$ would increase d and decrease t, thus increasing r.

Upper bound:

$\theta$ also cannot be equal or greater than $\frac{\pi}{2}$ as $\frac{\pi}{2}$ means you will run parallel to the bus, and anything greater means you will run away from the bus.

Knowing this:

We can set up a couple related rates equations, do some algebra to get r (speed required) in terms of $\theta$ (angle) and then setting the derivative equal to 0 and solving for theta to get the turning point, whose x-value is the speed-minimizing angle. (Technically we should take the second derivative to ensure the turning point is a minimum, but if you graph the equation, you'll see it always is a minimum within the $[0,\frac{\pi}{2})$ interval so theres no need to do this).

Math:

Math

Dealing with holes:

I could get rid of the really annoying denominator cuz it gets multiplied by 0, but this could technically create holes in the arctan graph (cuz you can't divide by zero). Here is a proof that shows that there are no holes:

No Holes Proof:

No Holes Proof

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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