2
$\begingroup$

This is a harder version of the fixed wall variation.

Every day you walk across a flat plane from a point $A$ to a point $B$. The points are $3$ miles apart. However, every day there is a 50% chance that there is an invisible force field between the two points. The force field extends $1$ mile in each direction perpendicular to the line between $A$ and $B$, and its position is uniformly distributed between the two points. You don't know if the force field is present or where it is until you run into it.

What path should you take to minimize the distance you must travel to reach point $B$ from point $A$ on average? This a mathematical problem, so your solution shouldn't involve "lateral thinking," like climbing over the wall. You can assume that you can follow your planned path exactly, the wall has negligible thickness, etc.


Computer simulation might be a good way to try to solve this but mathematical solutions are encouraged as well.

I am not good at drawing out diagrams here to show the possible paths so I hope someone can add it to their answer.

The answer could be expressed as an angle to leave starting point $A$; I am not sure how else the answer can be expressed other than maybe total distance traveled on average.

How the hell can this be off topic when the previous simpler version of this was not? Whoever stated it is off topic is very inconsistent and also this question received 2 upvotes and 3 favorite votes so it would make sense to keep it open and active, not on hold. Please "fix" this ASAP.

$\endgroup$
  • $\begingroup$ is the position of the wall uniformly randomly distributed on the segment with endpoints A and B? $\endgroup$ – elias Apr 15 '16 at 13:49
  • $\begingroup$ Yes the wall can be ANY random position between and B so any position within those $3$ miles. It could be $1$ inch away or $2.99999$ miles away or any position in between A and B. I guess on average it will be $1.5$ miles away. $\endgroup$ – David James Apr 15 '16 at 13:50
  • $\begingroup$ Something tells me that since the average distance the wall will be away is $1.5$ miles, that an optimal solution should be based on that assumption as if the wall was fixed at that location. However, the answer may surprise us and not be that. $\endgroup$ – David James Apr 15 '16 at 13:54
  • 2
    $\begingroup$ I guess that means uniform (chance of every position is the same) $\endgroup$ – ffao Apr 15 '16 at 14:14
  • 1
    $\begingroup$ @DavidJames While I didn't vote to close this one, I agree with the vote. Note that the only way to solve this is to use integrals, differential equations and the Euler-Lagrange formula, all things which are firmly into higher education math level, while the other one was much simpler: you just needed to observe that the optimal path is a line. $\endgroup$ – ffao Apr 16 '16 at 3:43
0
$\begingroup$

Rough outline of an answer:

I'm going to assume the optimal answer is in the same format as the original question: that is, we walk upwards up to a height of X, then downwards until the end, circumventing the wall whenever we find it (I'm using 'upwards' and 'downwards' in terms of a 2D diagram perspective, in real life 'left' and 'right').

In half the time, there is no wall, and we walk sqrt(x^2 + 1.5^2) as per in the original question.

25% of the time, the wall will show up on our upwards path, on average at the 0.75 mark. In this case, we walk towards X until we reach the wall, then go around it and head downwards the rest of the way.

The remaining 25% of the time the wall will show up on our downwards path, on average at the 2.25 mark. In this case we walk towards X, begin our way down, then go around it and head to the end.

then all that's left is to model the simple geometry and optimize for X.

$\endgroup$
  • $\begingroup$ I tested this solution, and it gets within about 1% of what I got for the optimal solution. My guess is that you could do even better by varying the horizontal position of point X. $\endgroup$ – 2012rcampion Apr 15 '16 at 14:45
  • $\begingroup$ The wall is symmetrical with respect to the AB direct path. That is, it will extend 1 mile "up" and 1 mile "down" so it doesn't matter if you leave A with either an "up" or "down" angle as you will hit the wall at the same distance away from A since it is symmetrical. $\endgroup$ – David James Apr 15 '16 at 14:54
0
$\begingroup$

This might be not the optimal strategy, but at least a full discussion of a strategy, namely the 'try to go from A to B on a straight line, and if the wall appears, walk to its end, and walk straight from there to B' strategy.

So there's 50% chance that the path will be $3$ miles long, and 50% chance it will be not a straight line. In that case $x$ will be any distance you walked until you bumped into a wall. The remaining distance is on the AB-axis is $3-x$. You have to walk $1$ mile to circumvent the wall.

So straight line path: $3$ miles. Random wall (at mile $x$) path: $x + 1 + \sqrt{1^2 + (3-x)^2}$

Example: Wall occurs at $1.78$ miles. Path length: $1.78 + 1 + \sqrt{1^2 + (3-1.78)^2} \approx 4.35$ miles.

With the wall being placed uniformly randomly on the $3$ mile, the average distance with this strategy is $\frac12\cdot3+\frac12\frac{\int_0^3x+1+\sqrt{1+(3-x)^2}\mathrm{d}x}3\approx3.69$ miles

$\endgroup$
  • 1
    $\begingroup$ But you dont have to walk straight from A to B, you can walk at an angle starting from A such as slightly north or slightly south. If the wall was at a fixed location such as the 1.5 mile position, the optimal solution (minimal distance) would NOT be walking straight from A to B until you hit the wall. Walking diagonal would be a shorter path. $\endgroup$ – David James Apr 15 '16 at 13:57
  • 1
    $\begingroup$ You're making no sense, you clearly stated multiple times, "The wall position will not be known until you actually bump it and can be anywhere between A and B and will extend 1 mile in both directions perpendicular to the AB path.". If the position is not known the direct path if obviously the most efficient, especially if you have a 50% chance of getting a straight path. $\endgroup$ – Coma Apr 15 '16 at 13:59
  • $\begingroup$ See this related problem with the restriction of having a fixed position wall midway between A and B. The optimal solution is NOT walking directly from A to B it is walking diagonal from A to about midway up (or down) the wall. puzzling.stackexchange.com/questions/30947/… $\endgroup$ – David James Apr 15 '16 at 14:01
  • 1
    $\begingroup$ @Coma, I'm afraid the calculation for the wall path with your strategy is not correct: Y=3-X, so it should be 1.78 + 1 + sqrt(1^2+(3-1.78)^2) = 4.35 miles $\endgroup$ – elias Apr 15 '16 at 14:04
  • 1
    $\begingroup$ @DavidJames, sure, but your modification of that problem means, that a strategy which was optimal for the fixed-position case is not necessarily optimal for a random-position one. and you still did not clarify the actual distribution of the position. $\endgroup$ – elias Apr 15 '16 at 14:06
-1
$\begingroup$

My solution would involve computer simulation only using a reasonable number of random wall positions (or equally spaced wall positions). For example, I can try wall positions $0.1$ miles from A, $0.2, 0.3... 2.8, 2.9$. To those $29$ points I can try multiple launch angles from A to the wall. That should get me an answer reasonably close to optimal. If the runtime of the program is reasonable I can increase the number of "slices" of the 3 mile distance to more than just $29$ and increase the # of launch angles too.

$\endgroup$
  • $\begingroup$ Why would someone downvote a computer simulation? That is a valid solution method and a reasonable approximation. $\endgroup$ – David James Apr 15 '16 at 16:50
  • 1
    $\begingroup$ I wasn't the one downvoting, but this description seems to be quite vague for me. What is an actual strategy? Is it going in a straight line starting with some $\alpha$ angle? What do you do if there is no wall? I think you should remember, that the strategy could not be chosen according to the actual position of the wall (it is suggested by your words 'launch angles from A to the wall', that you do this), but on the contrary: all the wall positions have to be tested for a given strategy. $\endgroup$ – elias Apr 15 '16 at 17:07
  • $\begingroup$ The program would just try multiple angles leaving from A for random wall positions and choose the best on average. For example, I could try 1 degree, 2 degrees, 3 degrees... and maintain an accumulated total distance walked using those angles and then just choose the best (shortest path) when I am all done. The limit of the angle would be such that I wouldn't "overshoot" the wall in the case where the wall is close to the full 3 miles away from A. Seems like a fairly simple simulation program to write using a general purpose language. I might try it. $\endgroup$ – David James Apr 16 '16 at 2:48
  • $\begingroup$ I calculated that if you keep the "leave" angle from A no more than $18.4$ degrees ($.3218$ radians), then you will never "overshoot" the wall even if it is all the way down close to the $3$ mile distance at B. Since we know the rise and run of the wall at a point very close to B, we can use a maximum rise of $1$ mile and a run of about $3$ miles and ask for the a arctangent of that and we get about $18.4$ degrees. $\endgroup$ – David James Apr 16 '16 at 6:50
  • $\begingroup$ I think it's an important question, that if you left A with, for example 12 degrees, and now you've done 2.8 miles (projected to the AB path), if that should raise your suspicion, that 'maybe we are in that 50%, when the wall did not appear', and it's worth risking turning straight towards B. or would you still keep going straight, until you reach a point which is on the same line as B, perpendicular to the AB path? $\endgroup$ – elias Apr 16 '16 at 7:50

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