You have a one dimensional meterstick that you distribute 100 pointlike ants on, at random locations. Each ant will select randomly to begin walking right or left, and keep walking that direction at until it bumps into another ant. If two ants bump into eachother, they will each turn around and go the other direction. If an ant reaches the end of the meterstick, it will fall off. The ants have a constant speed of 1 cm/s. Given enough time, eventually all of the ants will fall off the stick, and for different initial distributions and choices of initial directions this will take a varying amount of time. What is the theoretical maximum length of time it will take for all the ants to fall of the stick?
So, find the distribution and set of left/right choices that maximizes the time the ants spend on the stick. Or the class of distributions, I suppose, no guarantee that it is unique.
4 comments:
Wait, all your ants choose a RANDOM direction (that is, you don't get to tell them which way to go)?
So even the bestest distributions strategy has a worst case of 100 seconds?
... What if I hate having to integrate over all possible choices to determine the expectations?!
Oh, its theoretical maximum time. Okay.
Wait... isn't this no different then every other ants-walking-and-turning-instantly puzzle?
I'm much less impressed by this puzzle now.
I didn't know there were any other ants-walking-and-turning-instantly puzzle, but if there are, I guess this is the same as them.
Post a Comment