Соответствия, сравнения, количества
Ошибка.
Попробуйте повторить позже
Подмножество 
множества 
назовем неизолированным, если для любого элемента в 
найдется элемент, отличающийся от
него на 
Найдите количество 
-элементных неизолированных подмножеств.
Подсказка 1
Обозначим за x_n количество неизолированных подмножеств множества {1,2, ... n}. Попробуем начать вычислять x_(n+1) через x_n. Для начала стоит ответить на вопрос: "Сколько подмножеств S множества {1,2, ...., n+1}, которые не содержат число n+1?"
Подсказка 2
Верно, их x_n! Теперь будем считать количество подмножеств, которые содержат число n + 1. Какое еще число точно содержит такое подмножество?
Подсказка 3
Правильно! Оно еще точно содержит число n. Теперь давайте разобьем наш подсчет на два варианта. Первый, если n - 1 лежит в этом подмножестве, а второй, если n - 1 не лежит в этом подмножестве. Сколько получается множеств в первом и втором случае?
Подсказка 4
Точно! В первом случае получается n - 3 таких подмножеств, а во втором n - 4 таких подмножеств. Следовательно, x_(n+1) = x_n + 2n - 7. Теперь уже можно выписать явную формулу для x_n (для n > 5) через n. Какую?
Подсказка 5
Верно, x_n = 2(5 + 6 + ... + n - 1) - 7(n - 5) + 1. Это выражение можно преобразовать, использую формулу суммы чисел от 1 до n.
Обозначим за 
количество 
-элементных неизолированных подмножеств множества 
Вычислим 
зная 
Рассмотрим произвольное подмножество 
множества 
Если оно не содержит число 
то значит мы его посчитали
уже в 
Поэтому, рассмотрим 
которое содержит число 
По условию оно также должно содержать число
Далее рассмотрим два случая, первый если 
а второй если 
В первом случае, оставшиеся числа
множества 
должны быть вида 
и 
где 
— натуральное число, которое меньше, чем 
Следовательно, в
первом случае количество таких множеств 
равно 
Во втором же случае мы получим, что оставшиеся числа
множества 
будут иметь вид: 
где 
— натуральное число, которое меньше 
Поэтому в этом случаем
количество множеств 
получается равно 
Откуда следует, что 
для 
Заметим, что 
Следовательно,
Это можно преобразовать используя формулу суммы чисел от 
до 
в такое: 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
