Разделы 
Дополнительно
Задача по математике - 1336
2018-12-06 
Заведующая библиотекой, увидев, что 8 томов «Малой энциклопедии козлов» стоят в беспорядке, указала на это библиотекарю. Тот в ответ заявил: «Беспорядок - небольшой, так как каждый том стоит либо на своем месте, либо на соседнем».
Сколькими способами можно расставить тома энциклопедии в соответствии с этим условием?
Решение:
Решим более общую задачу. Пусть энциклопедия состоит из $n$ томов. Количество расстановок $n$-томной энциклопедии, удовлетворяющих условию задачи, обозначим $S_{n}$. Рассмотрим варианты расстановки последнего тома энциклопедии. Если мы его поставим на свое место, то остальные $n - 1$ томов можно поставить на первые $n - 1$ мест $S_{n - 1}$ способом. Если же мы поставим $n$-й том на $(n - 1)$-е место, то $n$-е место мы обязаны занять $(n - 1)$-м томом, при этом количество расстановок остальных $(n - 2)$-х томов на первые $n - 2$ места равно $S_{n - 2}$. Таким образом, $S_{n} = S_{n - 1} + S_{n - 2}$. Ясно, что $S_{1} = 1, S_{2} = 2$ (два тома можно либо поставить правильно, либо поменять местами). Далее, $S_{3} = S_{2} + S_{1} = 2 + 1 = 3; S_{4} = 3 + 2 = 5; S_{5} = 5 + 3 = 8; S_{6} = 8 + 5 = 13; S_{7} = 13 + 8 = 21; S_{8} = 21 + 13 = 34$.
Числовая последовательность ($S_{n}$), полученная в процессе решения задачи, называется последовательностью чисел Фибоначчи. Она задается начальными условиями $S_{1} = 1; S_{2} = 2$ и рекуррентным соотношением $S_{n} = S_{n-1} + S_{n-2}$ для всех $n > 2$, то есть, каждый член этой последовательности, начиная с третьего, равен сумме двух предшествующих.
Ответ: 34 (считал и тот случай, когда все тома стоят на своем месте).
Заведующая библиотекой, увидев, что 8 томов «Малой энциклопедии козлов» стоят в беспорядке, указала на это библиотекарю. Тот в ответ заявил: «Беспорядок - небольшой, так как каждый том стоит либо на своем месте, либо на соседнем».
Сколькими способами можно расставить тома энциклопедии в соответствии с этим условием?
Решение:
Решим более общую задачу. Пусть энциклопедия состоит из $n$ томов. Количество расстановок $n$-томной энциклопедии, удовлетворяющих условию задачи, обозначим $S_{n}$. Рассмотрим варианты расстановки последнего тома энциклопедии. Если мы его поставим на свое место, то остальные $n - 1$ томов можно поставить на первые $n - 1$ мест $S_{n - 1}$ способом. Если же мы поставим $n$-й том на $(n - 1)$-е место, то $n$-е место мы обязаны занять $(n - 1)$-м томом, при этом количество расстановок остальных $(n - 2)$-х томов на первые $n - 2$ места равно $S_{n - 2}$. Таким образом, $S_{n} = S_{n - 1} + S_{n - 2}$. Ясно, что $S_{1} = 1, S_{2} = 2$ (два тома можно либо поставить правильно, либо поменять местами). Далее, $S_{3} = S_{2} + S_{1} = 2 + 1 = 3; S_{4} = 3 + 2 = 5; S_{5} = 5 + 3 = 8; S_{6} = 8 + 5 = 13; S_{7} = 13 + 8 = 21; S_{8} = 21 + 13 = 34$.
Числовая последовательность ($S_{n}$), полученная в процессе решения задачи, называется последовательностью чисел Фибоначчи. Она задается начальными условиями $S_{1} = 1; S_{2} = 2$ и рекуррентным соотношением $S_{n} = S_{n-1} + S_{n-2}$ для всех $n > 2$, то есть, каждый член этой последовательности, начиная с третьего, равен сумме двух предшествующих.
Ответ: 34 (считал и тот случай, когда все тома стоят на своем месте).
