$[$ Problems with constraints $]$

A row of soldiers is called incorrect if no three consecutive soldiers stand in order of height (neither in ascending nor in descending order). How many incorrect rows can be formed from $n$ soldiers of different heights if
a) $n=4$;

b) $n=5$?
Let's place a "+" between neighboring soldiers if the right one is taller than the left one, and a "-" otherwise. According to the condition, the plus and minus signs in the incorrect rows should alternate. It is clear that the number of rows starting with a plus is equal to the number of rows starting with a minus.

a) Let's find the number of rows of the type *+*_*+*. Denote the soldiers by the letters $A, B, C$ and $D$ in decreasing order of height. In the row of the specified type, $A$ can stand in the second or fourth position (after a plus).

In the row ${ }^{*} A^{*+*}$, soldier $B$ can stand in the first or fourth position. In the first case, we have one row - $B A D C$, in the second case - two: $C$ and $D$ can be placed in the remaining positions arbitrarily.

In the row *+*_*A, soldier $B$ can stand only in the second position. There are again two such rows.

In total, we have 5 rows of the type *+*_*+*, and all incorrect rows are twice as many.

b) Let's find the number of rows of the type *+*_*+*_*. Denote the soldiers by the letters $A, B, C, D$ and $E$ in decreasing order of height. Here, $A$ can stand in the second or fourth position. But these cases are symmetric, so it is enough to consider only the first: * $A^{*+*}-*$. In this case, $B$ can stand in the first or fourth position.

In the first case ( $B A^{*+*}{ }^{*}$ ), $C$ can stand only in the fourth position, and $D$ and $E$ can be placed in the remaining positions arbitrarily (2 rows).

In the second case $\left({ }^{*} A^{*} B^{*}\right)$, we have 6 rows: $C, D$ and $E$ can be placed arbitrarily.

In total, we have 8 rows of the type * $A^{*+*-*}$, and all incorrect rows are four times as many.

## Answer

a) 10 rows;
b) 32 rows.