5. (1988 Canadian Mathematical Olympiad Training Problem) The sequence $\left\{S_{n}\right\}$ is constructed as follows: $S_{1}=\{1,1\}, S_{2}=\{1,2, 1\}, S_{3}=\{1,3,2,3,1\}$, generally, if $S_{k}=\left\{a_{1}, a_{2}, \cdots, a_{n}\right\}$, then $S_{k+1}=\left\{a_{1}, a_{1}+a_{2}, a_{2}, a_{2}+a_{3}, \cdots, a_{n-1}+a_{n}, a_{n}\right\}$. How many terms in $S_{1988}$ are equal to 1988?
5. Let $\varphi(n)$ be the Euler's function, i.e., the number of natural numbers not exceeding $n$ that are coprime with $n$.

It is easy to see that any two consecutive numbers in $S_{n}$ are coprime, and the larger number is the sum of its two adjacent numbers.
We will prove by mathematical induction that for $n \geqslant 2$, every pair of coprime numbers $a > b$ not exceeding $n$ are adjacent exactly twice in $S_{2}, S_{3}, \cdots, S_{n}$.
By symmetry, since every number in each $S_{t}$ is symmetric about 2, it suffices to prove that $a$ and $b$ are adjacent exactly once to the left of 2. For $n=2$, the conclusion is obvious.
Au
Lin
Yuan
Ke
Mathematics
in
Number
Theory
Assume the conclusion holds for $n-1 (n-1 \geqslant 2)$.
Consider only to the left of 2.
If $a < n$, then $a, b$ are not adjacent in $S_{n}$.
Otherwise, if $a, b$ are adjacent in $S_{n}$, by the construction of $S_{n}$, then $a-b$ and $b$ are in $S_{n-1}$ and adjacent. By the induction hypothesis, $a$ and $b$ are adjacent in $S_{2}, \cdots, S_{n-1}$, thus $a-b, b$ are adjacent in $S_{2}, S_{3}, \cdots, S_{n-2}$. This way, $a-b$ and $b$ are adjacent at least twice to the left of 2 in $S_{2}, \cdots, S_{n-1}$, leading to a contradiction.
Therefore, $a$ and $b$ are adjacent the same number of times in $S_{2}, \cdots, S_{n}$ as in $S_{2}, \cdots, S_{n-1}$, which is once.
If $a = n$, then by the fact that $n-b, b$ are adjacent exactly once in $S_{2}, \cdots, S_{n-1}$, so $n, b$ are adjacent exactly once in $S_{2}, \cdots, S_{n}$.
Thus, the conclusion holds for $n$.
Now consider the first occurrences of $n$ in $S_{2}, \cdots, S_{n}$ (not limited to the left of 2). These are the number of $n$ in $S_{n}$, and their left and right neighbors are less than $n$ (their sum equals $n$), and are coprime with $n$.
By the above argument, the number of left and right neighbors of $n$ is $2 \varphi(n)$, so the number of $n$ in $S_{n}$ is $\varphi(n)$.
The result of this problem is: the number of 1988 in $S_{1988}$ is
$$
\varphi(1988) = \varphi(4) \varphi(7) \varphi(71) = 840.
$$