Well, since you are talking about iterations, it must be that you mean the segment has (n+1) stations where each ants can be, and they take steps of size 1 at each iteration. I'm going to assume no two ants moving in the same direction can occupy the same station on the segment.
Then you can formalize this situation as a state machine with 4^(n + 1) states. It takes this number of states because each station can contain nothing, an ant moving right, an ant moving left, and a pair of ants (one going left, one right) that have just collided. You can think of the states as labeled with (n+1) pairs of bits (LR)_i. Bit L (or R) is 1 iff and only if station i contains an ant moving left (or right). This machine is deterministic. Once you (randomly or otherwise) choose the initial locations of the ants and their initial directions, you have chosen the start state. After that, the evolution of the machine is fully determined. If you think about it for a while you'll also see the state machine graph is a DAG, and the final state of every path in the dag is a single sink corresponding to no ants at all on the segment. I'll let you figure out how to prove this. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
