wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> The way to heaven
        
(Message started by: JocK on Aug 15^th, 2005, 1:45pm)

Title: The way to heaven
Post by JocK on Aug 15^th, 2005, 1:45pm

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!"

Title: Re: The way to heaven
Post by RiverPhoenix on Aug 15^th, 2005, 8:13pm

psshhh, whatever I'm not going to heaven anyway :-/

Title: Re: The way to heaven
Post by Grimbal on Aug 16^th, 2005, 3:06am

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. :(

Title: Re: The way to heaven
Post by JocK on Aug 16^th, 2005, 4:45am

on 08/16/05 at 03:06:26, 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.... ;D

Title: Re: The way to heaven
Post by River Phoenix on Aug 16^th, 2005, 6:50am

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.

Title: Re: The way to heaven
Post by JocK on Aug 16^th, 2005, 10:26am

on 08/16/05 at 06:50:08, River Phoenix wrote:

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.

Title: Re: The way to heaven
Post by Earendil on Aug 16^th, 2005, 12:53pm

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

Title: Re: The way to heaven
Post by River Phoenix on Aug 16^th, 2005, 1:13pm

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/8), ... . 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.

Title: Re: The way to heaven
Post by Eigenray on Aug 16^th, 2005, 1:36pm

A general strategy is walk r₁ right, go back to 0, walk r₂ left, then back to 0, walk r₃ right, go back, etc. The worst cases occur when D=r_n+epsilon, and in the "wrong" direction. In this case the total distance walked is
2(r₁+r₂+...+r_n+r_n+1)+r_n+epsilon,
and the least upper bound for the ratio is
c = 1 + 2*sup_n (r₁+...+r_n+1)/r_n

Since c > r_n+1/r_n for all n, r_n grows at most exponentially. Note also that if r_n is polynomial in n, say of degree k, then r₁+...+r_n+1 is like n^k+1, while r_n is like n^k, so c=infinity, which is no good.

The optimum c is probably obtained when r_n=rⁿ for some r. In this case, we have
c = 1 + 2*sup (rⁿ⁺²-r)/((r-1)*rⁿ)
= 1 + 2*sup (r²-r^1-n)/(r-1)
= 1 + 2r²/(r-1),
which is indeed minimized when r=2, as you can check by differentiation. This gives the value c=9.

Title: Re: The way to heaven
Post by River Phoenix on Aug 16^th, 2005, 1:52pm

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.

Title: Re: The way to heaven
Post by Earendil on Aug 16^th, 2005, 1:59pm

on 08/16/05 at 13:13:30, 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/8), ... . 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)

Title: Re: The way to heaven
Post by Eigenray on Aug 16^th, 2005, 2:28pm

For b, consider a logarithmic spiral r(t)=e^at. The arc length up to time t is given by
L(t) = [int]₀^t sqrt(dr²+r²dt²) = [int] sqrt(a²+1) r dt = sqrt(a²+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(a²+1)/a r(t+2pi).
Since
r(t+2pi)=r(t)e^{2pi a} < De^{2pi a},
this gives a ratio of no more than
sqrt(a²+1)/a e^{2pi 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.

Title: Re: The way to heaven
Post by Barukh on Aug 17^th, 2005, 3:49am

on 08/16/05 at 13:36:03, Eigenray wrote:

The optimum c is probably obtained when r_n=rⁿ for some r.

on 08/16/05 at 13:59:58, 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.

Title: Re: The way to heaven
Post by TenaliRaman on Aug 17^th, 2005, 4:44am

I think we have solved something remotely similar to this before but in the CS section,
Best Strategy for Searching in a Plane (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1072265611)

-- AI

Title: Re: The way to heaven
Post by Eigenray on Aug 17^th, 2005, 11:25am

on 08/16/05 at 13:59:58, Earendil wrote:

This way you only get the worse case half the time

For convenience let's start with a step of size r₀=1, ..., r_n=rⁿ.

If we randomly pick a direction at the beginning, and D=r^k+epsilon, then we will always travel
2(1+r+r²+...+r^k)=2(r^k+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 2r^k+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
r_n=arⁿ
where a is chosen randomly, say between 1 and r, pick a random direction to start, and thereafter alternate. So suppose D=br^k, with 1<=b<r, so that
r_k-1<r^k<=D < r^k+1 < r_k+1.
Then we always travel the distance
D + 2a(1+r+...+r^k-1)= D + 2a(r^k-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
2ar^k 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(r^k+r^k+1).
Putting this all together gives a ratio of
1 + a/D [ 2(r^k-1)/(r-1) + r^k + 1_{a<b}(r^k+r^k+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=r^u, where u is uniform in (0,1). Write b=r^v (which is fixed while calculating the expectation). Then {a<b}={u<v}, and
E(a)=[int]₀¹r^udu = (r-1)/log r,
E(a*1_{a<b})=[int]₀^v r^udu = (r^v-1)/log r = (b-1)/log r.
Using these values, the expected value of the ratio (for D=br^k fixed) becomes
1 + 1/(D log r) [ 2(r^k-1) + r^k(r-1) + (b-1)(r^k+r^k+1) ]
= 1 + [ br^k(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 = e^1+s
se^s=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.