# Flag carrying ants in a ring [duplicate]

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.

• I'm willing to bet it'll always recover, but I don't know how to prove. – warspyking Sep 23 '15 at 2:54
• 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. – f'' Sep 23 '15 at 2:55
• When you say "randomly distributed", do they have the same amount of distance in between them? – warspyking Sep 23 '15 at 2:55
• 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... – 2012rcampion Sep 23 '15 at 2:55
• I think this is not a duplicate of the other question. To completely answer this question we need more steps (like in Ross Millikan's answer) than just the single idea in the target dupe. I propose to reopen this. – justhalf Sep 17 '20 at 3:05

## 1 Answer

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.