Question

Сколькими способами можно расставить числа 1, 2,. . . , 10 в строку так, что- бы каждое число, кроме единицы, было больше по крайней мере одного из своих соседей?

Answer 1

Ответ: 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

Answer 2

Чтобы каждое число, кроме единицы, было больше по крайней мере одного из своих соседей, у нас есть несколько возможных случаев для размещения чисел:

1. 1 может быть размещена только в начале или в конце строки (или и в начале, и в конце). Остальные числа могут быть размещены в произвольном порядке между 1 и только рядом с 1.

2. 2, 3, 4, 5, 6, 7, 8, 9 и 10 могут быть переставлены между собой в любом порядке.

Сначала найдем количество способов для каждого из этих случаев:

1. Для случая, когда 1 находится только в начале или в конце строки, у нас есть 2 варианта размещения 1. Для оставшихся 9 чисел (2, 3, 4, 5, 6, 7, 8, 9 и 10) можно переставлять как угодно. Это можно сделать 9! способами.

2. Для случая, когда 1 находится как в начале, так и в конце строки, у нас есть 2 варианта размещения 1. Для оставшихся 8 чисел (2, 3, 4, 5, 6, 7, 8, 9 и 10) можно переставлять как угодно. Это можно сделать 8! способами.

Теперь сложим оба случая:

2 * 9! + 2 * 8!

Вычислим это:

2 * 9! + 2 * 8! = 7257600

Итак, существует 7 257 600 способов разместить числа от 1 до 10 в строке так, чтобы каждое число, кроме единицы, было больше по крайней мере одного из своих соседей.