Invisible wall problem
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
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?
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)
August 17th, 2016 at 5:35:37 PM
permalink
Quote: WizardImagine 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...
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
August 17th, 2016 at 5:51:31 PM
permalink
I don't understand how you could walk around the wall?
August 17th, 2016 at 6:11:48 PM
permalink
Quote: rsactuaryI 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)
August 17th, 2016 at 6:16:39 PM
permalink
Quote: WizardIt 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?
August 17th, 2016 at 6:17:52 PM
permalink
You can go outside the square.
August 17th, 2016 at 6:24:13 PM
permalink
As I understand the question, the wall only covers 50% of distance between BD.Quote: rsactuarySorry, 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?
Is the wall one piece or are there gaps?
Simplicity is the ultimate sophistication - Leonardo da Vinci
August 17th, 2016 at 6:24:50 PM
permalink
Quote: rsactuarySorry, 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)
August 17th, 2016 at 6:27:34 PM
permalink
Quote: WizardPlease think inside the box.
August 17th, 2016 at 6:39:06 PM
permalink
Quickly discovered this problem requires trigonometry. I'm out.
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.
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,
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
August 17th, 2016 at 6:52:27 PM
permalink
Quote: ChesterDogIf 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)
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.
August 17th, 2016 at 7:05:33 PM
permalink
Quote: RSQuickly discovered this problem requires trigonometry. I'm out.
I'd get Gorbachev to "Tear down this wall." :-)
DUHHIIIIIIIII HEARD THAT!
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).
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).
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
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
August 17th, 2016 at 8:59:35 PM
permalink
Quote: PeeMcGeeConcurring 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)
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.
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.
August 18th, 2016 at 8:06:28 AM
permalink
Quote: MrGoldenSunI 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 :)
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).
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).
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 older I get, the better I recall things that never happened
