Maths Olympiad Prep

Library / /89 of 91

Combinatorics Difficulty 8.8 Shortlist Prove it India

There are n3n \ge 3 particles on a circle situated at the vertices of a regular nn-gon. All these particles move on the circle with the same constant speed. One of the particles moves in the clockwise direction while all others move in the anti-clockwise direction. When particles collide, that is, they are all at the same point, they all reverse the direction of their motion and continue with the same speed as before.
Let ss be the smallest number of collisions after which all particles return to their original positions. Find ss.

Solutions — 2

Solution 1

The answer is (n1)m(n-1)m' where mm' is the smallest number such that m(n2)2n\frac{m'(n-2)}{2n} is an integer.
More precisely, the answer is
* 2n(n1)2n(n-1) when nn is odd
* n(n1)n(n-1) when nn is divisible by 4
* n(n1)2\frac{n(n-1)}{2} when n2n-2 is divisible by 4. (but the n/2n/2-th point will be the one moving in reverse, not p0p_0)

We first introduce some setup for convenience. We treat points on the circle as [0,2n)[0, 2n) and we use r=r+2nr = r + 2n for any real to refer to points on the circle for convenience. For example, we can use point 1-1 to mean 2n12n - 1 etc. Now, we also assume that it takes any particle 2n2n units of time to go around the entire circle. Thus, if a particle at 00 moves clockwise for time tt then it would reach point tt.

Initially, we let the particles be p0,,pn1p_0, \dots, p_{n-1} with pip_i at point 2i2i.

Now, moving clockwise means the value is increasing and moving anti-clockwise means value is decreasing and finally we assume p0p_0 is the point initially moving anti-clockwise.

Now, let t1>0t_1 > 0 be the total time when for the first time, all particles return to their initial positions.
Correspondingly let t2>0t_2 > 0 be the first time when all particles are equally spaced apart i.e. 2 units apart.

Now, clearly t1t2\frac{t_1}{t_2} is an integer. Thus, we try to find t2t_2.

Observe that if we replace each collision event with the two particles passing through each other, t2t_2 does not change. So for the purposes of calculating t2t_2, we can assume they indeed pass through. Thus, at time t2t_2, there are particles at t2,2+t2,4+t2,,2n2+t2-t_2, 2+t_2, 4+t_2, \dots, 2n-2+t_2. But for them to be equally spaced, this sequence must be t2,2+t2,4+t2,,2n2+t2t_2, 2+t_2, 4+t_2, \dots, 2n-2+t_2. Thus, modulo 2n2n, t2=t2t_2 = -t_2, and the minimum value of t2t_2 that makes this possible is t2=nt_2 = n. Now, we can set t1=nt1t_1 = n \cdot t'_1.

Alternatively, one could have observed that we can look at the positions relative to the clockwise moving particles. Then we just have the anti-clockwise particle moving at speed 2 so it must need nn units of time to return to original position and make n1n-1 collisions in this period.

Now, let us analyze what happens at time nn. There are now particles in positions n,n+2,,n2n, n+2, \dots, n-2. Observe that cyclic order of particles must be preserved as collisions never alter it and finally the collisions only happen in (1,n)(1, n) after the first collision of p0p_0 at point 2n12n - 1 with pnp_n. Thus, p0p_0 does not have any more collisions in the next n1n-1 units of time. Thus, p0p_0 must be at position 2n1+(n1)=n22n - 1 + (n-1) = n - 2. Now, since cyclic order is preserved, pip_i would be at position 2i+n22i + n - 2. Thus, everything has cyclically moved forward by n2n-2.

Thus, in time nn, every particle moves forward by n2n-2 units and there are n1n-1 collisions. Thus, in time nknk, we have (n1)k(n-1)k collisions and every particles moves forward by (n2)k(n-2)k units. Thus, if every particles to their initial position iff 2n(n2)k2n \mid (n-2)k. This is exactly what we desired! \square

Solution 2

Assume the circumference is 2 units, and the particles have speed 1 unit per second. Call a position "good" if the particles are equally spaced. We consider the distance of the particles as positive in the anti-clockwise direction and negative in the clockwise direction.

We first claim that if the position is good, the distance travelled by each particle is the same. Indeed, as the relative positions of the particles does not change (and the particles don't pass through each other), the distance travelled by any particle is sandwiched between the distances travelled by its neighbors, so by cyclicity all the distances must be equal.

Thus, the original position is repeated iff the final position is good and the sum of distances travelled by the particles is 2nl2nl for some integer ll. Since we only care about sum of distances and not the individual particles anymore, we consider the particles to be indistinguishable, and assume that they pass through each other when they collide.

As in the first solution, we can show that the first good position happens after t2=1t_2 = 1 second, with number of collisions being n1n-1 so far. In that 1 unit of time, one particle has travelled a clockwise distance of 1, with n1n-1 others have travelled an anti-clockwise distance of 1. This implies that the total distance travelled in time t2t_2 is n2n-2.

Thus, if t1t2=m\frac{t_1}{t_2} = m, then number of collisions is m(n1)m(n-1), and total distance travelled is m(n2)m(n-2). Thus the particles return to the original position iff 2nm(n2)2n \mid m(n-2), which gives the required answer as seen in the first solution. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.