Ну вот такой, например, еще можно разобрать случай,
такую можно разобрать задачку.
Давайте пусть у нас есть множество мощности 6.
Множество, состоящее из шести элементов.
а1, а2, а3, а4, а5, а6.
Спрашивается, сколькими способами можно выбрать из этого
множества некоторое подмножество, которое состояло бы из четного числа элементов.
Так.
Ну давайте напишем.
Сколькими способами [ПИШЕТ_НА_ДОСКЕ]
можно выбрать подмножество из четного числа элементов.
[ПИШЕТ_НА_ДОСКЕ]
[ПИШЕТ_НА_ДОСКЕ] Ну
в каком-то смысле это вполне типичная тоже задача на применение некоего тождества.
С другой стороны, мы это тождество можем и получить самостоятельно.
Да. Я забыл договориться с вами,
что пустое подмножество — это тоже подмножество из четного числа элементов,
то есть выбор пустого подмножества здесь также включен.
Ну, с одной стороны, можно написать, конечно,
что С из 6 по 0 — это количество как раз способов выбрать пустое подмножество.
Ровно один такой способ — это способ выбрать пустое подмножество.
Дальше можно выбрать подмножество, состоящее из 2 элементов,
и это опять число сочетаний С из 6 по 2.
Дальше можно выбрать подмножество из 4 элементов,
ну и, наконец, из 6.
Ну понятное дело, да?
Можно так.
Почему ж нет?
Но это как-то длинно.
Можно записать то же самое, на самом деле, по-другому, более коротко и более ясно.
Так, что это будет допускать обобщение на случай не только 6, но, скажем,
и 100 элементов, как в предыдущей задаче.
200, 1000, сколько хотите.
Вот.
Ну, как надо рассуждать?
Смотрите, что значит выбрать подмножество отсюда,
состоящее из скольких-то, пусть из четного числа элементов?
Давайте делать следующим образом, поступать следующим образом.
Возьмем элемент а1 и либо положим его в строящееся множество, либо не положим.
Ну давайте напишем.
а1.
Либо положим, либо не положим.
[ПИШЕТ_НА_ДОСКЕ] Два
варианта всего: можно положить, можно не положить.
Абсолютно то же самое скажем относительно элемента а2: можем положить,
а можем не положить.
И так далее, внимание, не вплоть, конечно, до элемента с индексом 6,
а вплоть до элемента с индексом 5.
По поводу элемента а5.
Снова говорим, что вне зависимости от того, как мы осуществляли выбор его
предшественников, то есть клали в строящееся множество или не клали,
вот этот элемент а5 мы тоже либо положим, либо не положим.
То есть тут есть два варианта,
тут есть два варианта и так далее вплоть до а с индексом 5.
И вот в любом из этих вариантов, в любом из последовательностей.
В любой из последовательностей этих вариантов.
То есть я намекаю на правило умножения.
Будет получаться некоторое множество.
Оно то ли содержит элемент а1, то ли не содержит.
То ли содержит элемент а2, то ли не содержит.
И так далее.
То ли содержит а5, то ли не содержит.
Но согласитесь, что в зависимости от того, какие именно элементы оно в итоге
содержит, то множество, которое получится в рамках вот таких вот альтернатив,
в зависимости от того, что мы включим в него, а что не включим,
оно может получиться как четной мощности, то есть как содержащим четное
число объектов, так и содержащим нечетное число объектов.
Например, мы вообще ни один объект могли не включить.
Каждый раз срабатывал второй вариант альтернативы: не клали а1,
не клали а2, не клали а5, получилось множество четной мощности, пустое.
А могло быть по-другому.
Мы положили а1, а дальше ничего не клали.
И, извините, тотчас же получилось, конечно, множество нечетной мощности.
То есть, как бог распорядится.
В зависимости от того,
сколько вариантов той или иной альтернативы у нас здесь выполнено,
получится либо четная мощность, либо нечетная мощность у вот этого множества.
Но смотрите.
Если получилась четная мощность, если получилась
четная мощность,
[ПИШЕТ_НА_ДОСКЕ] то последний элемент, а с индексом 6,
о котором в рамках вот этих альтернатив никакая речь вообще не шла,
то вот этот последний элемент, очевидно, класть в строящееся множество нельзя.
Если мы его положим, получится множество нечетной мощности,
а нас такое не интересовало.
То а6 не кладем в строящееся множество, не кладем.
Иначе, иначе это значит,
что в рамках вот этих альтернатив получилось множество нечетной мощности.
Но нам-то надо набрать четную мощность.
Иначе а6 кладем.
Иначе а6 кладем.
То есть каждой из вот этих вот ситуаций,
которые возникают в рамках последовательных альтернатив,
можно однозначно сопоставить множество четной мощности.
Если ситуация складывается так, что к вот этому, к предпоследнему,
к а5 мы собрали множество четной мощности, то а6 не кладем.
Если нечетной, то кладем.
Ну а этих ситуаций по правилу умножения 2 в 5 степени,
после чего все определяется однозначно.
То есть ответ в этой задаче на самом деле 2 в 5 степени, что есть, конечно, 32.
Ну и получается вот такое вот замечательное тождество.
Оно верно, разумеется, всегда.
То есть, если бы здесь была не шестерка, а какая-нибудь 1000,
то рассуждение было бы точно такое же,
только последовательно альтернировать мы закончили бы не на 5 шаге, а на 999.
У нас бы получилось: 2 в 999 степени равняется (С из
2000 по 0) + (С из 2000 по 2) +,..., + С из 2000 по 2000.
То есть сумма таких вот биномиальных коэффициентов с четными номерами.
В треугольнике Паскаля суммируем по строчке, но берем только четные номера.
Это 2 в n минус 1 степени.
Соответственно, если n — это, конечно, четное число.
Ну вот такая вот...
Собственно, почему четное?
Неважно.
Собственно, вот такая вот симпатичная тоже задача на то,
как можно получать тождества.
