B5. A sawtooth number is a positive integer with the following property: of each triplet of adjacent digits, the middle digit is either greater than its two neighboring digits or smaller than its two neighboring digits. The numbers 352723 and 314 are, for example, sawtooth numbers, but 3422 and 1243 are not.

How many eight-digit sawtooth numbers are there where each digit is either a 1, a 2, or a 3?

## C-problems

For the C-problems, the answer is not the only thing that matters; there should also be a reasoning that shows that your answer is correct. Solve each C-problem on a separate sheet of paper. Each correctly worked-out C-problem is worth 10 points.

Partial solutions can also earn points. Therefore, write everything clearly and submit your scratch paper (for each problem!) as well.
5. 110

We consider sawtooth numbers using only the digits 1, 2, and 3. We distinguish between so-called ascending sawtooth numbers and descending sawtooth numbers. Sawtooth numbers are ascending if the second digit is greater than the first, and descending if the second digit is smaller. There are six sawtooth numbers of length 2, namely 12, 13, 23, 21, 31, and 32, of which the first three are ascending and the last three are descending.

If we want to create an ascending sawtooth number of length 3, this can be done in two ways. We can either start with the digit 1 and append a descending sawtooth number of length 2. Or we start with the digit 2 and place a descending sawtooth number of length 2 that starts with the digit 3.

In the same way, we can create ascending sawtooth numbers of length 4 by either starting with the digit 1 and appending a descending sawtooth number of length 3, or starting with the digit 2 and appending a descending sawtooth number of length 3 that starts with a 3. Creating ascending sawtooth numbers of length 5, 6, 7, and 8 follows the same pattern.

For descending sawtooth numbers, we have a similar method to create them from shorter ascending sawtooth numbers. Here, we start with the digit 3 and append an ascending sawtooth number, or we start with the digit 2 and append an ascending sawtooth number that starts with a 1.

We now create a table with the number of sawtooth numbers of lengths 2, 3, ..., 8. Due to the above construction of sawtooth numbers from shorter sawtooth numbers, the table can be filled in from left to right.

| length | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| ascending, starting digit 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |
| ascending, starting digit 2 | 1 | 2 | 3 | 5 | 8 | 13 | 21 |
| descending, starting digit 2 | 1 | 2 | 3 | 5 | 8 | 13 | 21 |
| descending, starting digit 3 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |

In total, there are thus $34+21+21+34=110$ sawtooth numbers of length 8.

## C-questions