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

        riddles >> hard >> Blindfolded rabbit catch the turtle
        
(Message started by: ERIC H. ZENGULUS on Jun 22nd, 2004, 6:41pm)
Title: Blindfolded rabbit catch the turtle
Post by ERIC H. ZENGULUS on Jun 22nd, 2004, 6:41pm
Rabbit tries to catch the turtle. They both start from zero point at a infinitely long road. Rabbit can jump two steps at a time while turtule can cover one step at a time. Turtle is travelling always towards one direction while rabbit is blindfolded and will jump left or right randomly.

What are the chances that the rabbit will ever catch the turtle?
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by BNC on Jun 22nd, 2004, 9:59pm
When you say "can move" do you mean the turtle can stay still, or must move continously?
And for the rabbit, can he jump in single steps or must jump two at a time?

And do they start at the same time?
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by ERIC H. ZENGULUS on Jun 22nd, 2004, 10:15pm
the turtle must move all the time towards one direction, let's say, towards right end.

they start at same time.

the rabbit can jump in single steps. In one unit time, the rabbit must jump twice (the two steps are not correlated, that is, do not have to be in the same direction), while turtle must move only one step in one unit time.

when they meet again, it's call a catch.
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by THUDandBLUNDER on Jun 23rd, 2004, 12:36am
After 2k steps let the turtle be +/-2k steps from the origin.  

After 2n steps by the rabbit the probability that it will be (the same positive or negative distance) +/-2k steps from the origin is given by

(1/2)2n * 2nCn+k for k = 1,2,3,...

= (1/2)2n * 2nC3n/2 when n = 2k

Hence required probability = [sum](1/2)4k * 4kC3k for k = 1 to oo

Mathematica gives 0.47368...
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by BNC on Jun 23rd, 2004, 12:52am
If I understand the problem, it's trivially easy...

At t=0, rabbit is at x=0 (notation: R=0|t=0), and the turtle is at x=0 (notation: T=0|t=0).

At t=1, either T=1|t=1 or T=-1|t=1. The rabbit chooses, say, the + direction, thus R=2|t=1 (I assume that if T=1, and the rabbit goes R=1,R=2 in a single move, it's not a catch, otherwise it's even simpler).

If T=1|t=1, then T=2|t=2. The rabbit may jump back and forth (R=3,R=2), hence R=2|t=2, and the turtle is cought.

If at t=2 the turtle is not cought, then T=-2|t=2, R=2|t=2;
Continoue: T=-3|t=3, R=0|t=3; T=-4|t=4, R=-2|t=4; T=-5|t=5, R=-4|t=5; T=-6|t=6, R=-6|t=6.


Thus, the answer (the probablity of catch) is 1.

Opps, missed the word "Randomly"..
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by towr on Jun 23rd, 2004, 2:44am
Do they move simultaneously? Or does first the turtle move then the rabbit, or vice versa?
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by Eric H. Zengulus II on Jun 23rd, 2004, 9:20am
to towr: let's say they move simultaneously


to Thud: there are possiblities that they'll meet more than once ... it's not considered in ur solution ... ???
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by towr on Jun 23rd, 2004, 11:22am
Hmm, so the rabbit is allways behind the turtle untill he catches it (because he can't pass without getting at the same point as the turtle first).

So if we define
a function F(R, T, i) as the chance the the rabbit has of catching the turtle if they're at points R and T respectively, and the rabbit still has i (0 or 1) jump(s) to make.
F(X, X, #) = 1 for X > 0
F(R, T, 0) = 1/2 F(R-1, T+1, 1) + 1/2 F(R+1, T+1, 1)
F(R, T, 1) = 1/2 F(R-1, T, 0) + 1/2 F(R+1, T, 0)
And then we want F(0,0,0)
Which can be easily solved numerically, and probably simplified and/or solved analytically

[edit]
after the first step the rabbit has either caught the turtle immediately (if it make the first step in the same direction as the turtle, which occurs with probability 1/2) or it's is behind by two steps, then takes his second step again and is behind either 1 or 3 steps, both with probability 1/4

So we consider now R < T, take X=T-R and simplify the above recursive formula to

F(0) = 1
F(X) = 1/4 F(X+3) + 1/2 F(X+1) + 1/4 F(X-1)

And we're now looking for 1/4 F(3) + 1/4 F(1) + 1/2  ([ge] 1/2 obviously)
[/edit]
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by Perfection on Jun 23rd, 2004, 2:14pm
I've a question, okay let's say the rabbit starts off going forward (the turtle's direction being forward) and then jumps backward.  Would them being on the same point at t=4/3 count as a catch or would the rabbit just hop over the turtle?
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by THUDandBLUNDER on Jun 23rd, 2004, 2:28pm
It is obvious, to me at least, that they can be coincident only at discrete time intervals of 2T units (T is a positive integer), where the turtle takes 1 step in 1 unit of time. So it doesn't matter who got where first or why.  

::)
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by towr on Jun 23rd, 2004, 2:35pm

on 06/23/04 at 14:14:19, Perfection wrote:
I've a question, okay let's say the rabbit starts off going forward (the turtle's direction being forward) and then jumps backward.  Would them being on the same point at t=4/3 count as a catch or would the rabbit just hop over the turtle?
I don't think there is a t=4/3. It seems to me we're dealing with discrete time steps. But I do think that if the rabbit moves forward on his first step and then back that it's a catch..
(You could also look at it as the rabbit making 1 step at each time-step, and the turtle making a step forward every second time-step)
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by Perfection on Jun 23rd, 2004, 2:48pm

on 06/23/04 at 14:28:04, THUDandBLUNDER wrote:
It is obvious, to me at least, that they can be coincident only at discrete time intervals of 2T units (T is a positive integer), where the turtle takes 1 step in 1 unit of time. So it doesn't matter who got where first or why.  

::)
Well if we're dealing with discrete time steps the meeting would not occur at any integer point or time and so it would not count as a catch.

However if we are dealing with a one after another type system as towr suggests or a continious system then there would be a catch.

I think we'll just have to wait until Eric comes back with the clarification.  (or try working it both ways)
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by towr on Jun 23rd, 2004, 3:34pm
I get a probability of about 0.5803 if the rabbit may catch the turtle with either of his two jumps per turn, and about 0.3214 if it has to be on the last jump.
In the first case that's assuming the turtle has moved to his next position in the same time the rabbit takes for his first jump (otherwise he'd be halfway, and it'd be equal to the second case).

If you'd rather look at it continuously, the results are the same, the first case is equivalent to their paths crossing (i.e. it's also a catch when the rabbit jumps over the turtle), the second to them landing on the same position at integer timesteps.

And of course, once the rabbit has caught the turtle, they stop, and he doesn't have to catch him again and again, which would give  
[sum]i=1[supinfty] 0.321426i [approx] 0.47368 (the number Thud got before)
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by ERIC H. ZENGULUS on Jun 24th, 2004, 2:37pm
maybe this will clarify the problem:

// the following is simulating one match:

int pos_rabbit = 0;
int pos_turtle = 0;
bool caught = false;
while(true)
{
   // turtle advances one step
   pos_turtle ++;

   // blindfolded rabbit makes two steps
   for(int jumps=1;jumps<=2;jumps++)
   {
           if( RandomDirection() == RIGHT )
                   pos_rabbit ++;
           else
                   pos_rabbit --;
 
           if( pos_rabbit >= pos_turtle )
           {
                  caught = true;
                  return;
           }
    }
}
     
Monte Carlo simulation shows that towr is right !!! But anybody has any analytical solution ???                  
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by towr on Jun 24th, 2004, 3:05pm
It's probably easier to use a markovmodel instead of monte-carlo simulation (among other things it converges faster, though it does use a bit more memory).

And with a bit more massaging the function I gave earlier also converges very quickly (just calculating the first 10 values,  setting the rest to 0 already gives the same answer)

I'll see if I can find an analytical solution tomorrow..
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by towr on Jun 25th, 2004, 1:37am
0.5803 seems suspiciously much like 0.5 + 1/4*(0.3214)

So maybe the analytical value is simply 0.5 + 1/4 * t/(t+1), where t = [sum](1/2)4k * 4kC3k for k = 1 to [infty]
(it's not pretty, but hey)
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by THUDandBLUNDER on Jun 25th, 2004, 5:29am

Quote:
Well if we're dealing with discrete time steps the meeting would not occur at any integer point or time and so it would not count as a catch.

Why not?
After 2 discrete time steps of 1 second each, if the turtle is at +2, the rabbit can also be at +2.
Or did I pull my partial answer out of a hat, along with the rabbit?
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by ERIC H. ZENGULUS on Jun 25th, 2004, 1:48pm

on 06/23/04 at 11:22:25, towr wrote:
Hmm, so the rabbit is allways behind the turtle untill he catches it (because he can't pass without getting at the same point as the turtle first).

So if we define
a function F(R, T, i) as the chance the the rabbit has of catching the turtle if they're at points R and T respectively, and the rabbit still has i (0 or 1) jump(s) to make.
F(X, X, #) = 1 for X > 0
F(R, T, 0) = 1/2 F(R-1, T+1, 1) + 1/2 F(R+1, T+1, 1)
F(R, T, 1) = 1/2 F(R-1, T, 0) + 1/2 F(R+1, T, 0)
And then we want F(0,0,0)
Which can be easily solved numerically, and probably simplified and/or solved analytically

[edit]
after the first step the rabbit has either caught the turtle immediately (if it make the first step in the same direction as the turtle, which occurs with probability 1/2) or it's is behind by two steps, then takes his second step again and is behind either 1 or 3 steps, both with probability 1/4

So we consider now R < T, take X=T-R and simplify the above recursive formula to

F(0) = 1
F(X) = 1/4 F(X+3) + 1/2 F(X+1) + 1/4 F(X-1)

And we're now looking for 1/4 F(3) + 1/4 F(1) + 1/2  ([ge] 1/2 obviously)
[/edit]


i've found a solution:
let's consider now that the turtle is one step ahead of you,
based on towr's conclusion we have:
F1 = 1/4 F4 + 1/2 F2 + 1/4;

But note that F2 = F1^2. (Think that there are two turtles before you, so you have to catch one first then catch the next one, thus F2 = F1*F1). Similarly F4 = F1^4. Substitute the we have:
F1 = 1/4 F1^4 + 1/2 F1^2 + 1/4.

And the final answer we're looking for is:
P = 1/2 + 1/4 F1 + 1/4 F3 = 1/2 + 1/4 F1 + 1/4 F1^3

Solve for F1 and then we can compute P, i used matlab
and it gives P = 0.5804.

TO towr, how do u solve ur recursion function numerically? and could you elaborate more on the markov way u mentioned? THANKS !!!
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by Perfection on Jun 26th, 2004, 12:26am

on 06/25/04 at 05:29:02, THUDandBLUNDER wrote:
Why not?
After 2 discrete time steps of 1 second each, if the turtle is at +2, the rabbit can also be at +2.
Or did I pull my partial answer out of a hat, along with the rabbit?
Take a look at the followin scenario
T,R
0,0
1,2
2,0

I'm still confused as to weather that would count as catch
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by THUDandBLUNDER on Jun 26th, 2004, 4:31am

on 06/26/04 at 00:26:43, Perfection wrote:
Take a look at the followin scenario
T,R
0,0
1,2
2,0

I'm still confused as to weather that would count as catch

Yes, that counts as a catch using the method that gives an answer of 0.580...  
My previous interpretation was that it was not a catch; in which case, the answer is 0.3214...
(In fact, the initial question was not well-defined.)  

But (even if the above is not a catch) we can still have, for example:
T,R
0,0
1,2
2,2 (rabbit jumps to 3 and then back again)
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by towr on Jun 27th, 2004, 8:19am

on 06/25/04 at 13:48:13, ERIC H. ZENGULUS wrote:
i've found a solution:
let's consider now that the turtle is one step ahead of you,
based on towr's conclusion we have:
F1 = 1/4 F4 + 1/2 F2 + 1/4;

But note that F2 = F1^2. (Think that there are two turtles before you, so you have to catch one first then catch the next one, thus F2 = F1*F1). Similarly F4 = F1^4. Substitute the we have:
F1 = 1/4 F1^4 + 1/2 F1^2 + 1/4.

And the final answer we're looking for is:
P = 1/2 + 1/4 F1 + 1/4 F3 = 1/2 + 1/4 F1 + 1/4 F1^3

Solve for F1 and then we can compute P, i used matlab
and it gives P = 0.5804.
Very nice, I wish I'd thought of it. :)


Quote:
TO towr, how do u solve ur recursion function numerically?
What I did to approximate the value was first write down F(1) to F(10), then fill in F(X-1) in F(X), and 'solve' for F(X)
f.i.
F(1) = 1/4 F(4) + 1/2 F(2) + 1/4
F(2) = 1/4 F(5) + 1/2 F(3) + 1/4 F(1)
=>
F(2) = 1/4 F(5) + 1/2 F(3) + 1/4 (1/4 F(4) + 1/2 F(2) + 1/4)
=>
7/8 F(2) = 1/4 F(5) + 1/2 F(3) + 1/16 F(4) + 1/16
=>
F(2) = 8/7 (1/4 F(5) + 1/2 F(3) + 1/16 F(4) + 1/16)

and then I set F(11), F(12) and F(13) to 0, and worked back to F(1).


Quote:
and could you elaborate more on the markov way u mentioned? THANKS !!!
One way to look at it is to take a large number of rabbits, and start them all off at the same time, then keep track of what fraction of them is where (and doing what).
So if we start with the array [1/2, 1/4, 0, 1/4, 0 ...], where the first element (array[0]) gives the fraction of rabbits that caught the turtle, and the other elements give the fraction of rabbits at that position.
The next step we would have
[1/2, 0 ...] +
1/4 * [1/4, 0, 1/4, 0 ...] +
1/2 * [0, 0, 1/4, 0, 1/4, 0 ...] +
1/4 * [0, 0, 0, 0, 1/4, 0, 1/4, 0 ...]
=
[9/16, 0, 3/16, 0, 3/16, 0, 1/16, 0 ...]
And we can repeat this same step again and again.
The way to use this to approximate the value is to use a finite array, and a finite number of iterations.

One of the benefits is that each step exactly the right proportion of rabbits jump left, and the right amount jump right, whereas with a simulation based on a random number generator you need a very large amount of trials to approximate this.

Here's the program I wrote

Code:
#include <iostream>
#include <vector>

using namespace std;

int main()
{
 vector<double> bla(10010, 0), bla2(10010, 0);

 double c = 0.5;

 bla[1]=0.25;
 bla[3]=0.25;

 for (int i=0; i < 10000; i++)
 {
   bla2 = vector<double>(10010, 0);
   for (int j=1; j < 10000; j++)
   {
     bla2[j-1]+= bla[j]/4;
     bla2[j+1]+= bla[j]/2;
     bla2[j+3]+= bla[j]/4;
   }
   bla = bla2;
   c += bla[0];
 }

 cout << c << endl;
}
Title: Re: NEW: HARD: Blindfolded rabbit catch the turtle
Post by ERIC H. ZENGULUS on Jun 27th, 2004, 10:04am
Very informative. Thank you.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board