wolf eat sheep problem: There are 100 equally spaced points around a circle....

[camel]

Hi all,

I've encountered this problem:
============================================================================================
There are 100 equally spaced points around a circle. At 99 of the points, there are sheep, and at 1 point, there is a wolf. At each time step, the wolf randomly moves either clockwise or counterclockwise by 1 point. If there is a sheep at that point, he eats it. The sheep don't move. What is the probability that the sheep who is initially opposite the wolf is the last one remaining?
============================================================================================
This problem is more or less like the gambler ruin problem, but I can not think of a proper way to come up a recursive formula for it. Very appreciate for help.

Thanks.

 

[tkhunny]

Hi all,

I've encountered this problem:
============================================================================================
There are 100 equally spaced points around a circle. At 99 of the points, there are sheep, and at 1 point, there is a wolf. At each time step, the wolf randomly moves either clockwise or counterclockwise by 1 point. If there is a sheep at that point, he eats it. The sheep don't move. What is the probability that the sheep who is initially opposite the wolf is the last one remaining?
============================================================================================
This problem is more or less like the gambler ruin problem, but I can not think of a proper way to come up a recursive formula for it. Very appreciate for help.

Thanks.

Perhaps it is time to start building and theorizing.

What if there are only 2 points, 0 and 1. 100% that #1 will be eaten first and last.
What if there are 4 points, 0, 1 2, 3.
- 1 or 3 goes down.
-- Back to 0 or fail.
--- Same or Different

There you have it.
- 100% Go either way
-- 50% Go Back to 0.
--- 50% Go the opposite way from the first step.
1/4 that #2 will eaten last.
Speculate n = 3 (sheep), (1/2)^(n-1) = (1/2)^2 = 1/4

Your turn. n = 5 (sheep). What do you get? Is it (1/2)^(n-1) = (1/2)^4 = 1/16? If it is, can we prove the pattern continues? If it isn't, what's your next theory?