A fun problem, someone told me that there is a physics explanation for this but still lookin for it though
There are people standing around a circle
After a signal, every one starts running around the circle with arbitrary direction (either clockwise or counter clockwise) and with the same velocity . Whenever two of them bump into each other like this
><, they immediately change direction like this
<> and continue running. Is there any possiblity that, after a while, the configuration of these people (the ordered sets of positions and velocity vectors) return to its initial state?
Find the pattern
And by pattern, I mean invariance. Notice that
>< changing to
<> can be seen as either
- The two changes their directions, or
- The two pass through each other and keep moving in their own direction
The second case provides more invariance compare to the first (namely, direction invariance). But yeah, the second case is not provided in the problem statement, so we should introduce some additional entities to add this perspective into argument.
A new variable
Hand each person a ball and tell them that besides turning direction whenever collision happens, exchange the ball. So now we have successfully injected direction invariance into the problem. What’s left is how to properly use this invariance.
Name your variables
Before giving out observations, let’s name some of the entities in this problem:
- Denote the perimeter of this circle
- Denote the running people , in a specific direction along the circle
- Denote the their corresponding balls at the beginning
- Mark the initial positions
- Let the set of positions at time be .
- Let be a function such that is an ordered permutation of where is the position of . In other words, corrects so that it matches . Note that this implies
The very first observation
Now after the signal, watch the balls closely and one thing shall immediately follows: after each period of , returns to . This is equivalent to saying that: after each period of , the set of positions of people is still (because each ball always belong to someone at any given time). The thing we don’t know yet, is which person is standing where.
At this point, it’ll be useful to introduce a few new terms: let’s call the points critical, since they are the points at which . Note that is also critical. Let be an ordered set of velocity vectors defined at each of these critical points, where is the velocity vector of the person who is at position
Now, the question can be formally expressed as follow
Is there a point in time such that and for all ?
In other words, if we define the configuration at time to be , we are finding such that . Let’s assign such configurations (that are identical to the original one) the name original.
Weak, original configurations
Although is a set of vectors, each of which is defined by a length and a direction, we don’t really care about the lengths of these vectors since is constant throughout. Regarding , I can’t really determine which person is standing where at these critical points except for , but there are two other observations to consider:
- The relative position of these people, at any given time, is unchanged. i.e. person is always somewhere in between and at any given time, and the order is also the constant.
- At two consecutive critical points, there will be two persons running in the same direction at , that is because this is the direction of .
From observation and it can be concluded that: the ‘weak’ configurations are original at every critical points. It naturally follows that the original strong configurations , which we are looking for, if there is any, should be amongst these weaker original configurations.
Position set transformation
We know exactly what does to at time (namely, turns to ), it should be sufficient to forget the transformation made by at every other critical points, and shift the focus onto the transformation that turn to .
From , we know these transformations are shift transformations, and since the weak original configurations are identical, the amount of shift is independent of time. In other words . let’s denote the amount of shift , which will be constant throughout as in the logic presented just then.
Let’s apply this shift transformation: Starting from we know the person standing at is . Hence, at the person at should be . Quick, demolish the unknown by setting , the person at is now exactly .
So yes, we found a solution to this problem: . And since this strong configuration is original, it should follows that after another amount of time, another original strong configuration is found. In short, the set of all solutions are: