1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ I'm willing to bet it'll always recover, but I don't know how to prove. $\endgroup$
    – warspyking
    Commented Sep 23, 2015 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''
    Commented Sep 23, 2015 at 2:55
  • $\begingroup$ When you say "randomly distributed", do they have the same amount of distance in between them? $\endgroup$
    – warspyking
    Commented Sep 23, 2015 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
    Commented Sep 23, 2015 at 2:55
  • $\begingroup$ 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. $\endgroup$
    – justhalf
    Commented Sep 17, 2020 at 3:05

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

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