Problem 1199

I. solution. The polynomial $x^{3}-x-1$ has three distinct complex roots, $\alpha, \beta$, and $\gamma$ (exactly one of which is real); this can be easily proven by the usual function analysis. It is known that in this case, with suitable $A, B, C$ (complex) constants, $a_{n}=A \alpha^{n}+B \beta^{n}+C \gamma^{n}(n=0,1,2, \ldots)$. The values of $A, B, C$ are uniquely determined by the first three terms of the sequence. In our case, $A=B=C=1$, since from the relationships between the roots and coefficients, $\alpha+\beta+\gamma=0=a_{1}, \alpha^{2}+\beta^{2}+\gamma^{2}=(\alpha+\beta+\gamma)^{2}-2(\alpha \beta+\beta \gamma+\gamma \alpha)=0^{2}-2(-1)=2=a_{2}$, and of course $\alpha^{0}+\beta^{0}+\gamma^{0}=3=a_{0}$. Therefore,

$$a_{n}=\alpha^{n}+\beta^{n}+\gamma^{n} \quad(n=0,1,2, \ldots)$$

Using the fact that $\alpha, \beta, \gamma$ satisfy the equation $x^{3}=x+1$ from (1), we get that

$a_{3 n}=(\alpha+1)^{n}+(\beta+1)^{n}+(\gamma+1)^{n}=\sum_{k=0}^{n}\binom{n}{k}\left(\alpha^{k}+\beta^{k}+\gamma^{k}\right)=\sum_{k=0}^{n}\binom{n}{k} a_{k}(1)$ and $a_{n}=\left(\alpha^{3}-1\right)^{n}+\left(\beta^{3}-1\right)^{n}+\left(\gamma^{3}-1\right)^{n}=\sum_{t=0}^{n}(-$

For any prime $p$ and integer $1 \leq r \leq p-1$, $\binom{p}{r}=\frac{p(p-1) \ldots(p-r+1)}{r!}$ is divisible by $p$; therefore, according to (2),

$$a_{p} \equiv a_{0}+(-1)^{p} a_{3 p} \equiv a_{0}+(-1)^{p}\left(a_{0}+a_{p}\right) \quad(\bmod p)$$

For $p>2$, $a_{p} \equiv-a_{p}(\bmod p)$, which implies $p \mid 2 a_{p}$. This leads to the statement of the problem.

II. solution. Let $n$ be a positive integer; inscribe a regular (convex) $A_{1} A_{2} \ldots A_{n} n$-gon in a circle (allowing degenerate "1- and 2-gons" here and in the following). Let $b_{n}$ be the number of convex polygons whose vertices are among $A_{1}, A_{2}, \ldots, A_{n}$, and any two adjacent vertices are second or third neighbors in the original $A_{1} A_{2} \ldots A_{n}$ polygon (one or two original vertices fall between them). We will show that $b_{n}=a_{n}$ ( $n=1$, $2, \ldots)$. Clearly, $b_{1}=0=a_{1}, b_{2}=2=a_{2}, b_{3}=3=a_{3}$; it is sufficient to prove the recursion $b_{n}=b_{n-2}+b_{n-3}$ $(n \geq 4)$. Consider an arbitrary polygon that meets the requirements; one of $A_{n}, A_{n-1}$, and $A_{n-2}$ must appear as a vertex of this polygon, so the two largest numbered vertices of this polygon can be:

2(1) $\quad A_{n}$ and $A_{n-2}$;

(2) $A_{n-1}$ and $A_{n-3}$;

(3) $A_{n-2}$ and $A_{n-4}$; $A_{n}$ and $A_{n-3}$

$A_{n-1}$ and $A_{n-4}$ $A_{n-2}$ and $A_{n-5}$.

If we merge these two vertices and the original vertices between them (i.e., "pull them together"), and then continuously change the numbering of the vertices, we get a polygon inscribed in a regular $n-2$-gon in cases (1), (2), and (3), and in cases (4), (5), and (6), we get a polygon inscribed in a regular $n-3$-gon. All of these latter polygons do indeed occur, and precisely once in this way, so indeed $b_{n}=b_{n-2}+b_{n-3}$, hence $b_{n}=a_{n}$.

Now let $n=p$ be a prime. If $S$ is a properly inscribed polygon, then its rotations by $\frac{360^{\circ}}{p} i$ around the center of the circle $(i=1,2, \ldots, p)$ are also valid. These are all distinct, since if there were two identical ones, then $S$ would be mapped to itself by some $\frac{360^{\circ}}{p} \cdot t$ rotation $(1 \leq t \leq p-1)$. However, the $\frac{360^{\circ}}{p} t j$ rotations would also map $S$ to itself $(j=1,2, \ldots, p-1)$, and among these rotations, there is the $\frac{360}{p}$ rotation; this rotation, however, clearly does not map $S$ to itself.

Therefore, the $a_{p}$ polygons that meet the conditions can be divided into groups of $p$, so $p \mid a_{p}$.