Found this question online - Tilted Forum Project Discussion Community

Cryptic · 11-19-2004, 05:48 PM

An ant stands in the middle of a circle (3 metres in diameter) and walks in a straight line at a random angle from 0 to 360 degrees. Problem is, it can only walk one metre before it needs a break
(Yes, I know. The lengths I'll go to make a 'problem' for the conditions set in the puzzle =P) To make things even more exasperating, the ant has the memory of a fish and forgets what direction it has just walked in. ( [reader] "You're just making this plot up as you go along to fit in with the problem aren't you?" ). Anyway, after the break, it gets all dizzy and thus chooses another random direction from 0 to 360 in an attempt to escape the circle again).
As you can well imagine, it could escape the circle after just 2 walks (just one break needed). Or... it could take 20,000 walks (19,999 breaks needed)!! There might even be the very slim possibility it might take 20,000^20,000 walks. You can probably guess what I'm going to ask.
What is the average amount of walks required for the ant to escape the circle?

http://www.skytopia.com/project/imath/imath.html

namnori · 11-20-2004, 03:10 AM

as a general rule, random walk problems are very common, and goes as a square root.

BlitzkriegKommt · 12-02-2004, 09:04 PM

Ok Let's say hypothetically; it infinitely and randomly keeps turning 180 degrees every time (It's very unlikely but is possible). So then asking for average is kind of stupid isn't it. Because it can go infinitely. I hope I understand the problem correctly.

keldon · 12-02-2004, 11:32 PM

With a simulation of 10 million trials, I get an average of about 3.53 walks needed. Unfortunately, 3.53 doesn't seem related to 1.5 or the square root of 1.5 in any way I can find.

Anyone have a better way to solve this?

12-03-2004, 07:49 AM

It depends on how random the ant's turning circle is (i.e. might it really turn 180 and go back where it came?)

So you can say with probability 1/360 that it will turn in any particular direction after it's rest.

The first walk is for free, lets say he goes north. At this point, he's only 0.5m from the edge of the circle (closest point), but has to spin his dice. Now the amount of angle he's got at this point that will still allow him to cross the line is (at a guess) more than 180 degrees, but let's keep it at 180 to make it easy.

So 180/360 is 1/2 which means the ant has a 1/2 chance of leaving the circle in 2 gos. So what happens if he doesn't make the line?

Now he could be anywhere in the circle again, but he's probably as close to the edge as he was before (unless he turned round about 180 and walked back to the centre) which means he's probably still got a 1/2 chance of escaping.

So this ant (assuming he didn't already cross the line) now has lets say, a 135/180 chance of being as well off as the first at the end of his walk (i.e. around 1m away from the centre with only 0.5m left to go) These ants are the ones with a chance to leave next go.

So 45/180 ants get it wrong and go the wrong way, while 135/180 ants are back in a similar position as before. (i.e. their next go they have a 1/2 chance of escaping, and a 45/180 chance of ending up in the worst state possible i.e. back at the centre of the circle) These are the ones who have to stay for another walk.

Ok, so with those things in mind (yes, we've simplified the whole thing grossly, but it ought to work out) lets take 1000 ants and time them according to our simple calculations.

So every step, there are
some ants that can escape
some that cant
of the ants that can escape
some will escape
some wont escape, but have another go next time
some wont escape and go in totally the wrong direction

Code:

Walk        Total          Can Exit          Must Wait       Did Exit          Might Next    Can't Next
1          1000.0               0.0          1000.0               0.0            1000.0             0.0
2          1000.0            1000.0             0.0             500.0             375.0           125.0
3           500.0             375.0           125.0             187.5             140.6            46.9
4           187.5             140.6            46.9              70.3              52.7            17.6
5            70.3              52.7            17.6              26.4              19.8             6.6
6            26.4              19.8             6.6               9.9               7.4             2.5
7             9.9               7.4             2.5               3.7               2.8             0.9
8             3.7               2.8             0.9               1.4               1.0             0.3
9             1.4               1.0             0.3               0.5               0.4             0.1
10            0.5               0.4             0.1               0.2               0.1             0.0

So using the probabilities I guestimated before, it looks like 90% of the ants will have escaped by the 5th go - So the average number of walks is going to be a reasonably low number - of course, there are also many different ways to calculate an average.

As for working this out properly, you would need to decide on the probabilities of the ants leaving, not leaving but being able to leave, and not leaving and having to 'miss a go' based on proper trigonometry etc - you should then be able to create a function (i.e. a formula) that described a population curve over time.

The average time would be the point at which the population is halved from it's initial number.

11-19-2004, 05:48 PM	#1 (permalink)
Cryptic Upright	Found this question online An ant stands in the middle of a circle (3 metres in diameter) and walks in a straight line at a random angle from 0 to 360 degrees. Problem is, it can only walk one metre before it needs a break (Yes, I know. The lengths I'll go to make a 'problem' for the conditions set in the puzzle =P) To make things even more exasperating, the ant has the memory of a fish and forgets what direction it has just walked in. ( [reader] "You're just making this plot up as you go along to fit in with the problem aren't you?" ). Anyway, after the break, it gets all dizzy and thus chooses another random direction from 0 to 360 in an attempt to escape the circle again). As you can well imagine, it could escape the circle after just 2 walks (just one break needed). Or... it could take 20,000 walks (19,999 breaks needed)!! There might even be the very slim possibility it might take 20,000^20,000 walks. You can probably guess what I'm going to ask. What is the average amount of walks required for the ant to escape the circle? http://www.skytopia.com/project/imath/imath.html __________________ F=MA 2.998*108ms-1 Ek = 1/2mv2 R D R R

12-03-2004, 07:49 AM	#5 (permalink)
zen_tom Guest	It depends on how random the ant's turning circle is (i.e. might it really turn 180 and go back where it came?) So you can say with probability 1/360 that it will turn in any particular direction after it's rest. The first walk is for free, lets say he goes north. At this point, he's only 0.5m from the edge of the circle (closest point), but has to spin his dice. Now the amount of angle he's got at this point that will still allow him to cross the line is (at a guess) more than 180 degrees, but let's keep it at 180 to make it easy. So 180/360 is 1/2 which means the ant has a 1/2 chance of leaving the circle in 2 gos. So what happens if he doesn't make the line? Now he could be anywhere in the circle again, but he's probably as close to the edge as he was before (unless he turned round about 180 and walked back to the centre) which means he's probably still got a 1/2 chance of escaping. So this ant (assuming he didn't already cross the line) now has lets say, a 135/180 chance of being as well off as the first at the end of his walk (i.e. around 1m away from the centre with only 0.5m left to go) These ants are the ones with a chance to leave next go. So 45/180 ants get it wrong and go the wrong way, while 135/180 ants are back in a similar position as before. (i.e. their next go they have a 1/2 chance of escaping, and a 45/180 chance of ending up in the worst state possible i.e. back at the centre of the circle) These are the ones who have to stay for another walk. Ok, so with those things in mind (yes, we've simplified the whole thing grossly, but it ought to work out) lets take 1000 ants and time them according to our simple calculations. So every step, there are some ants that can escape some that cant of the ants that can escape some will escape some wont escape, but have another go next time some wont escape and go in totally the wrong direction Code: Walk Total Can Exit Must Wait Did Exit Might Next Can't Next 1 1000.0 0.0 1000.0 0.0 1000.0 0.0 2 1000.0 1000.0 0.0 500.0 375.0 125.0 3 500.0 375.0 125.0 187.5 140.6 46.9 4 187.5 140.6 46.9 70.3 52.7 17.6 5 70.3 52.7 17.6 26.4 19.8 6.6 6 26.4 19.8 6.6 9.9 7.4 2.5 7 9.9 7.4 2.5 3.7 2.8 0.9 8 3.7 2.8 0.9 1.4 1.0 0.3 9 1.4 1.0 0.3 0.5 0.4 0.1 10 0.5 0.4 0.1 0.2 0.1 0.0 So using the probabilities I guestimated before, it looks like 90% of the ants will have escaped by the 5th go - So the average number of walks is going to be a reasonably low number - of course, there are also many different ways to calculate an average. As for working this out properly, you would need to decide on the probabilities of the ants leaving, not leaving but being able to leave, and not leaving and having to 'miss a go' based on proper trigonometry etc - you should then be able to create a function (i.e. a formula) that described a population curve over time. The average time would be the point at which the population is halved from it's initial number. Last edited by zen_tom; 12-03-2004 at 07:59 AM..

11-20-2004, 03:10 AM	#2 (permalink)
namnori Upright Location: Tx	as a general rule, random walk problems are very common, and goes as a square root.

12-02-2004, 09:04 PM	#3 (permalink)
BlitzkriegKommt Upright Location: Houston	Ok Let's say hypothetically; it infinitely and randomly keeps turning 180 degrees every time (It's very unlikely but is possible). So then asking for average is kind of stupid isn't it. Because it can go infinitely. I hope I understand the problem correctly.

12-02-2004, 11:32 PM	#4 (permalink)
keldon Upright	With a simulation of 10 million trials, I get an average of about 3.53 walks needed. Unfortunately, 3.53 doesn't seem related to 1.5 or the square root of 1.5 in any way I can find. Anyone have a better way to solve this?