3
$\begingroup$

You walk a certain path often from point A to point B which is 3 miles direct line. However, your path is obstructed randomly by a magic wall force field which extends 1 mile (in both directions) perpendicular to your path of travel between A and B. Your can think of those force field endpoints as C and D. So imagine a wide plus shape such that the wide part is the path you want to walk optimally (shortest possible case) but the perpendicular part of the force field is the part you have to walk around when it is present. The roughly plus shape is what it would look like if viewed from a plane looking on the ground at the shape points A,B,C and D make if the force field is present.

The rules are as follows:

  • You cannot detect the presence of the forcefield until you are right at it, at which point you could continue walking if it is not present or MUST walk around it if present. It will not disappear if you just wait there and you cannot just step over it. Once you successfully walk around it, it will then disappear (but may come back next walk).

  • You must walk only in straight line segments between A and B. You cannot follow a curved route for example like a semicircle shape path.

  • The forcefield appears randomly like the flip of a coin so on average it will be there 50%.

  • You cannot backtrack your path, you always make an effort to walk with B as your destination.

  • The force field will appear only at the midpoint between A and B which is 1.5 miles from both A and B. Your path will be marked at this point so you don't "crash" into the force field. You can simply stop at that point and test if the force field is present. It will only first appear (for that particular walk) when you are standing at this very small point along the path.

So the questions are what path do you take to minimize the walking distance on average? What will be that minimum average distance?

UPDATE:

Actually I was in a big hurry when I asked this question. Originally, the forcefield wall was supposed to be exactly midway between A and B but by forgetting to post that piece of information, it actually made the question more interesting. But for the sake of this question, assume it is midway between A and B each time it appears.

$\endgroup$
  • 3
    $\begingroup$ If the wall appears, is it always in the same place along the path? $\endgroup$ – LogicianWithAHat Apr 13 '16 at 15:41
  • 7
    $\begingroup$ "You cannot follow a curved route for example like a semicircle" - can't you approximate a semicircle by many straight lines? What does this restriction accomplish? $\endgroup$ – ffao Apr 13 '16 at 16:47
  • 2
    $\begingroup$ We actually require OP to tell us if the wall appears in the middle, or if it can appear anywhere along the route. VTC Unclear until this is established. $\endgroup$ – Chris Cudmore Apr 13 '16 at 17:09
  • 1
    $\begingroup$ Voting to reopen as question is clarified $\endgroup$ – ffao Apr 14 '16 at 3:30
  • 1
    $\begingroup$ Agreed, clarification helped. After my 'on hold' vote, I went along with the 'reopen' vote too. $\endgroup$ – Tim Couwelier Apr 14 '16 at 8:38
14
$\begingroup$

Average Walk (if Force Field at Midpoint): 3.5227 miles

In this answer I consider the wall at the middle.
I'm searching for the optimal direction to take at the begining (once you meet the wall (or not) the optimal direction is obvious).

enter image description here

I am looking for the value of $x$ such that average path is minimal.

$$ \begin{align} \overline{AP} &= \sqrt{1.5^2+x^2} \\ \overline{PC} &= 1-x \\ \overline{PB} &= \overline{AP} \\ \overline{CB} &= \sqrt{1.5^2+1^2} \end{align} $$

If the force field is present, the walking distance is $\overline{AP}+\overline{PC}+\overline{CB}$. If the force field is not present, the walking distance is $\overline{AP} + \overline{PB}$.

The average distance, $f(x)$, is equal to:

$$ \begin{align} f(x) &= \frac{(\overline{AP}+\overline{PC}+\overline{CB})+(\overline{AP} + \overline{PB})}{2} \\ &= \frac{3}{2}\overline{AP}+\frac{1}{2}\left(\overline{PC}+\overline{CB}\right) \\ &= \frac{3}{2}\sqrt{\left(\frac{3}{2}\right)^2+x^2} + \frac{1}{2}\left((1-x) + \sqrt{\left(\frac{3}{2}\right)^2+1^2}\right) \\ &= \frac{1}{2} + \frac{\sqrt{13}}{4} - \frac{x}{2} + \frac{3}{2}\sqrt{\frac{9}{4}+x^2} \end{align} $$

We can differentiate to find the value of $x$ for which $f(x)$ is minimized:

$$ f'(x) = 0 \\ -\frac{1}{2} + \frac{3}{4}\left(\frac{9}{4}+x^2\right)^{-1/2}\left(2x\right) = 0 \\ \frac{1}{2} = \frac{3}{2\sqrt{\frac{9}{4}+x^2}} \\ \sqrt{\frac{9}{4}+x^2} = 3x \\ \frac{9}{4}+x^2 = 9x^2 \\ x = \sqrt{\frac{9}{4\cdot 8}} = \frac{3}{4\sqrt{2}} \approx 0.530330\ldots $$

The minimum average distance is:

$$ f(3/\sqrt{32}) = \frac{1}{2} + \frac{\sqrt{13}}{4} + \frac{3}{\sqrt{2}} \approx 3.522708\ldots $$


Note that this is only a $3.5\%$ improvement over the worst strategy, walking straight towards $B$:

$$ f(0) = \frac{11}{4} + \frac{\sqrt{13}}{4} \approx 3.651388\ldots $$

...and only a $2.3\%$ improvement over always walking around the force field:

$$ f(1) = \sqrt{13} \approx 3.605551\ldots $$

$\endgroup$
  • $\begingroup$ This is actually the answer I was looking for and I got an identical answer if I run a computer program and ask it to print out the value of x that gives the shortest path. Choosing the midpoint of the wall (x=0.5) comes very close to the optimal (shortest) route. $\endgroup$ – David James Apr 14 '16 at 2:36
  • $\begingroup$ But the puzzle states that you "must walk only in straight line segments between A and B." This answer involves walking along a line that is not on the straight line between A and B? Additionally, if the wall was not present, you would have to turn partway through the walk in order to reach point B, which the puzzle expressly forbids. $\endgroup$ – Trevor Powell Apr 14 '16 at 9:30
  • $\begingroup$ @TrevorPowell The solution here is 2 or 3 straight line segments depending on the wall. "must walk only in straight line segments between A and B." means that you can go from A to B only by straight line segments, not that you should stay on the line AB. And I don't see where the puzzle forbids you to turn whenever you want. $\endgroup$ – Fabich Apr 14 '16 at 9:39
  • $\begingroup$ @Lordofdark I had taken "you always make an effort to walk with B as your destination" to mean that you must always walk as directly as possible toward B. $\endgroup$ – Trevor Powell Apr 14 '16 at 10:41
  • 1
    $\begingroup$ You are allowed to walk any line segment path between A and B. The "moving towards B" restriction was to not waste time thinking about any backtracking methods/paths but if I removed that, the correct answer would not change. The "crux" of this puzzle is finding the optimal angle to leave A since you cannot plan ahead of time if the force field will be present or not so you have to make your choice while still at A ideally. $\endgroup$ – David James Apr 14 '16 at 10:55
4
$\begingroup$

This solution is not at all optimized but it's a starting point:.

Average Walk if Force Field at Midpoint: 3.65 miles

Average Walk if Force Field N Miles from B: $\frac{7-N+\sqrt{N^2+1}}{2}$ miles


Here is a non-optimized answer: Attempt to walk a straight path every time.

If there is no force field, your route is a 3 mile straight line.

If there is a force field that day, your route will look like this:

Route

So the average length of your route is:

$\frac{3+(3-N+1+\sqrt{N^2+1})}{2} = \frac{7-N+\sqrt{N^2+1}}{2}$

If the force field always appears at the midpoint of your path, then that turns out to be 3.65 miles.

$\endgroup$
0
$\begingroup$

For my answer (and for the benefit of those not so good in math like me), I just wrote a very short computer program to check all values for x (the amount either "up" or "down" the wall) that we "aim" at immediately when leaving A. So if x=$0$, that is a straight line segment from A to midpoint of A and B for example and x=$0.5$ would be halfway "up" (or "down") the force field midway between A and B. So the program checks x=$0.00$, x=$0.01$, x=$0.02$... x=$0.99$, x=$1.00$ and simply chooses the one that produced the shortest average path. My program told me x=$0.53$ is optimal for an average path length of $3.5227$ miles. Interestingly, simply picking the midpoint (up or down) from the center of the wall (x=$0.5$) gives a near optimal result of $3.5231$ miles which is only $0.004$ miles longer which is only about $21$ feet.

$\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.