1
$\begingroup$

This question already has an answer here:

There are $n$ ants randomly distributed on a ring facing clockwise or anticlockwise. Each ant is carrying a flag numbered $1,\ldots,n$. They all start moving around the ring at the same speed (in the direction they were facing).

When they meet they swap flags and turn around and continue walking in the direction they came from (still at the same speed). Effectively a perfect bounce of the ants.

Find a configuration where the initial position is never recovered, or prove that the initial position will always be recovered.

$\endgroup$

marked as duplicate by f'', 2012rcampion, Rohcana, Hackiisan, Cristian Marian Sep 23 '15 at 10:36

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I'm willing to bet it'll always recover, but I don't know how to prove. $\endgroup$ – warspyking Sep 23 '15 at 2:54
  • 7
    $\begingroup$ Is there a significant difference between this and the original puzzle (puzzling.stackexchange.com/questions/1784/…)? When the ants swap flags and turn around, it's equivalent to them passing through each other. $\endgroup$ – f'' Sep 23 '15 at 2:55
  • $\begingroup$ When you say "randomly distributed", do they have the same amount of distance in between them? $\endgroup$ – warspyking Sep 23 '15 at 2:55
  • $\begingroup$ I'm a little confused about the collisions. If the ants swap flags and turn around, then the flags continue in the same direction, and each will make a full orbit at the same speed... $\endgroup$ – 2012rcampion Sep 23 '15 at 2:55
3
$\begingroup$

The initial position will be recovered. The flags keep circulating, so after one circuit they are all back where they started. At that time there will be a permutation of the ants. The ants will be facing the same direction as the one in their location at the start. Some power of the permutation is the identity, so the initial configuration will recur.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.