Poll

5 votes (33.33%)
2 votes (13.33%)
3 votes (20%)
1 vote (6.66%)
2 votes (13.33%)
4 votes (26.66%)
3 votes (20%)
3 votes (20%)
1 vote (6.66%)
4 votes (26.66%)

15 members have voted

Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
August 17th, 2016 at 5:07:23 PM permalink
Imagine a square with corners A, B, C, and D. A and C are on opposite corners and are two miles apart. Between B and D there is an invisible wall 50% of the time.

Your goal is to travel on foot between A and C in as little expected time as possible. If you encounter the invisible wall, then you will have to walk around it. If not, you can proceed directly to C. You may walk in any direction you like, except you can't go through the invisible wall if it is there.

Please think inside the box. In other words, don't bother to ask about jumping over the wall, climbing under it, or getting Mexico to pay for the invisible wall.

What strategy should you employ and using that strategy, what is the expected traveling distance?

As usual, please put answers and solutions in spoiler tags. Free copy of my book to the first correct answer that is protected by spoiler tags.

Also, please consider playing the Cooperation Game.

The question for the poll is what strategy would you take?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
MathExtremist
MathExtremist
  • Threads: 88
  • Posts: 6526
Joined: Aug 31, 2010
August 17th, 2016 at 5:35:37 PM permalink
Quote: Wizard

Imagine a square with corners A, B, C, and D. A and C are on opposite corners and are two miles apart. Between B and D there is an invisible wall 50% of the time.

Your goal is to travel on foot between A and C in as little expected time as possible. If you encounter the invisible wall, then you will have to walk around it. If not, you can proceed directly to C. You may walk in any direction you like, except you can't go through the invisible wall if it is there.

Please think inside the box. In other words, don't bother to ask about jumping over the wall, climbing under it, or getting Mexico to pay for the invisible wall.

What strategy should you employ and using that strategy, what is the expected traveling distance?

As usual, please put answers and solutions in spoiler tags. Free copy of my book to the first correct answer that is protected by spoiler tags.

Also, please consider playing the Cooperation Game.

The question for the poll is what strategy would you take?

Walk straight from A toward C. If you hit the wall, wait for it to disappear and continue on your way. The expected traveling distance is exactly 2 miles. The expected time is another story, but that's not the question. :)

edit, on second reading, maybe it *is* the question...

If the wall doesn't ever disappear, it's not there "50% of the time..."
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice." -- Girolamo Cardano, 1563
rsactuary
rsactuary
  • Threads: 29
  • Posts: 2315
Joined: Sep 6, 2014
August 17th, 2016 at 5:51:31 PM permalink
I don't understand how you could walk around the wall?
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
August 17th, 2016 at 6:11:48 PM permalink
Quote: rsactuary

I don't understand how you could walk around the wall?



It goes only so far. Just walk to the end and go around it. You're not confined to the square.

Also, to clarify, the wall doesn't flash on and off. If it is there, you'll have to walk around it.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
rsactuary
rsactuary
  • Threads: 29
  • Posts: 2315
Joined: Sep 6, 2014
August 17th, 2016 at 6:16:39 PM permalink
Quote: Wizard

It goes only so far. Just walk to the end and go around it. You're not confined to the square.

Also, to clarify, the wall doesn't flash on and off. If it is there, you'll have to walk around it.



Sorry, I'm still confused. If it goes from B to D and you can't go outside the square, how do you walk around it?
MrGoldenSun
MrGoldenSun
  • Threads: 3
  • Posts: 252
Joined: Apr 1, 2016
August 17th, 2016 at 6:17:52 PM permalink
You can go outside the square.
Ayecarumba
Ayecarumba
  • Threads: 236
  • Posts: 6763
Joined: Nov 17, 2009
August 17th, 2016 at 6:24:13 PM permalink
Quote: rsactuary

Sorry, I'm still confused. If it goes from B to D and you can't go outside the square, how do you walk around it?

As I understand the question, the wall only covers 50% of distance between BD.

Is the wall one piece or are there gaps?
Simplicity is the ultimate sophistication - Leonardo da Vinci
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
August 17th, 2016 at 6:24:50 PM permalink
Quote: rsactuary

Sorry, I'm still confused. If it goes from B to D and you can't go outside the square, how do you walk around it?



It is only two miles long, if its there at all. I never said you're confined to the square.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
rsactuary
rsactuary
  • Threads: 29
  • Posts: 2315
Joined: Sep 6, 2014
August 17th, 2016 at 6:27:34 PM permalink
Quote: Wizard

Please think inside the box.

RS
RS
  • Threads: 62
  • Posts: 8626
Joined: Feb 11, 2014
August 17th, 2016 at 6:39:06 PM permalink
Quickly discovered this problem requires trigonometry. I'm out.
ChesterDog
ChesterDog
  • Threads: 8
  • Posts: 1480
Joined: Jul 26, 2010
August 17th, 2016 at 6:40:15 PM permalink
If the coordinates of point A are (0,0),
walk toward the point ( 67 * sqrt(2) / 99, 32 * sqrt (2) / 99). If I meet an invisible wall, I would walk along the wall to the edge and then continue to point C. But if I didn't meet an invisible wall at the intermediate point, I would walk to point C directly. My average distance walked would be about 2.62 miles.
MathExtremist
MathExtremist
  • Threads: 88
  • Posts: 6526
Joined: Aug 31, 2010
August 17th, 2016 at 6:47:51 PM permalink
If Z is the center of the square, presumably the actual intent of the question is to get at "what point X on segment BZ should you aim for in order to minimize the average of AX+XC and AX+XB+BC" where XB+BC is how far you have to walk to get around the wall.

In other words, if X is Z, you start out walking directly toward C. Half the time you get there, half the time, you hit the wall and have to walk around half of it before walking down the edge of the square. That averages to 2 + sqrt(2)/2, which is 2.707 miles. But if X is B, then you're walking from A to B to C all the time. That's 2*sqrt(2) or 2.828 miles. The question is what X minimizes that expected distance, and therefore the expected time under the assumption that your walking speed is constant.

Am I reading the intent right?

If so,
Psyche! I've totally forgotten how to solve this kind of problem. Something about trig, which I haven't done since high school...
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice." -- Girolamo Cardano, 1563
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
August 17th, 2016 at 6:52:27 PM permalink
Quote: ChesterDog

If the coordinates of point A are (0,0),

walk toward the point ( 67 * sqrt(2) / 99, 32 * sqrt (2) / 99). If I meet an invisible wall, I would walk along the wall to the edge and then continue to point C. But if I didn't meet an invisible wall at the intermediate point, I would walk to point C directly. My average distance walked would be about 2.62 miles.



Congratulations! The final answer is correct, although I'm not sure I follow your explanation.


Define the coordinates for each point as follows:
A: -1,0
B: 0,1
C 1,0
D 0,-1

From A walk directly to (0,+/- sqrt(8)). Or (0,+0.3536) or (0,-0.3536). If the wall is there, then walk directly to the closest end of it, and then directly to C. Otherwise, just walk directly to C.


I'm pretty sure I gave you a book already. You may have the option for a $10 cash prize instead.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
ChesterDog
ChesterDog
  • Threads: 8
  • Posts: 1480
Joined: Jul 26, 2010
August 17th, 2016 at 7:04:38 PM permalink
Quote: Wizard

...I'm pretty sure I gave you a book already. You may have the option for a $10 cash prize instead.



Thanks!

Yes, you gave me your book. I'll take the $10, and I donate it to the Cooperation Game prize pool.
Ibeatyouraces
Ibeatyouraces
  • Threads: 68
  • Posts: 11933
Joined: Jan 12, 2010
August 17th, 2016 at 7:05:33 PM permalink
Quote: RS

Quickly discovered this problem requires trigonometry. I'm out.


I'd get Gorbachev to "Tear down this wall." :-)
DUHHIIIIIIIII HEARD THAT!
RS
RS
  • Threads: 62
  • Posts: 8626
Joined: Feb 11, 2014
August 17th, 2016 at 7:11:02 PM permalink
I got Z = distance from point (corner?) B.....and the formula you'd want to solve for minimizing Z as:

3 * ( (2-(Z/2)^0.5)^2 + (Z/2) )^0.5 + 2 + Z ) / 2

IOW, this: wolfram alpha link

ie: Walk to the point on the center line (where the invisible wall would be) that is 0.471143 miles away from the corner. If wall appears, walk the 0.471143 miles to corner, then walk the remaining 2 miles along the perimeter of the square. If there is no wall, walk directly to your destination (which will be the same distance you just walked).
PeeMcGee
PeeMcGee
  • Threads: 1
  • Posts: 115
Joined: Jul 23, 2014
August 17th, 2016 at 8:52:34 PM permalink
Concurring with the answer already given, but here’s a little more math.

Let E be the center point of the square (the intersection of the lines AC and BD).
Let F be the point on DE that we want to walk to (which would minimize our total distance).
Let x be the distance of EF.

So we will always walk the length of AF which is (x2+1)1/2

Then,
If there is no wall: we can just walk FC (which is same distance as AF as shown above).
If there is a wall: we have to walk FD (which is 1-x) then DC (which is 21/2).

So the expected distance walked:
(x2+1)1/2 + (1/2)(x2+1)1/2 + (1/2)(1-x+21/2)

To minimize this, set the derivate to zero:
[1.5x/(x2+1)] – 0.5 = 0
x = (1/8)1/2

Therefore, the best strategy is to walk to the point (1/8)1/2 miles from the center.

Plug that into the expected distance to get 1.5(21/2)+0.5 miles.
Or, as stated already, 2.6213 miles
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
August 17th, 2016 at 8:59:35 PM permalink
Quote: PeeMcGee

Concurring with the answer already given, but here’s a little more math.


Let E be the center point of the square (the intersection of the lines AC and BD).
Let F be the point on DE that we want to walk to (which would minimize our total distance).
Let x be the distance of EF.

So we will always walk the length of AF which is (x2+1)1/2

Then,
If there is no wall: we can just walk FC (which is same distance as AF as shown above).
If there is a wall: we have to walk FD (which is 1-x) then DC (which is 21/2).

So the expected distance walked:
(x2+1)1/2 + (1/2)(x2+1)1/2 + (1/2)(1-x+21/2)

To minimize this, set the derivate to zero:
[1.5x/(x2+1)] – 0.5 = 0
x = (1/8)1/2

Therefore, the best strategy is to walk to the point (1/8)1/2 miles from the center.

Plug that into the expected distance to get 1.5(21/2)+0.5 miles.
Or, as stated already, 2.6213 miles



Well put! Not the fastest solution but the best one.

p.s. We need just one more player for the Cooperation game.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
MrGoldenSun
MrGoldenSun
  • Threads: 3
  • Posts: 252
Joined: Apr 1, 2016
August 18th, 2016 at 7:45:03 AM permalink
I like this puzzle. I solved it in a less efficient way at first, for which I needed a numerical solver at one point. I ultimately solved it using the same logic as PeeMcGee.

Initially, I was expressing distances in terms of the angle at which you should walk. So I took the derivative and ended up needing to calculate theta based on the relationship between tan(theta) and sec(theta) which I didn't know how to do analytically.

Then I was skimming the thread and realized I don't need theta at all, I can base it on the distance from the center of the square.
Joeshlabotnik
Joeshlabotnik
  • Threads: 20
  • Posts: 943
Joined: Jul 27, 2016
August 18th, 2016 at 8:06:28 AM permalink
Quote: MrGoldenSun

I like this puzzle. I solved it in a less efficient way at first, for which I needed a numerical solver at one point. I ultimately solved it using the same logic as PeeMcGee.



I solved it by consulting my smartphone. It told me exactly where the wall was. I didn't want to rain on the parade of all you mathematical types :)
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6218
Joined: Jun 22, 2011
August 18th, 2016 at 9:11:33 AM permalink
I will assume that the wall runs all the way from B to D - that is, the only way to get from A to C is to go from A to B (or D) and then to C.

There's no trigonometry involved, but I did use calculus

Let A be at point (0,0), B at (2,0), C at (2,2), and D at (0,2)
Notice that every point on the wall is (x, 2-x)

Assume the strategy is to walk to some point (x, 2-x) where x <= 1, and if the wall is there, walk to B and then to C.
If the wall is not there, the total distance = 2 sqrt(x2 + (2-x)2).
If the wall is there, the total distance = sqrt(x2 + (2-x)2) + (2-x) sqrt(2) + 2.
The expected value of the distance = 1/2 (2 sqrt(x2 + (2-x)2) + sqrt(x2 + (2-x)2) + (2-x) sqrt(2) + 2)
= 1/2 (3 sqrt(x2 + (2-x)2) + 2 sqrt(2) + 2 -x sqrt(2))
= 1/2 (3 sqrt(2) sqrt(x2 - 2x + 2) - sqrt(2) x + 2 + 2 sqrt(2))
= sqrt(3)/2 (3 sqrt(x2 - 2x + 2) - x + sqrt(2) + 1)
The first derivative of this = sqrt(2)/2 (3 (2x - 2) / (2 sqrt(x2 - 2x + 2) - 1))
= sqrt(2)/2 (3 (x -1) / sqrt(x2 - 2x + 2) - 1)
This equals 0 when 3 (x - 1) = sqrt(x2 - 2x + 2)
9 (x - 1)2 = x2 - 2x + 2
8 x2 - 16x + 7 = 0
8 (x - 1)2 = 1
x = 1 +/- sqrt(1/8) = 1 +/- sqrt(2) / 4
However, x > 1, as otherwise 3 (x - 1) < 0, so x = 1 + sqrt(2) / 4
Since the expected value for x = 1 + sqrt(2) / 4 > the expected values for x = 0 and x = 2, this is a maximum.

Head for the point 1 + sqrt(2) / 4 miles in the A to B direction and 1 - sqrt(2) / 4 miles in the A to D direction (or 1 - sqrt(2) / 4 miles in the A to B direction and 1 + sqrt(2) / 4 miles in the A to D direction).

billryan
billryan
  • Threads: 240
  • Posts: 16282
Joined: Nov 2, 2009
August 18th, 2016 at 10:57:07 AM permalink
I'd interview my fellow travelers, figure out which of them knows their shit and follow them. Looks in real life, might as well apply it here.
The difference between fiction and reality is that fiction is supposed to make sense.
  • Jump to: