Author |
Topic: Blindfolded rabbit catch the turtle (Read 1359 times) |
|
ERIC H. ZENGULUS
Newbie
Posts: 11
|
 |
Blindfolded rabbit catch the turtle
« on: Jun 22nd, 2004, 6:41pm » |
 Quote  Modify
|
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?
|
| « Last Edit: Jul 19th, 2004, 7:48pm by Icarus » |
 IP Logged |
|
|
|
BNC
Uberpuzzler
Gender: 
Posts: 1732
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #1 on: Jun 22nd, 2004, 9:59pm » |
Quote Modify
|
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?
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
ERIC H. ZENGULUS
Newbie
Posts: 11
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #2 on: Jun 22nd, 2004, 10:15pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #3 on: Jun 23rd, 2004, 12:36am » |
Quote Modify
|
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...
|
| « Last Edit: Jun 23rd, 2004, 2:54am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #4 on: Jun 23rd, 2004, 12:52am » |
Quote Modify
|
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"..
|
| « Last Edit: Jun 23rd, 2004, 1:07am by BNC » |
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #5 on: Jun 23rd, 2004, 2:44am » |
Quote Modify
|
Do they move simultaneously? Or does first the turtle move then the rabbit, or vice versa?
|
| « Last Edit: Jun 23rd, 2004, 7:12am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eric H. Zengulus II
Guest
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #6 on: Jun 23rd, 2004, 9:20am » |
Quote Modify
 Remove
|
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 ... 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #7 on: Jun 23rd, 2004, 11:22am » |
Quote Modify
|
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]
|
| « Last Edit: Jun 23rd, 2004, 11:47am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Perfection
Newbie
Gender:
Posts: 17
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #8 on: Jun 23rd, 2004, 2:14pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #9 on: Jun 23rd, 2004, 2:28pm » |
Quote Modify
|
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.
|
| « Last Edit: Jun 23rd, 2004, 2:34pm 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: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #10 on: Jun 23rd, 2004, 2:35pm » |
Quote Modify
|
on Jun 23rd, 2004, 2:14pm, 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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Perfection
Newbie
Gender:
Posts: 17
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #11 on: Jun 23rd, 2004, 2:48pm » |
Quote Modify
|
on Jun 23rd, 2004, 2:28pm, 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)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #12 on: Jun 23rd, 2004, 3:34pm » |
Quote Modify
|
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)
|
| « Last Edit: Jun 23rd, 2004, 3:38pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ERIC H. ZENGULUS
Newbie
Posts: 11
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #13 on: Jun 24th, 2004, 2:37pm » |
Quote Modify
|
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
|
| « Last Edit: Jun 24th, 2004, 2:40pm by ERIC H. ZENGULUS » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #14 on: Jun 24th, 2004, 3:05pm » |
Quote Modify
|
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..
|
| « Last Edit: Jun 24th, 2004, 3:06pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #15 on: Jun 25th, 2004, 1:37am » |
Quote Modify
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #16 on: Jun 25th, 2004, 5:29am » |
Quote Modify
|
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?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
ERIC H. ZENGULUS
Newbie
Posts: 11
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #17 on: Jun 25th, 2004, 1:48pm » |
Quote Modify
|
on Jun 23rd, 2004, 11:22am, 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 !!!
|
|
IP Logged |
|
|
|
Perfection
Newbie
Gender:
Posts: 17
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #18 on: Jun 26th, 2004, 12:26am » |
Quote Modify
|
on Jun 25th, 2004, 5:29am, 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
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #19 on: Jun 26th, 2004, 4:31am » |
Quote Modify
|
on Jun 26th, 2004, 12:26am, 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)
|
| « Last Edit: Jun 26th, 2004, 8:09am 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: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #20 on: Jun 27th, 2004, 8:19am » |
Quote Modify
|
on Jun 25th, 2004, 1:48pm, 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;
}
|
|
|
| « Last Edit: Jun 27th, 2004, 8:20am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ERIC H. ZENGULUS
Newbie
Posts: 11
|
|
Re: NEW: HARD: Blindfolded rabbit catch the turtle
« Reply #21 on: Jun 27th, 2004, 10:04am » |
Quote Modify
|
Very informative. Thank you.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print