#### Solution

We will represent numbers by points on a circle of unit length $($numbers with the same fractional part correspond to the same point of the circle, see the comments to the solution of problem 6 for the 10th class of the 1997 mathematical Olympiad$)$. Then the sequence $x_n$ = {an + b} corresponds to a sequence of points on the circle obtained from {b} by an n-fold rotation onto the arc {a}. In this case $p_n = [2x_n]$.

$\\$ $\\$

It is not difficult to see that if $x_n \in [0; {\frac {1} {2}})$, that is, the point $x_n$ lies on the upper semicircle, then $p_n$ = 0; if $x_n$ lies on the lower semicircle, then $p_n$ = 1.

$\\$ $\\$

a) We construct sequences $p_n$, in which all words of length 4, beginning with zero, occur. There are eight such words. The remaining eight words can be obtained by replacing $($a, b$)$ with $($a, b + ½$)$. Indeed, with such a replacement, the points $x_n$ are replaced by diametrically opposite ones, so that $p_n$ is replaced by $1 – p_n$.

$\\$ $\\$

Examples: Consider a and b for which the sequence $x_n$ forms regular figures $($see below$)$.

The correct figures a b.

Necessary words from $ p_n = [2x_n] $ octagon 1/8 0 0000, 0001, 0011, 0111 square 1/4 0 0110 “bi-angle” 1/2 0 0101 triangle 1/3 0 0010

$\\$ $\\$

b) Let us prove that the word 00010 is not realised for any a and b. Let this word be realised. Consider three consecutive terms of the sequence $x_n, x_{n + 1}$ and $x_{n + 2}$.

If points $x_n$ and $x_{n + 2}$ are diametrically opposite, then the next point is obtained from the previous one by turning by $90^{\circ}$, and it is obvious that three consecutive zeroes cannot occur in the sequence $p_n$.

If the points $x_n$ and $x_{n + 2}$ are not diametrically opposite, then they divide the circle into two different arcs. Two situations are possible: $x_{n + 1}$ lies on a larger, and $x_{n + 1}$ lies on a smaller arc.

$\\$ $\\$

Let $x_{n + 1}$ lie on a larger arc, then any other points $x_m, x_{m + 1}$ and $x_{m + 2}$ are located in the same way, since they are obtained from the points $x_n, x_{n + 1}$ and $x_{n + 2}$ by rotation to the same angle. But then three such points cannot be on the upper semicircle, and therefore in the sequence $p_n$ the word 000 does not occur – this is a contradiction.

$\\$ $\\$

Let $x_{n + 1}$ lie on the smaller arc. Then any of the points $x_m, x_{m + 1}$ and $x_{m + 2}$ are located in the same way; therefore, if $x_m$ and $x_{m + 2}$ lie on the upper semicircle, then the point $x_{m + 1}$ lies in the same place, and so the word 010 does not occur in the sequence $p_n$.

$\\$ $\\$

So, we sorted out all of the options, and proved that the word 00010 cannot occur in the sequence.

$\\$ $\\$

A few comments. If $p_n$ is divided into pieces consisting only of zeros or only of ones $($where we should note that a part of zeros is followed by a part made up of ones and a part made up from ones is followed by a part made up of zeros$)$, then the lengths of any two such pieces will differ by not more than 1 This task relates to symbolic dynamics, which is described in the article [#! Smale-horseshoe! #].

#### Answer

See the solution above.