|
||
Title: Landing in the woods Post by jollytall on Mar 22nd, 2006, 11:04am You land with a parachute somewhere in a stripe of wood with total loss of direction. The stripe is 1 Km (or mile if you prefer) in width and very long. You want to get out but because of the darkness (night, too many trees, or whatever you prefer) you only know that you are out when you really are. Q: How long do you have to walk (and in what path/shape) to surely get out with the shortest distance of walk? |
||
Title: Re: Landing in the woods Post by Sjoerd Job Postmus on Mar 22nd, 2006, 1:04pm My guess would be that walking a total of 2 sqrt(2) units would be enough. Walk sqrt(2) units, if not out yet, turn 90 degrees - any direction - and continue walking, another sqrt(2) units, and you're out for sure. But, that's not a certain shortest distance. Maybe it could be optimized. I don't know how though. The optimal method can not be less then 1 unit, worst-case. |
||
Title: Re: Landing in the woods Post by towr on Mar 22nd, 2006, 3:05pm I think [hide]a spiral[/hide]would work best. |
||
Title: Re: Landing in the woods Post by JocK on Mar 23rd, 2006, 2:47am By using a path based on the two sides of a [hide]Reulieux triange[/hide], both extended with straight line pieces, I can do in 2[pi]/3 + 2 - [sqrt]3 or approximately 2.36 km. One can do better though... |
||
Title: Re: Landing in the woods Post by Grimbal on Mar 23rd, 2006, 3:02am Following [hide] the 2 sides of an equilateral triangle with side sqrt(4/3) [/hide] would work. You are out in [hide] 2.3094 [/hide] km. |
||
Title: Re: Landing in the woods Post by JocK on Mar 23rd, 2006, 3:19am I can do better than 4/[sqrt]3... I wonder what solution jollytall has in mind that justifies placing this in 'easy'... ::) 8) Nice problem though..! |
||
Title: Re: Landing in the woods Post by Grimbal on Mar 23rd, 2006, 3:37am on 03/23/06 at 03:19:47, JocK wrote:
Climb on a tree? |
||
Title: Re: Landing in the woods Post by Grimbal on Mar 23rd, 2006, 4:12am on 03/23/06 at 03:19:47, JocK wrote:
Like [hide] 2.2870 [/hide] ? |
||
Title: Re: Landing in the woods Post by JocK on Mar 23rd, 2006, 4:57am on 03/23/06 at 04:12:02, Grimbal wrote:
More like [hide]2.2820[/hide]... and still open for further optimisation... :o |
||
Title: Re: Landing in the woods Post by JocK on Mar 23rd, 2006, 5:12am OK, let me post my optimum solution so far: (no need for hiding :P ) 1) Take your GPS. Manually set the Northing to zero and the Easting to -530.9 m. 2) Walk in a straight line to the point with Northing 455.4 m and Easting -368.4 m. 3) From there, walk in a straight line to the point with Northing 1000 m and Easting 0.0 m 4) From there, walk in a straight line to the point with Northing 455.4 m and Easting 368.4 m. 5) From there, walk in a straight line to the point with Northing 0 m and Easting 530.9 m Don't keep your eyes fixed on the GPS: if you look around, at some point you will notice you have left the forrest! 8) |
||
Title: Re: Landing in the woods Post by JocK on Mar 23rd, 2006, 5:26am It seems the shortest curve that can not be covered by a strip of unit width is [hide]a symmetrical V-shape with each leg smooth and consisting of a straight-line segment, a circular arc, and another straight-line segment[/hide]. But too lazy to try... :P |
||
Title: Re: Landing in the woods Post by towr on Mar 23rd, 2006, 5:28am http://www-fs.informatik.uni-tuebingen.de/~reinhard/lake.pdf |
||
Title: Re: Landing in the woods Post by SMQ on Mar 23rd, 2006, 6:00am Cited from the paper towr linked above, and giving the directly applicable result: http://www.cs.uwaterloo.ca/~tmchan/river.pdf |
||
Title: Re: Landing in the woods Post by Speaker on Mar 23rd, 2006, 6:36am Well, I did not click on your links. Not quick enough to figure out the scientific or computer whatevers. Sorry and no disrespect to of course (not that a lack of respect really ever stopped me, of course again). I want to do a drunkards walk. Wander around in a drunken stupor and you will probalby get out in less than a kilometer. The problem of course (again cubd) is that you need to be completely random. If you walk like a half drunk drunkard you will go in circles. You need to be really random. I have only a slight grasp of the science of this (picked it up from R. Heinlein) but I think it wins, if you are random. What say you? |
||
Title: Re: Landing in the woods Post by JocK on Mar 23rd, 2006, 7:06am on 03/23/06 at 06:36:29, Speaker wrote:
I'd say you cannot do much worse than a continuous random walk (limit of stepsize going to zero) as that would require traversing an infinite distance to leave the woods... :o |
||
Title: Re: Landing in the woods Post by jollytall on Mar 23rd, 2006, 9:14am JocK, actually I did not think it was easy, but I had seen so many threads downgraded I would not dare to start anythink higher than "easy". It is better to be upgraded than downgraded. Grimbal, thanks for trusting me, having "Climb on a tree" in mind ;) Actually reading the correct answer, probably I really had something easier in mind from my school years. Maybe it sounded that you landed exactly in the middle of the stripe and you only lost your direction. Or maybe this is even more difficult? Now I am confused. |
||
Title: Re: Landing in the woods Post by JocK on Mar 23rd, 2006, 11:13am on 03/23/06 at 09:14:44, jollytall wrote:
If the forrest strip is 1 km wide and you know you landed in the middle than a (much) shorter path is possible. Walking 1/2 km in a straight line, followed by a right turn and walking half a circle with unit radius centered around the starting point would do the job in (1 + [pi])/2 = 2.071 km. But shorter solutions are possible... |
||
Title: Re: Landing in the woods Post by JocK on Mar 23rd, 2006, 11:19am on 03/23/06 at 11:13:26, JocK wrote:
such as: walk 1/2 km in a straight line, followed by a quarter circle with radius 1/2 km centered around the starting point, and finally 1/2 km in a straight line in opposite direction to the initial straight line. A total of 1 + pi/4 = 1.785 km. |
||
Title: Re: Landing in the woods Post by JocK on Mar 23rd, 2006, 4:17pm Better yet: a path of three straight-line sections that adds up to 1/2 + 2/sqrt(3) = 1.6547 km... (And... open for improvement ... ) |
||
Title: Re: Landing in the woods Post by Speaker on Mar 23rd, 2006, 5:26pm Thanks Jock. Another example of a little knowledge being a dangerous thing. If you happen to see the small pile of bleached bones on your way out of the woods could you contact the executor of my estate? Thanks. |
||
Title: Re: Landing in the woods Post by Icarus on Mar 23rd, 2006, 7:49pm on 03/23/06 at 09:14:44, jollytall wrote:
The riddles I "downgrade" fit the following categories: (1) riddles that quite evidently belong elsewhere - in particular, "who/what am I" riddles posted in other forums. (2) riddles that the poster put in "Hard" because they didn't know the answer, but in fact are well-known, and not particularly difficult for most of our regulars (with the exception of some riddles that are in the "Hard" forum because William put them or related riddles there - for example the "Missing Dollar" riddle). (3) Riddles that I would describe as "Obtuse" or "Obscure" rather than "Hard". An "Obscure" riddle is one that requires particularly specialized knowledge to solve. For example: In nineteen and forty-three, he fought upon the Solomon Sea. In nineteen and forty-four, he was stationed off the Aleutian shore. In nineteen and forty-five, he saw the end of all that jive. Obviously, the answer is my father, Jack Sinclair. What? You didn't know that? Shame on you! As a general rule, I don't hold with Obscure riddles, unless the information is common to a significant subset of our members, such as the mathematical riddles, or the CS ones. An "Obtuse" riddle is one which depends on even more specialized knowledge - knowledge contained only in the proposer's head. Solving the riddle requires guesswork to figure out what the riddler was thinking, not insight. I am not entirely opposed to such riddles. Occasionally they are interesting, particularly if the riddler is trying to lead you down a curious thought-path. More commonly, though, they seem to be vehicles for the riddler's ego trip. Those I find annoying. But in any case, I do not believe an Obtuse or Obscure riddle belongs in the Hard forum, so when they occur I will move them to wherever I feel is most appropriate. This riddle, however, does not fit any of those situations. I would quite happily of left it in the Hard forum. Really, I would prefer that you put riddles where you think they fit best. And if I or towr disagree strongly enough to move it, please don't feel insulted. It is never meant personally. Finally, don't count on being upgraded, no matter how hard the riddle is. We take some care to defend the character of the Hard forum because if we didn't, people would be posting all sorts of things in there, and it would lose its distinctiveness. However, the Easy forum already tends to be a catch-all for all sorts of riddles, so it doesn't have any distinctiveness to defend. Partly for this reason, and partly because of laziness, "Easy" riddles are rarely upgraded to "Medium" or "Hard". ;) |
||
Title: Re: Landing in the woods Post by SMQ on Mar 24th, 2006, 6:54am on 03/23/06 at 16:17:47, JocK wrote:
Combining your last two suggestions yields a solution I believe is optimal: - walk in any direction for a length of 1/[sqrt]3 - turn 120 degrees either direction and walk for a length of 1/(2[sqrt]3) - continue along a circle of radius 1/2 about your starting point until you are facing 180 degrees from the direction you first started walking - walk for a length of 1/2 This gives a total path length of 3/(2[sqrt]3) + [pi]/12 + 1/2 ~= 1.6278 --SMQ |
||
Title: Re: Landing in the woods Post by JocK on Mar 24th, 2006, 7:23am on 03/24/06 at 06:54:58, SMQ wrote:
Indeed: modifying the second half of the second straight segment into a circular arc yields a very efficient path. Nice solution! If there is a better solution than this, it must follow a completely different path... |
||
Title: Re: Landing in the woods Post by JocK on Mar 24th, 2006, 7:29am on 03/24/06 at 06:54:58, SMQ wrote:
So minimising the maximum path length leads to a path that guarentees you to leave the forest in no more than 1627.8 m. But what path minimises the expected distance needed to get you out of this forrest? What is this expected distance? |
||
Title: Re: Landing in the woods Post by Grimbal on Mar 24th, 2006, 1:19pm on 03/24/06 at 06:54:58, SMQ wrote:
After 1/12 of a circle, don't you face 150° from the inital direction? Or do you start with a 30° turn? Except for that, nice solution! Anyway, I wouldn't like to be the one leading a group of people out of the forest using this funny path. - Now, let's turn 120° and continue straight. - Couldn't we just have cut across? - No. - Do you know where we are heading? - No, that's the point. |
||
Title: Re: Landing in the woods Post by SMQ on Mar 24th, 2006, 1:39pm on 03/24/06 at 13:19:24, Grimbal wrote:
Erm, yes; yes you do. And well you should. ;D --SMQ |
||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |