Author |
Topic: The way to heaven (Read 1765 times) |
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
The way to heaven
« on: Aug 15th, 2005, 1:45pm » |
 Quote  Modify
|
1) You have died, and find yourself on the road to heaven. A thick white fog surrounds you. Through the fog you hear St. Peter's voice:
"You have sinned my friend! You have waisted your time on a math riddle forum!! But I give you one last chance. If you can prove the time on the forum was not all waisted, you will be allowed entry to heaven. Listen carefully: the road you are on is very, very long. One direction leads you to infinity, the other leads you to heaven's gate. You will only notice the gate once you pass it. If you get there in the shortest possible travel that guarantees you arrival at that gate, you are allowed in. Good luck!"
2) You have died, and find yourself in a boat at the sea bordering heaven. A thick white fog surrounds you. Through the fog you hear St. Peter's voice:
"You have sinned my friend! You have waisted your time on a math riddle forum!! But I give you one last chance. If you can prove the time on the forum was not all waisted, you will be allowed entry to heaven. Listen carefully: the sea you are sailing is very, very large. In fact, it is a half plane bounded by a straight shoreline of the continent known as heaven. You will only notice the shoreline once you hit it. If you land in heaven in the shortest possible travel that guarantees you to do so, you are allowed in. Good luck!"
3) You have died, and find yourself in that part of space bordering heaven. A thick white gas cloud surrounds you. Through the cloud you hear St. Peter's voice:
"You have sinned my friend! You have waisted your time on a math riddle forum!! But I give you one last chance. If you can prove the time on the forum was not all waisted, you will be allowed entry to heaven. Listen carefully: the space you are in is very, very large. In fact, it is a half space bounded by the plane that forms the entry to heaven. You will only notice this entry once you hit it. If you reach heaven's entry plane in the shortest possible travel that guarantees you to do so, you are allowed in. Good luck!"
|
| « Last Edit: Aug 15th, 2005, 3:25pm by JocK » |
 IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
RiverPhoenix
Guest
|
psshhh, whatever I'm not going to heaven anyway 
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: The way to heaven
« Reply #2 on: Aug 16th, 2005, 3:06am » |
Quote Modify
|
My thought is that you can not do that.
If heaven is 1 mile away, you can guarantee to reach it by walking 1 mile left, and, if you didn't find it, walk 2 miles right, for a maximum of 3 miles.
If heaven is 1 mile and 1 meter away, you can reach it walking max 3 miles and 3 meters.
But if you don't know how far heaven is, you can not guarantee to reach it in 3 miles if it is 1 mile away AND guarantee to reach it in 3 miles and 3 meters if it is 1 mile and 1 meter away.
I'll be damned. 
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: The way to heaven
« Reply #3 on: Aug 16th, 2005, 4:45am » |
Quote Modify
|
on Aug 16th, 2005, 3:06am, Grimbal wrote:My thought is that you can not do that. [..] if you don't know how far heaven is, you can not guarantee to reach it in 3 miles if it is 1 mile away AND guarantee to reach it in 3 miles and 3 meters if it is 1 mile and 1 meter away.
I'll be damned. |
|
C'mon Grimbal, I would expect you to be the first to knock on heaven's gate.... 
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: The way to heaven
« Reply #4 on: Aug 16th, 2005, 6:50am » |
Quote Modify
|
I agree with Grimbal, so far, that your best chance is just to pick a direction and pray to God
Unless there is somehow a best strategy 'on average'? In fact, even heaven was 1 mile away and you got there by walking 3 miles, that's not the fastest way that guarentees you to reach to gate. The fastest way only requires walking 1 mile.
|
| « Last Edit: Aug 16th, 2005, 6:53am by River Phoenix » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: The way to heaven
« Reply #5 on: Aug 16th, 2005, 10:26am » |
Quote Modify
|
on Aug 16th, 2005, 6:50am, River Phoenix wrote:I agree with Grimbal, so far, that your best chance is just to pick a direction and pray to God
Unless there is somehow a best strategy 'on average'? In fact, even heaven was 1 mile away and you got there by walking 3 miles, that's not the fastest way that guarentees you to reach to gate. The fastest way only requires walking 1 mile. |
|
Nope... I am not asking you for the shortest path possible...
I am asking you to do what you and Grimbal deem to be impossible:
to devise a path that for a distance to heaven equal to D (= unknown!!) guarantees you to reach heaven after traversing a distance not exceeding c.D, and to ensure the proportionality constant c is minimal.
|
| « Last Edit: Aug 16th, 2005, 10:32am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Earendil
Newbie
 
Gender:
Posts: 46
|
|
Re: The way to heaven
« Reply #6 on: Aug 16th, 2005, 12:53pm » |
Quote Modify
|
x(t) <- your position at decision t.
x(0) = 0
x(t) = (-2)^(t-1)
When you reach D you will have walked something close to:
2*D
|
|
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: The way to heaven
« Reply #7 on: Aug 16th, 2005, 1:13pm » |
Quote Modify
|
Earendil, I calculate that with your method, the proportionality constant is 9 (in the worst case). Unless I misinterpreted your solution. Nevertheless I agree that it is probably optimal. My interpretation is that we travel some distance in one direction, then in the event of failure we return to the origin and travel double that distance in the opposite direction, etc.
The worst case occurs when you randomly choose the wrong direction to begin with such that:
At some point you are in the right direction and infinitesimally close to x, but not quite there. Then you turn around and go back to 0 and then (infinitesimally less than) 2x, but in the wrong direction. Then we have to go back to the origin again and finally go a distance x in the correct direction to reach the gate.
With these movements alone (beginning with the distance in the correct direction but falling just short of x), we have travelled x + x + 2x + 2x + x = 7x.
Before this point we must have travelled distances of (x/2), (x/4), (x/ , ... . I'll pretend that this pattern continues infinitely (so at the origin we are actually taking steps of size zero). Each of these distances is travelled twice, since we also have to return to the origin. So we've travelled an additional 2 * (.5 + .25 + .125 + ...) * x = 2x. For a total of 9x.
This is almost certainly the optimal solution for question a.
|
| « Last Edit: Aug 16th, 2005, 1:24pm by River Phoenix » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: The way to heaven
« Reply #8 on: Aug 16th, 2005, 1:36pm » |
Quote Modify
|
A general strategy is walk r1 right, go back to 0, walk r2 left, then back to 0, walk r3 right, go back, etc. The worst cases occur when D=rn+epsilon, and in the "wrong" direction. In this case the total distance walked is
2(r1+r2+...+rn+rn+1)+rn+epsilon,
and the least upper bound for the ratio is
c = 1 + 2*supn (r1+...+rn+1)/rn
Since c > rn+1/rn for all n, rn grows at most exponentially. Note also that if rn is polynomial in n, say of degree k, then r1+...+rn+1 is like nk+1, while rn is like nk, so c=infinity, which is no good.
The optimum c is probably obtained when rn=rn for some r. In this case, we have
c = 1 + 2*sup (rn+2-r)/((r-1)*rn)
= 1 + 2*sup (r2-r1-n)/(r-1)
= 1 + 2r2/(r-1),
which is indeed minimized when r=2, as you can check by differentiation. This gives the value c=9.
|
|
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: The way to heaven
« Reply #9 on: Aug 16th, 2005, 1:52pm » |
Quote Modify
|
Thanks, eigenray 
That was my logic as well, but I was too lazy to do math.
Now, for parts 2 and 3, all I can say is that ever since Apple released a multi-button mouse, hell isn't really as hot as it used to be.
|
|
IP Logged |
|
|
|
Earendil
Newbie
Gender:
Posts: 46
|
|
Re: The way to heaven
« Reply #10 on: Aug 16th, 2005, 1:59pm » |
Quote Modify
|
on Aug 16th, 2005, 1:13pm, River Phoenix wrote:
The worst case occurs when you randomly choose the wrong direction to begin with such that:
At some point you are in the right direction and infinitesimally close to x, but not quite there. Then you turn around and go back to 0 and then (infinitesimally less than) 2x, but in the wrong direction. Then we have to go back to the origin again and finally go a distance x in the correct direction to reach the gate.
With these movements alone (beginning with the distance in the correct direction but falling just short of x), we have travelled x + x + 2x + 2x + x = 7x.
Before this point we must have travelled distances of (x/2), (x/4), (x/, ... . I'll pretend that this pattern continues infinitely (so at the origin we are actually taking steps of size zero). Each of these distances is travelled twice, since we also have to return to the origin. So we've travelled an additional 2 * (.5 + .25 + .125 + ...) * x = 2x. For a total of 9x.
This is almost certainly the optimal solution for question a. |
|
River Phoenix, indeed, this was my idea...
But I think you can get a better a.
X ~ Bernoulli (0.5)
x(t) = 2^(t-1) * (-1)^(X+t)
This way you only get the worse case half the time
(And it also doesn't look so sure that 2 is best r)
|
| « Last Edit: Aug 16th, 2005, 2:13pm by Earendil » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: The way to heaven
« Reply #11 on: Aug 16th, 2005, 2:28pm » |
Quote Modify
|
For b, consider a logarithmic spiral r(t)=eat. The arc length up to time t is given by
L(t) = [int]0t sqrt(dr2+r2dt2) = [int] sqrt(a2+1) r dt = sqrt(a2+1)/a r(t).
If the perpendicular to the line is at an angle t, and r(t) < D < r(t+2pi), then you will surely hit it by t+2pi, for a distance
sqrt(a2+1)/a r(t+2pi).
Since
r(t+2pi)=r(t)e2pi a < De2pi a,
this gives a ratio of no more than
sqrt(a2+1)/a e2pi a,
which is minimized for a~0.155, and the ratio is then ~ 17.3.
This can probably be improved by a better estimate of where the line intersects the spiral though.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: The way to heaven
« Reply #12 on: Aug 17th, 2005, 3:49am » |
Quote Modify
|
on Aug 16th, 2005, 1:36pm, Eigenray wrote:| The optimum c is probably obtained when rn=rn for some r. |
|
on Aug 16th, 2005, 1:59pm, Earendil wrote:But I think you can get a better a.
X ~ Bernoulli (0.5)
x(t) = 2^(t-1) * (-1)^(X+t)
This way you only get the worse case half the time
|
|
I didn’t check Earendil’s solution, but it may indicate that in order to find the optimal path one needs to resort to Calculus of Variations.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: The way to heaven
« Reply #13 on: Aug 17th, 2005, 4:44am » |
Quote Modify
|
I think we have solved something remotely similar to this before but in the CS section,
Best Strategy for Searching in a Plane
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: The way to heaven
« Reply #14 on: Aug 17th, 2005, 11:25am » |
Quote Modify
|
on Aug 16th, 2005, 1:59pm, Earendil wrote:| This way you only get the worse case half the time |
|
For convenience let's start with a step of size r0=1, ..., rn=rn.
If we randomly pick a direction at the beginning, and D=rk+epsilon, then we will always travel
2(1+r+r2+...+rk)=2(rk+1-1)/(r-1)
to start with. We will also always travel D at the end. Half the time that's it, but in the unlucky case we waste an additional 2rk+1 going in the wrong direction. Thus the expected ratio is
1+ 2(r-1/D)/(r-1) + r -> 1+ 2r/(r-1) + r,
which ends up being minimized with r=1+sqrt(2) ~ 2.4, for c=4+2sqrt(2) ~ 6.8
What this says is that, for any D, the expected travel length is no more than cD. That is, c is the worst case of the expected ratio.
How else can we randomize this? If we randomly pick a direction each time, I get c=10, which is worse. But we can let
rn=arn
where a is chosen randomly, say between 1 and r, pick a random direction to start, and thereafter alternate. So suppose D=brk, with 1<=b<r, so that
rk-1<rk<=D < rk+1 < rk+1.
Then we always travel the distance
D + 2a(1+r+...+rk-1)= D + 2a(rk-1)/(r-1)
no matter what.
Now, if we went the wrong direction on the k-th step, which happens half the time, then we have wasted
2ark going there and back before hitting it on the (k+1)-th step.
But, if we went the right direction on the k-th step, there are two possibilities. If (b<a), then we hit it, and there's nothing to add. However, if (b>a), we don't hit it until the (k+2)-th step, so we add 2a(rk+rk+1).
Putting this all together gives a ratio of
1 + a/D [ 2(rk-1)/(r-1) + rk + 1_{a<b}(rk+rk+1) ],
where 1_{a<b} is the indicator function which is 1 when a<b, and 0 otherwise.
In order to evaluate this, we need to know E(a) and E(a*1_{a<b}), which both depend on the distribution of a. Due to the exponential nature of the problem, let's take* a=ru, where u is uniform in (0,1). Write b=rv (which is fixed while calculating the expectation). Then {a<b}={u<v}, and
E(a)=[int]01rudu = (r-1)/log r,
E(a*1_{a<b})=[int]0v rudu = (rv-1)/log r = (b-1)/log r.
Using these values, the expected value of the ratio (for D=brk fixed) becomes
1 + 1/(D log r) [ 2(rk-1) + rk(r-1) + (b-1)(rk+rk+1) ]
= 1 + [ brk(1+r) - 2 ] / (D log r)
= 1 + (1+r)/log r - 2/(D log r).
For fixed r, the supremum over D of of this is clearly
c=1+(1+r)/log r.
This is minimized when log r = 1+1/r; if r=1/s, then
-log s = 1+s <-> 1/s = e1+s
ses=1/e <-> s=W(1/e)
so r = 1/W(1/e) ~ 3.59, where W is Lambert's, and
c = 1 + (1+r)/log r = 1 + r ~ 4.59.
*It also makes the calculations easy, and works better than the other distributions I've tried.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove