Four, (Full marks 35 points) $a_{1}, a_{2}, \cdots, a_{n}$ is a sequence, for each $k, 1 \leqslant k \leqslant n, a_{k} \in\{1,0\}$. If $a_{k}, a_{k+1}$ are different, write $b_{k}=1$; if $a_{k}, a_{k+1}$ are the same, write $b_{k}=0$. Thus, a new sequence $b_{1}, b_{2}$, $\cdots, b_{n-1}$ is obtained, where $b_{k} \in\{1,0\}(1 \leqslant k \leqslant n-1)$. Repeating this method, a triangular number table composed of the digits 0 and 1 is formed, with the last row containing only one digit. Find the maximum value of the sum of 1s in this number table.
Let $x_{n}$ denote the maximum value of the number in question. When $n=1$, $x_{n}=1$; for $n=2$, $x_{n}=2$; for $n=3$, $x_{n}=4$, because $a_{1}, a_{2}, a_{3}$ have 6 possible permutations: $0,0,0 ; 1,1,1 ; 1,0,1 ; 1,1,0 ; 0,1,1 ; 0, 1,0$; in the 2nd, 3rd, and 4th cases, $x_{3}=4$, and in the other cases, it is less than 4.

Now, we seek the relationship between $x_{n-1}$ and $x_{n}$. Consider the case when $n \geq 3$. The first three rows are:
$$
\begin{array}{llllllll}
a_{1} & a_{2} & a_{3} & \cdots & a_{n} & a_{n+1} & a_{n+2} & a_{n+3} \\
& b_{1} & b_{2} & b_{3} & \cdots & b_{n} & b_{n+1} & b_{n+2} \\
& & c_{1} & c_{2} & \cdots & c_{n} & c_{n+1}
\end{array}
$$

We will prove that in the first three rows, there are at least $n+2$ zeros. If $\left(a_{k}, b_{k}, c_{k}\right)(1 \leqslant k \leqslant n+1)$ contains at least one zero, we group these three numbers together and place them in a box. If $\left(a_{k}, b_{k}, c_{k}\right)$ are all 1s, then $a_{k+1}=0, b_{k+1}=0$, and we group $\left(a_{k}, b_{k}, c_{k}\right)$ and $\left(a_{k+1}, b_{k+1}, c_{k+1}\right)$ together, which contain at least two zeros, and place them in the box. Starting from the first group $\left(a_{1}, b_{1}, c_{1}\right)$, we perform the above operation sequentially. Finally, there are two possibilities: the first possibility is that $\left(a_{n+1}, b_{n+1}, c_{n+1}\right)$ has already been placed in the box, in which case the box contains at least $n+1$ zeros, and the last three numbers $\left(a_{n+2}, a_{n+3}, b_{n+2}\right)$ contain at least one zero; the second possibility is that $\left(a_{n+1}, b_{n+1}, c_{n+1}\right)$, being all 1s, have not been placed in the box, in which case the box contains at least $n$ zeros, but $a_{n+2}=0, b_{n+2}=0$, and the two groups $\left(a_{n+1}, b_{n+1}, c_{n+1}\right)$ and $\left(a_{n+2}, a_{n+3}, b_{n+2}\right)$ contain at least two zeros. Therefore, the first three rows contain at least $n+2$ zeros. In other words, the first three rows contain at most $2 n+4$ ones. Thus, we have
$$
x_{n+3} \leqslant x_{n}+(2 n+4) .
$$

When $n=3 k(k \in N)$, from the above, we have
$$
\begin{array}{l}
x_{3 k} \leqslant x_{3(k-1)}+6(k-1)+4, \\
x_{3(k-1)} \leqslant x_{3(k-2)}+6(k-2)+4, \\
x_{3(k-2)} \leqslant x_{3(k-3)}+6(k-3)+4, \\
\cdots \cdots . \\
x_{6} \leqslant x_{3}+6+4 \\
x_{3}=4 .
\end{array}
$$

Adding the above inequalities, we get
$$
x_{3 k} \leqslant(3 k+1) k \text {. }
$$

When $n=3 k-1$, starting from (1), we can similarly prove
$x_{3 k-1} \leqslant(3 k-1) k$.
When $n=3 k-2$, we have
$x_{3 k-2} \leqslant 3 k(k-1)+1$.
(2), (3), and (6) can be combined into one inequality $x_{n} \leqslant\left[\frac{n(n-1)}{3}+1\right]$. $x_{n}=\left[\frac{n(n+1)+1}{3}\right]$ can be achieved, as shown in the following figure.
(2)
$\begin{array}{lllllllll}1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0\end{array}$
$\begin{array}{llllll}0 & 1 & 0 & 1 & 1 & 0\end{array}$
$\qquad$
$\begin{array}{llllll}1 & 1 & 0 & 1 & 1 & 0\end{array}$
$\begin{array}{llll}1 & 0 & 1 & 1\end{array}$
110
0 1
In each segment of three rows, the first row is a cycle of 1,1,0, and the number of elements in the first row is a multiple of 3. The second row is a cycle of 0,1,1, and the last two digits are 0,1. The third row is a cycle of 1,0,1, and the last digit is 1. In other words, counting backwards, the number of 1s in each row is 1, 1, 2, 3, 3, 4, 5, 5, 6, ..., so
$$
\begin{array}{l} 
x_{3 k} \geqslant(1+1+2)+(3+3+4)+(5+5+6) \\
+\cdots+((2 k-1)+(2 k-1)+2 k) \\
=(3 k+1) k, \\
x_{3 k+1} \geqslant(3 k+1) k+(2 k+1) \\
= 3 k(k+1)+1, \\
x_{3+2} \geqslant x_{3+1}+(2 k+1)=3 k^{2}+5 k+2,(8)
\end{array}
$$

Here $k$ is a positive integer. When $k=0$, (7) and (8) are also correct.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
