Let $a_{1}, a_{2}, \ldots, a_{n}$ be numbers that are either 0 or 1. We define $b_{1}, b_{2}, \ldots, b_{n-1}$ as follows: if $a_{k}=a_{k+1}$, then $b_{k}=0$, otherwise $b_{k}=1$. We repeat this process until we have filled a triangular table. What is the maximum number of 1s that this table can contain?
There is a natural method to construct a table containing many 1s: starting from the bottom. We take 1 as the last row of the table, 01 as the second-to-last row. Then, for each subsequent row, there are only two possibilities (one starting with 0 and one with 1), for example, for row 3, we have the choice between 001 and 110. We then choose the possibility containing the most 1s. This results in the following table:

The calculation allows us to be convinced that in such a table of $n$ rows, the number 1 appears $\left\lfloor\frac{n^{2}+n+1}{3}\right\rfloor$ times. This table also reveals a sort of periodicity with a period of 3, which suggests, in the induction, using the property at rank $n$ to show that at rank $n+3$.

Let's prove by induction on $n$ that the table contains at most $\frac{n^{2}+n+1}{3}$ times the number 1. The initialization (for $n$ being 0, 1, or 2) is obvious. Suppose the property is true at rank $n$, and let's show it at rank $n+3$. Consider the first 3 rows of such a table, which we denote as $a_{1} a_{2} \ldots a_{n+3}, b_{1} b_{2} \ldots b_{n+2}$, and $c_{1} c_{2} \ldots c_{n+1}$. Either the first column $a_{1} b_{1} c_{1}$ contains a 0, or it contains 3 times 1, but then $a_{2}$ and $b_{2}$ are zero, and the first two columns contain at least two zeros. We proceed in this manner from left to right, which shows that either the first $n+1$ columns contain at least $n+1$ zeros (case 1), or the first $n$ columns contain at least $n$ zeros (case 2).

In case 1, since $a_{n+2}, a_{n+3}$, and $b_{n+2}$ cannot all be 1, the first 3 rows contain at least $n+2$ zeros. In the second case, we can assume that the column $a_{n+1} b_{n+1} c_{n+1}$ is composed of three times the number 1 (otherwise, we can reduce to the first case), and therefore $a_{n+2}$ and $b_{n+2}$ are equal to 0, and in this case, too, the first 3 rows contain at least $n+2$ zeros, and thus these 3 rows contain at most $2 n+4$ times the number 1. Now we have

$$
\frac{n^{2}+n+1}{3}+2 n+4=\frac{(n+3)^{2}+(n+3)+1}{3}
$$

which closes the induction.