A positive integer is called zigzag if it satisfies the following three conditions:

- Its digits are non-zero and distinct.
- It does not have three consecutive digits in ascending order.
- It does not have three consecutive digits in descending order.

For example, 14385 and 2917 are zigzag, but 2564 and 71544 are not.

a) Find the largest zigzag number.

b) How many four-digit zigzag numbers exist?
Solution

a) The number 978563412 is, clearly, a zigzag number. Let's show that if $N$ is a zigzag number, then

$$
N \leq 978563412
$$

The maximum number of digits a zigzag number can have is 9. Therefore, we can assume that $N$ is of the form

$$
N=\overline{a b c d e f g h i}
$$

since otherwise, the inequality (.19) would already be satisfied. Moreover, $a=9$ because, otherwise, inequality (.19) would already be satisfied. If $b$ were equal to 8, the next digit $c$ would necessarily be less than 8, and $N$ would not be a zigzag number. Therefore, we have $b<8$. If $b$ were not equal to 7, inequality (.19) would already be satisfied. We can then assume that $b=7$. Thus, $c$ can only be 8. We can then assume that $N$ is of the form

$$
N=\overline{978 d e f g h i}
$$

The digit $d$ cannot be 6, because this would imply that $e<6$ and, thus, $N$ would not be a zigzag number. Therefore, $d<6$ and we can assume that $d=5$, otherwise (.19) would already be satisfied. Necessarily, $e=6$. We can continue the argument and conclude that if $N$ were not equal to 978563412, it would necessarily be smaller.

b) To produce a 4-digit zigzag number, we can use the following procedure:

(1) Choose a subset $\{a, b, c, d\}$ of 4 distinct numbers from $\{1,2,3, \ldots, 9\}$. Let's say $a<b<c<d$.

(2) We can use the digits $\{a, b, c, d\}$ to form 10 distinct zigzag numbers:

$$
\begin{aligned}
& \overline{a c b d}, \overline{a d b c}, \overline{b d a c}, \overline{b c a d}, \overline{c d a b} \\
& \overline{d b c a}, \quad \overline{d a c b}, \overline{c a d b}, \overline{c b d a} \text { and } \overline{b a d c}
\end{aligned}
$$

Every 4-digit zigzag number can be produced by this procedure, and different choices at each step of the procedure produce distinct zigzag numbers. Now we can count them. For the first step of the procedure, we have $\binom{9}{4}$ possible choices, and for the last step, we have 10 choices. Therefore, there are

$$
10 \times \binom{9}{4}=10 \times \frac{9!}{5!4!}=1260
$$

4-digit zigzag numbers.