2
$\begingroup$

The following diagram depicts a Pass the Baton tournament

enter image description here

(Note: due to a merge, some of the answers below use this image instead.)

Each team consists of 6 members, 2 at the central point $E$, and one on each side of the quadrilateral, $a$, $b$, $c$, and $d$. The members of the race run to the sides in the following order: $E$ to side $a$, $a$ to $b$, $b$ back to $E$, $E$ to $c$, $c$ to $d$, and $d$ back to $E$.

The challenge for the teams is not only to run as fast as they can but to select the best route, by selecting the best points on $a$, $b$, $c$, and $d$ to have the relay runners stand.

What is this route?

$\endgroup$
  • $\begingroup$ Are we given the lengths of EA, EB, etc. or are we supposed to solve the problem for them being arbitrary? $\endgroup$ – Joe Z. Mar 28 '15 at 4:59
  • $\begingroup$ No. You may find a minimal route without this information but you may employ some measurements. $\endgroup$ – Moti Mar 28 '15 at 5:30
  • $\begingroup$ When you say "run to a line" can it be any point on that line? $\endgroup$ – Areeb Aug 7 '16 at 19:41
  • 1
    $\begingroup$ You are supposed to run through the purple area to the lines... $\endgroup$ – Moti Aug 7 '16 at 20:02
  • 2
    $\begingroup$ Are AC and BD perpendicular? $\endgroup$ – f'' Aug 7 '16 at 21:15
4
$\begingroup$

In any locally minimal solution, the paths must reflect off the edges, with equal angle of incidence and reflection. This is because reflecting a leg of this this path makes a straight line between one point and the reflection of the other, the shortest distance between two points.

So, we can find the shortest path by reflecting the figure over a, then the result over b, and connecting the original point E to the final one. This gives a cycle from E to a to b to E. We then do the same for c and d. Taking the union of two cycles gives the full cycles.

(Sorry, I can't draw a diagram now because I'm on my phone. )

$\endgroup$
  • $\begingroup$ Oh wow, I can't believe I missed that. $\endgroup$ – Joe Z. Mar 28 '15 at 6:39
  • $\begingroup$ How you know that the reflections "meet" , and if not how you find the actual minimal path? You have done the first step... but using this rule is not yet the silution. $\endgroup$ – Moti Mar 28 '15 at 20:06
  • $\begingroup$ The reflection of b is going where? Through E? $\endgroup$ – Moti Mar 28 '15 at 20:07
  • $\begingroup$ @Moti I don't understand what you're asking. The whole figure is being reflected over each edge. $\endgroup$ – xnor Mar 28 '15 at 20:15
  • $\begingroup$ No, there are no symmetries in the figure. The distances are arbitrary - only AC perpendicular to BD. So, what exactly in the figures is reflected? You may chose a direction that will be reflected, but is this true - all three lines are reflected $\endgroup$ – Moti Mar 28 '15 at 20:30
3
$\begingroup$

Let us first consider the first half of the race, from AC to AB to BC back to the starting point on AC. Let $H_A, H_B, H_C$ be the three points the path meets. For a given choice of $H_A$ and $H_B$, the best possible $H_C$ is that such that $\angle H_BH_CA = \angle BH_CH_A$. This fact is easy to see by reflecting one half of the path $H_A \to H_C \to H_B$ along $AB$.

The best possible path therefore satisfies $\angle H_BH_CA = \angle BH_CH_A, \angle H_CH_AB = \angle CH_AH_B$ and $\angle H_AH_BC = \angle AH_BH_C$, otherwise there would obviously be a better path. These three conditions are satisfied exactly when $H_A$, $H_B$ and $H_C$ are the altitude basepoints of the triangle. To verify that, use the inscribed angle theorem a bunch of times on the Thales circles over the three sides.

So the best path for the first half of the race starts and ends at the orthogonal projection of $B$ onto $AC$, which is conveniently $E$.

The best path for the second half of the race starts and ends at the orthogonal projection of $D$ onto $AC$, which is just as conveniently also $E$.

The optimal path for the entire race is therefore this:

Start at $E$. Go straight to the projection of $C$ onto $AB$, then straight to the projection of $A$ onto $BC$, then back to $E$. Continue to the projection of $C$ onto $AD$, then to the projection of $A$ to $CD$, then finish back at $E$.


$\endgroup$
  • $\begingroup$ Your answer is right! I hope that you could solve it without the need of the great editor... Peregrine the Rook...:) $\endgroup$ – Moti Aug 7 '16 at 23:04
  • $\begingroup$ @Moti: Was that comment meant to be sarcastic? I ask because, like your question, it wasn’t clear.      :-)      (And, yes, that was sarcastic.) $\endgroup$ – Peregrine Rook Aug 8 '16 at 0:38
  • $\begingroup$ @McFry: Good job, but I almost downvoted this answer for switching the orientation of points $B$ and $C$. $\endgroup$ – Peregrine Rook Aug 8 '16 at 0:39
2
$\begingroup$

Here's a brute-force solution involving calculus, in the absence of anything more elegant at the moment.


Let $p_a, p_b, p_c, p_d$ be the proportional position of the points that the relay racers run to, with:

  • $p_a, p_d = 0$ being at point $A$,
  • $p_b, p_c = 0$ being at point $C$,
  • $p_a, p_b = 1$ being at point $B$, and
  • $p_c, p_d = 1$ being at point $D$.

Then, for example, if $p_a = 0.5$, then the racer touches $a$ at its midpoint, and if $p_a = 0.75$, then the racer touches $a$ three-quarters of the way toward point $B$.

If we've defined these, then we can define a total distance function $f(p_a, p_b)$ as follows:

\begin{align} f(p_a, p_b) =\ &\sqrt{(EA \cdot p_a)^2 + (EB \cdot (1 - p_a))^2} +\\ &\sqrt{(EC \cdot p_b)^2 + (EB \cdot (1 - p_b))^2} +\\ &\sqrt{(EC \cdot p_b + EA \cdot p_a)^2 + (EB \cdot (p_a - p_b))^2} \end{align}

This function appears to be differentiable, and graphing them in Wolfram Alpha shows that they have a global minimum when their partial derivatives are both equal to zero.

You can define $g(p_c, p_d)$ similarly, and since they're independent, we can minimize each of them individually and that will minimize the sum.


The partial derivatives are sort of tedious, though, so I'll put them off until later.

$\endgroup$
  • $\begingroup$ It could be interesting to find if this approach will work and if you could translate it into a practical solution $\endgroup$ – Moti Mar 29 '15 at 4:58
2
$\begingroup$

Edit: Incorrect
My answer would be:

Right on point E

Explanation:

If you place the starting on Point E, a runner can go straight up to AB, touch it, and then touch BC without having to move, before coming straight down. After that, they can go straight down to AD, touch that, and then DC without having to move before coming back up.

$\endgroup$
  • $\begingroup$ I assume that you mean go to pint B, return to E and then continue to D and back. You are increasing the probability of losing... Wrong answer $\endgroup$ – Moti Aug 7 '16 at 19:57
  • $\begingroup$ Suggest you remove the answer not discourage others assuming that it was answered... $\endgroup$ – Moti Aug 7 '16 at 19:58
  • $\begingroup$ @Moti I'll just mark it incorrect, so people don't make the same mistake. $\endgroup$ – Areeb Aug 7 '16 at 19:59
  • 1
    $\begingroup$ I'm not sure that that's necessary — puzzles on this site often get as many as $42$ answers; most people know not to give up until one has been accepted (and some people don't give up even then). $\endgroup$ – Peregrine Rook Aug 7 '16 at 20:04
  • $\begingroup$ See the correct answer - the minimal path of internal triangle is formed by the foots of the heights. $\endgroup$ – Moti Aug 8 '16 at 0:55
2
$\begingroup$

I think the answer is as follows:

Reflect the triangle ABC in line AB to produce triangle ABC'; reflect this in BC' to produce triangle A'BC'. Transfer the second and third segments of the path you run into these reflected triangles in the obvious way. You get a path from your starting point P to its twice-reflected counterpart P', which is obviously shortest when it's a straight line.

(Another way to put this: Your path from P to AB to BC and back to P must be one that light could travel, if the sides of the triangle were mirrors.)

Now do the same thing to the lower part of the picture, with the same conclusion. Except that it will make things a little nicer if we traverse the second half of the path in the opposite direction from that given in the question -- from P to CD to AD and back to P -- which becomes a path from P via CD to A''D and then to A''C'' at point P''.

Now, it seems this path will be shortest when it's a straight line from P' to P'', which ... ah, but no, this is wrong, because P' and P'' are not fixed points; when P moves so do they. So, what's the relationship between these points? Answer: P' is what you get from P by rotating clockwise about B through twice the angle at B (in triangle ABC), and P'' is what you get by rotating clockwise about D through twice the angle at D. Hence the distance PP' is 2 BP sin B and PP' is 2 DP sin D and we're trying to minimize BP sin B + DP sin D. If ABCD were in arbitrary places this would (I think) be fiddly but in this case it happens that point E minimizes DP and BP simultaneously and hence minimizes BP sin B + DP sin D (since both those sines are positive).

So Areeb was partly right and we should start and end at point E. But the path we take should be the one I described above (reflect, draw a straight line, and then reflect back into the original triangle) rather than going straight to B/D and back again.

$\endgroup$
  • $\begingroup$ Your answer is hard to visualize, could you add a diagram? $\endgroup$ – Areeb Aug 7 '16 at 20:46
  • $\begingroup$ Yup, but I'm busy with other things for maybe the next hour... $\endgroup$ – Gareth McCaughan Aug 7 '16 at 20:49
  • $\begingroup$ This is not the right answer - at least there is a much simpler solution that may be proved to be minimal and I do not see how the proposed path by you reflects on it. $\endgroup$ – Moti Aug 7 '16 at 21:06
  • $\begingroup$ A drawing (at least for the first case) would help to evaluate your solution. How you conclude that start at E? Note that your double reflection introduces a point that is not reflected into AC thus it does not have to be a straight line, if I understand your solution. A drawing would clarify and allow a better evaluation of your solution. $\endgroup$ – Moti Aug 7 '16 at 21:17
  • $\begingroup$ I agree that a diagram would help. Unfortunately I'm still otherwise occupied... $\endgroup$ – Gareth McCaughan Aug 7 '16 at 22:16
2
$\begingroup$

Not an answer. Maybe a clarification?

Based on the number of comments, it seems that there is a bit of confusion surrounding this puzzle. This is my interpretation of how an answer might look. The runner starts at the point shown by the arrow, then runs through segments 1-6 in order.

The puzzle does not specify that the "touch and go" points on the ABCD diamond are fixed, so I assume we have freedom to build a course however we wish.

Is this correct or have I missed something?

sample path

$\endgroup$
  • $\begingroup$ Your interpretation is right but not the minimal path...:) $\endgroup$ – Moti Aug 7 '16 at 21:07
1
$\begingroup$

I believe that the answer is

  • Start at the midpoint of line AC.
  • Go to the midpoint of line AB (on a path that's parallel to line BC).
  • Go to the midpoint of line BC (on a path that's parallel to line AC).
  • Return to the midpoint of line AC (on a path that's parallel to line AB).
  • Go to the midpoint of line AD (on a path that's parallel to line CD).
  • Go to the midpoint of line CD (on a path that's parallel to line AC).
  • Return to the midpoint of line AC (on a path that's parallel to line AD).

Like this:

Still working on a proof.

$\endgroup$
  • $\begingroup$ This is not the right answer - there is a shorter path $\endgroup$ – Moti Aug 7 '16 at 21:07
0
$\begingroup$

Edit: Duplicate.

I haven't read any of the spoilers yet, but I would guess the shortest line would be from

E to B to D and back to E.

...because...

B is on both AB and BC; likewise D is on both AD and CD. This eliminates two of the line segments in the path. I'm pretty sure I can prove this using the triangle rule.

I will work out the math after checking the other answers.

$\endgroup$

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.