Найдите число таких подмножеств $%X$% множества $%\big\{1,2,…,15\big\}$%, что никакие два элемента $%X$% не отличаются на $%1$%.

задан 5 Янв '15 11:14

изменен 5 Янв '15 14:01

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
2

Рассмотрим задачу для общего случая, то есть для множества из $%n$% элементов. Обозначим ответ через $%f(n)$%. Легко видеть, что $%f(0)=1$% (одно пустое подмножество), $%f(1)=2$%, $%f(2)=3$%.

Пусть $%n > 2$%. Разберём два случая. Подмножеству либо не принадлежит элемент $%n$%, либо принадлежит. В первом случае у нас имеется ровно $%f(n-1)$% подмножеств. Во втором случае $%n-1$% не принадлежит нашему подмножеству, и тогда мы выбираем подмножество без соседних элементов в $%(n-2)$%-элементном подмножестве, а их имеется $%f(n-2)$%. Итого получается $%f(n)=f(n-1)+f(n-2)$%, то есть это числа Фибоначчи. Осталось подсчитать $%f(15)$%.

ссылка

отвечен 5 Янв '15 11:29

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×427

задан
5 Янв '15 11:14

показан
606 раз

обновлен
5 Янв '15 11:29

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru