Author |
Topic: Cross the infinite wall (Read 5614 times) |
|
pscoe2
Junior Member
Gender: 
Posts: 77
|
 |
Cross the infinite wall
« on: May 11th, 2010, 4:41am » |
 Quote  Modify
|
Hi,
I tried to look for a similar already posted riddle but could not find one. I am sorry if this is a repost.
The question is that there is an infinite wall with only 1 gate to get through it.
You are dropped off at a random location and are asked to go to the other side.
What is the best approach for this problem.
thanks,
Puneet
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cross the infinite wall
« Reply #1 on: May 11th, 2010, 4:50am » |
Quote Modify
|
If you go along the wall in one direction there's a 50% chance you will miss the gate, so you'll need to go backwards and forwards in some way.
I don't know what would be optimal, but you could double or triple the distance every time you switch direction.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Cross the infinite wall
« Reply #2 on: May 11th, 2010, 4:54am » |
Quote Modify
|
I haven't given it much thought, but perhaps it involves the properties of a 1-D random walk , where we can place the gate at the origin WLOG. 
However, we would need to prove that no method exists that is more efficient than tossing a fair coin.
|
| « Last Edit: May 11th, 2010, 5:20am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
icecoldcelt
Newbie
Gender:
Posts: 48
|
|
Re: Cross the infinite wall
« Reply #3 on: May 12th, 2010, 8:40am » |
Quote Modify
|
Is it infinitely tall? 
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Cross the infinite wall
« Reply #4 on: May 12th, 2010, 9:18am » |
Quote Modify
|
on May 11th, 2010, 4:54am, ThudanBlunder wrote:| However, we would need to prove that no method exists that is more efficient than tossing a fair coin. |
|
I think that's unlikely to be true. At any given time you have searched some continuous region of the line. Recrossing this region yields no new information--you already know the door isn't there. Therefore, at a minimum, any time spent by a random walk within the region already searched could be better spent either extending the searched region or crossing the region directly.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Cross the infinite wall
« Reply #5 on: May 12th, 2010, 9:42am » |
Quote Modify
|
on May 12th, 2010, 9:18am, SMQ wrote:
I think that's unlikely to be true.
--SMQ |
|
I agree with your reason. (Well, I did say I hadn't given it much thought.)
But I'm not sure if the OP has any reason for putting this in Easy.
on May 12th, 2010, 9:18am, SMQ wrote:
And what does the Q stand for? 
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Cross the infinite wall
« Reply #6 on: May 12th, 2010, 10:07am » |
Quote Modify
|
on May 12th, 2010, 9:42am, ThudanBlunder wrote:| And what does the Q stand for? |
|
Believe it or not: nothing at all. It's just a letter I chose because my actual initials are too generic.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Cross the infinite wall
« Reply #7 on: May 12th, 2010, 11:11am » |
Quote Modify
|
on May 12th, 2010, 10:07am, SMQ wrote:
Believe it or not: nothing at all. It's just a letter I chose because my actual initials are too generic.
--SMQ |
|
Exactly what I said to rmsgrey the other day.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Cross the infinite wall
« Reply #8 on: May 12th, 2010, 3:00pm » |
Quote Modify
|
Choosing randomly from infinity gets messy.
It's fairly easy to come up with an approach that's guaranteed to find the gate after travelling a finite distance provided you start within a finite distance of it - just keep changing direction, walking at least one step further after each turn.
Deciding how to compare different approaches is tricky - you can't talk sensibly about expected time to the gate without knowing more about the random distribution involved...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cross the infinite wall
« Reply #9 on: May 12th, 2010, 3:16pm » |
Quote Modify
|
How would it work out with the gate's location was given by a (known) normal distribution with the mean at the location where you were dropped? So for example going one standard deviation in one direction, and two standard deviations in return would give you over 68.2% chance of having found the gate. (Expected time is a bit more complicated)
What would be the best path to follow?
|
| « Last Edit: May 12th, 2010, 3:17pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pscoe2
Junior Member
Gender:
Posts: 77
|
|
Re: Cross the infinite wall
« Reply #10 on: May 12th, 2010, 11:47pm » |
Quote Modify
|
The way i was thinking this can be done best is to go logrithmically.
Like go n miles in 1 direction and then 2n in other... 4n back in first then 8n in other and so on till you find the gate..
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Cross the infinite wall
« Reply #11 on: May 13th, 2010, 4:26am » |
Quote Modify
|
on May 12th, 2010, 3:16pm, towr wrote:| How would it work out with the gate's location was given by a (known) normal distribution with the mean at the location where you were dropped? |
|
That's one model, but isn't a uniform distribution more natural and less anthropocentric. LOL
on May 12th, 2010, 11:47pm, pscoe2 wrote:
Like go n miles in 1 direction and then 2n in other... 4n back in first then 8n in other and so on till you find the gate..
|
|
With a uniform distribution perhaps a Fibonacci switch is more efficient (as when searching and sorting). 
|
| « Last Edit: May 13th, 2010, 4:31am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cross the infinite wall
« Reply #12 on: May 13th, 2010, 4:29am » |
Quote Modify
|
on May 13th, 2010, 4:26am, ThudanBlunder wrote:
That's one model, but isn't a uniform distribution more natural and less anthropocentric. |
|
Err, how do you imagine getting a uniform distribution on an infinite domain?
And besides, most things in nature seem to follow/approximate a normal distribution. I don't see what's anthropocentric about it.
|
| « Last Edit: May 13th, 2010, 4:30am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Cross the infinite wall
« Reply #13 on: May 13th, 2010, 4:35am » |
Quote Modify
|
on May 13th, 2010, 4:29am, towr wrote:
Err, how do you imagine getting a uniform distribution on an infinite domain?
|
|
Oh dear, I just edited my post to mention that very matter. Then I unedited it.
As for the rest, I suggest you lighten up.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cross the infinite wall
« Reply #14 on: May 13th, 2010, 4:43am » |
Quote Modify
|
*throws molotov cocktail at ThudanBlunder*
Will that do for lighting things up ? 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Cross the infinite wall
« Reply #15 on: May 13th, 2010, 5:19am » |
Quote Modify
|
on May 13th, 2010, 4:43am, towr wrote:*throws molotov cocktail at ThudanBlunder*
Will that do for lighting things up ? |
|
The problem being 1-D does not require us to be.
Anyway, is there any reason to assume that we will be dropped off at the most favourable point on the distribution?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Cross the infinite wall
« Reply #16 on: May 13th, 2010, 6:18am » |
Quote Modify
|
If you aren't dropped at the most favorable point in the distribution, you have to further know the distribution of your starting point (the simplest possibility other than starting at the mean of the door's distribution is probably using the door's distribution as your starting point distribution as well). This further complicates the problem, which already seems fairly hard even in the case where you start at the mean.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Cross the infinite wall
« Reply #17 on: May 13th, 2010, 7:01am » |
Quote Modify
|
on May 13th, 2010, 4:26am, ThudanBlunder wrote:| With a uniform distribution perhaps a Fibonacci switch is more efficient (as when searching and sorting). |
|
Unfortunately, a uniform distribution is sufficiently nonsensical (not only is there 0 probability of the door being at any chosen x, there is 0 probability of it being in any finite neighborhood of x) that it leads straightforwardly to a nonsensical solution:
Assume first a finite uniform distribution of width 2k--i.e. you are told you will be dropped off somewhere within k units of the door with uniform probability. It should be clear that no strategy can beat the obvious one: walk k units in one direction, then at most 2k units back the other way. This gives an expected distance of 3k/2. Any strategy with more reversals involves more average time spent traversing the region already searched and so loses to the simple strategy.
Now we see that in the limit as k approaches infinity, the best strategy approaches: "head out in one direction and walk to infinity," a strategy with only a 50% chance of success.
Seen another way, any strategy will be in steps of the form "cross the already-searched region, then continue onward some distance further." Given a uniform distribution, it would seem obvious that for any useful solution these steps should be scale-invariant--i.e. the further distance is always in the same proportion to the distance already searched--since the real number line is itself scale-invariant.
But now we find that a larger constant of proportionality is always more efficient than a smaller one, and again the limit of the strategy is to head out in one direction and hope it's the right one.
Either way, we find that any strategy on a "uniform" distribution which guarantees finding the door in finite time can be beaten by a strategy with larger steps, and so we conclude that there cannot be any such winning strategy.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Cross the infinite wall
« Reply #18 on: May 14th, 2010, 2:52am » |
Quote Modify
|
It is more natural to think that the door is at a fixed position, and that we have been dropped at a random posiiton with a known distribution (that distribution including our lack of knowledge of the actual distribution).
It is not unreasonable to think the distribution is centered on the door, using the symmetry of the situation. That argument is door-centric.
But then it happens that once you have been dropped, the distribution of the position of the door as compared to your starting position is the reverse distribution of your position as compared to the door's. So the idea that we probably start at the center of the distribution of where the door is is not anthropocentric (or ego-centric).
|
| « Last Edit: May 14th, 2010, 2:54am by Grimbal » |
IP Logged |
|
|
|
monday
Newbie
Posts: 1
|
|
Re: Cross the infinite wall
« Reply #19 on: Jun 10th, 2010, 10:43am » |
Quote Modify
|
Well since the Earth is round, if you walk in one direction, you would eventually come to the gate, right?
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Cross the infinite wall
« Reply #20 on: Jun 11th, 2010, 5:28am » |
Quote Modify
|
Hi, I were not here for a while ... but surely this one was in some of the forums. I would expect towr searching abilities to find it .
Good measure here is comparison of optimal path len and the path len given by the algorithm.
Of course optimal algorithm choses geometric series with negative base and wents alternatively to points with corresponding cordinate (unless the hole is found). The question is to chose the optimal base.
I cannot remember it and I am lazy to count it now, but I suppose it was either -2 or -q (with q the golden ration (1+\sqrt{5})/2).
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_med ium;action=display;num=1206479450
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_har d;action=display;num=1183214402
(Shortly ... q correspond to optimum for sum of turnpoint distances and 2 to optimum for walked path, but the generalisation to k-way search with k/(k-1) is also worth to mention (with \infty for only one way  ))
|
| « Last Edit: Jun 11th, 2010, 5:56am by Hippo » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Cross the infinite wall
« Reply #21 on: Jun 11th, 2010, 8:25am » |
Quote Modify
|
I though about this the other day, and there might such a thing as an uniform distribution over the infinite space.
It looks like this:
Generate a random number r0 uniformly between 0 and 1.
This fixes the door's position as r0 (mod 1). Here mod is understood in reals.
Then start walking according to your favorite strategy.
When you reach a position r0 (mod 1), you select a random integer i1 in {0,1} and add it to r0.
r1 = r0 + 1*i1.
The door position is now fixed as r1 (mod 2).
Etc. When you reach a position rn (mod 2n), you select a random integer in+1 in {0, 1} and extend you range. rn+1 = rn + 2n*in+1.
The door position is now fixed as rn+1 (mod 2n+1).
This process is for all practical purposes equivalent to choosing the door uniformly over an infinite space, except that you never actually know where the door is. You just know where it is not. And it makes it plain obvious that you will never reach it. Or more precisely, you will reach it with probability 0 (which is the probability to flip a coin an infinite number of times and get tails every single time*).
* well, yes, Chuck Norris could do that.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cross the infinite wall
« Reply #22 on: Jun 11th, 2010, 12:52pm » |
Quote Modify
|
It isn't a uniform distribution over all reals for any n, though. And if you let n go to infinity, I don't see how it is any better than taking lim x -> inf x*r0; or avoids the same problems.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Cross the infinite wall
« Reply #23 on: Jun 13th, 2010, 6:02am » |
Quote Modify
|
Well, yes. It is not a distribution in the mathematical sense.
In fact, it illustrates that the limit to infinity of a uniform distribution results in the zero function, which is not a distribution any more.
But at least, you can send the poor guy searching.  This process gives a feel of what it would be like to search for a door located "anywhere on the real line". It shows that the door wouldn't be anywhere you can reach in finite time.
Of course, the fact that it fails to actually place the door anywhere shows that there is something wrong with the concept. But that problem is conveniently hidden at the end of times.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print