Сколькими способами можно расставить числа 1, 2,. . . , 10 в строку так, что-
бы каждое число, кроме единицы, было больше по крайней мере одного из
своих соседей?
Ответы
Ответ: 512
Пошаговое объяснение:
Пусть число 1 находится на n месте c начала строки, тогда оно находится на m = 11-n месте с конца строки.
Рассмотрим первые n членов, cчитая с начала.
У первого члена a1 c начала есть единственный сосед a2, но тогда остается единственный вариант: a1>a2.
У a2 есть еще один сосед a3, но раз a2<a1, то также остается один вариант: a2 > a3.
Продолжая рассуждения вплоть до an получаем:
a1>a2>a3>a4>... >an-1>an = 1, то есть члены идут в порядке убывания слева направо.
Для m = 11-n чисел с конца все аналогично, то есть они идут в порядке убывания справа налево.
Таким образом, все числа до 1 расположены в порядке убывания, а после 1 уже в порядке возрастания.
То есть, чтобы сформировать такую строку необходимо и достаточно выбрать несколько чисел, которые будут стоять до числа 1 или не выбрать их совсем (1 это и есть первое число) и разместить их в порядке убывания, а все оставшиеся после 1 числа в порядке возрастания.
Иначе говоря, общее число таких способов равно числу способов выбрать любое количество любых чисел из 9 возможных (1 не входит), ибо упорядочить числа можно только одним способом.
То есть для любого из чисел в данном ряду есть две возможности:
число было выбрано или не было выбрано, то есть число способов, включая способ, в котором не выбрано ни одно число равно: 2^9 = 512