Competition problem — Combinatorics

Library / /21 of 27

Combinatorics Difficulty 6.7 National olympiad Prove it Austria

Let $n \ge 3$ be an integer. A *circle dance* is a dance that is performed according to the following rule: On the floor, $n$ points are marked at equal distances along a large circle. At each of these points is a sheet of paper with an arrow pointing either clockwise or counterclockwise. One of the points is labeled „Start“. The dancer starts at this point. In each step, he first changes the direction of the arrow at his current position and then moves to the next point in the new direction of the arrow.

a) Show: Each circle dance visits each point infinitely often.

b) How many different circle dances are there? Two circle dances are considered to be the same if they differ only by a finite number of steps at the beginning and then always visit the same points in the same order. (The common sequence of steps may begin at different times in the two dances.)

(Birgit Vera Schmidt)

Solution

a) By the pigeon-hole principle, there exists at least one point that is visited infinitely often. If there is another point that is visited only finitely many times, then there are also two neighboring points where one point is visited infinitely many times and the other one finitely many times. But this is not possible because the dancer leaves the point that is visited infinitely many times, alternately in the two directions, so he also visits the neighboring points infinitely many times.

b) Claim: If the dancer takes exactly $k < n$ consecutive steps in one direction right before a change of direction, then he takes at least $k+1$ steps in the other direction after the change of direction.

*Proof:* After the dancer takes $k$ steps in one direction and changes direction, he first takes one step in the other direction. Because of the previous $k$ steps, he has $k$ arrows in front of him that point toward him. This means that he will certainly take $k$ more steps in the other direction than the first one. □

Therefore, after at most $n$ changes of direction, the dancer will take $n$ consecutive steps in the same direction. With the $n$ th step, he visits the first point of the step sequence, flips the arrow and then has only $n - 1$ arrows in front of him pointing towards him, so he will again make $n$ consecutive steps in one direction.
So we have seen, that every dance eventually has a „turning point“. The dancer will dance a whole circle clockwise from the turning point to itself, then a whole circle counter-clockwise from the turning point to itself, and so on.
It is possible to choose the arrow directions at the beginning so that any point can become the turning point. For example, we can have all arrows starting at the start point and continuing counter-clockwise until the desired turning point pointing clockwise and all other arrows pointing counter-clockwise.
Therefore, we have $n$ different dances.

(Birgit Vera Schmidt) ☐

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 and solution reproduced as published; topic and difficulty added by this site.