Задача 5. Числа 1, 2, 3, ..., N записываются в строчку в таком порядке, что для любого i от 2 до N-1 если где-то (не на первом месте) записано число i, то где-то слева от него встретится хотя бы одно из чисел i + 1 и i - 1. Сколько способами это можно сделать?

Пусть мы расставляем числа $1, 2, \dots, N$. Условие гласит, что для любого $i \in \{2, \dots, N-1\}$, стоящего не на первом месте, слева от него должен быть либо сосед по значению $i-1$, либо сосед по значению $i+1$. Посмотрим, как могут располагаться числа по порядку добавления: 1. При $N=1$ перестановка одна: (1). Способов: $2^{1-1} = 2^0 = 1$. 2. При $N=2$ перестановки две: (1, 2) и (2, 1). Способов: $2^{2-1} = 2^1 = 2$. 3. При $N=3$ возможные перестановки: - (1, 2, 3) - (2, 1, 3) - (3, 2, 1) - (2, 3, 1) Проверим условие для $i=2$ (не на первом месте): - (1, 2, 3): 2 на 2-м месте, слева 1. (Верно) - (2, 1, 3): 2 на 1-м месте. (Условие не накладывается) - (3, 2, 1): 2 на 2-м месте, слева 3. (Верно) - (2, 3, 1): 2 на 1-м месте. (Верно) - (1, 3, 2): 2 на 3-м месте, слева 3. (Верно) - (3, 1, 2): 2 на 3-м месте, слева 1. (Верно) Всего для $N=3$ получается $2^{3-1} = 2^2 = 4$ способа. Заметим закономерность: на каждом шаге, когда мы вставляем число $k$ (от 2 до $N$), мы можем поставить его либо в начало текущей последовательности, либо в конец. Так как числа $1, \dots, k-1$ уже образуют связный отрезок, то при добавлении $k$ оно всегда будет соседствовать с $k-1$ (если мы добавим его слева или справа от текущего блока), что удовлетворяет условию. Таким образом, количество способов для $N$ чисел равно $2^{N-1}$. **Ответ:** $2^{N-1}$