2001-gre-vs-practice.pdf/Q41 — различия между версиями
Илья52 (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Вопрос: Q41-e5724f == | == Вопрос: Q41-e5724f == | ||
| − | + | Пусть ''A'' — конечное множество мощности ''n''. | |
| − | + | ||
| − | Пусть | + | |
| + | Чему равно количество подмножеств <m>S \subseteq A</m> нечетной мощности (т.е. число количества элементов множества ''S'' нечетное)? | ||
=== Ответы === | === Ответы === | ||
| − | |||
* <m>n</m> | * <m>n</m> | ||
* <m>2^{\frac{n}{2}}</m> | * <m>2^{\frac{n}{2}}</m> | ||
* Правильный ответ: <m>2^{n-1}</m> | * Правильный ответ: <m>2^{n-1}</m> | ||
* <m>2^{n}</m> | * <m>2^{n}</m> | ||
| − | * определенной формулы нет | + | * определенной формулы нет |
| + | |||
=== Объяснение === | === Объяснение === | ||
{{cstest-source|2001-gre-vs-practice.pdf|34|41}} | {{cstest-source|2001-gre-vs-practice.pdf|34|41}} | ||
| − | Количество подмножеств, какого - либо конечного множества равно <m>2^{n}</m>, где | + | Количество подмножеств, какого-либо конечного множества равно <m>2^{n}</m>, где ''n'' мощность множества. |
| − | Докажем | + | Докажем данную формулу. |
| − | + | Упорядочим каким — либо образом все элементы множества ''A''. | |
| − | + | Сопоставим последовательность нулей и единиц каждому подмножеству следующим образом: если j-ый элемент <m>a_j</m> множества <m>A</m> содержится в подмножестве <m>S \subseteq A </m>, то в последовательности из нулей и единиц будет стоять 1, в противном случае 0. Таким образом, получено взаимно однозначное соответствие между битовыми последовательностями и подмножествами. Битовых последовательностей <m>2^{n}</m>. | |
| − | + | ||
| − | + | Докажем, что четных и нечетных множеств одинаковое количество. | |
| − | + | Пусть <m>n</m> четное. Установим биекцию между четными и нечетными подмножествами. <m>f(S) = A \setminus S</m>. Таким образом получаем, что количество четных и нечетных подмножеств одинаковое количество. | |
{{Badsol}} | {{Badsol}} | ||
| − | [[Участник:StasFomin|StasFomin]] | + | [[Участник:StasFomin|StasFomin]] 22:36, 27 декабря 2024 (UTC): Гм. Так же из четных будут получаться тоже четные. A = {1, 2}, S = {} → f(S) → {1, 2}… |
| + | |||
| + | |||
| + | Пусть <m>n</m> нечетное. | ||
| + | Построим разбиение для <m>A</m>. | ||
| + | |||
| + | Выберем произвольный элемент <m>x_0</m>. Тогда подмножеств содержащих <m>x_0</m> столько же сколько и не содержащих: <m>2^{n-1}</m> (вспоминаем битовую последовательность описанную выше). Тогда можно по тому же правилу как и с четным <m>n</m> описать биекцию между подмножествами, то есть из содержащих <m>x_0</m> в несодержащие, и наоборот. Таким образом вне зависимости от четности <m>n</m> получаем ответ <m>2^{n-1}</m>. | ||
| + | |||
| + | {{question-ok|}} | ||
| − | [[Категория: | + | [[Категория:Комбинаторика]] |
Текущая версия на 22:36, 27 декабря 2024
Вопрос: Q41-e5724f
Пусть A — конечное множество мощности n.
Чему равно количество подмножеств нечетной мощности (т.е. число количества элементов множества S нечетное)?
Ответы
- Правильный ответ:
- определенной формулы нет
Объяснение
Исходники — вопрос 41 на 34 странице книги «2001-gre-vs-practice.pdf»
Количество подмножеств, какого-либо конечного множества равно , где n мощность множества.
Докажем данную формулу.
Упорядочим каким — либо образом все элементы множества A.
Сопоставим последовательность нулей и единиц каждому подмножеству следующим образом: если j-ый элемент множества содержится в подмножестве , то в последовательности из нулей и единиц будет стоять 1, в противном случае 0. Таким образом, получено взаимно однозначное соответствие между битовыми последовательностями и подмножествами. Битовых последовательностей .
Докажем, что четных и нечетных множеств одинаковое количество.
Пусть четное. Установим биекцию между четными и нечетными подмножествами. . Таким образом получаем, что количество четных и нечетных подмножеств одинаковое количество.
Пусть нечетное.
Построим разбиение для .
Выберем произвольный элемент . Тогда подмножеств содержащих столько же сколько и не содержащих: (вспоминаем битовую последовательность описанную выше). Тогда можно по тому же правилу как и с четным описать биекцию между подмножествами, то есть из содержащих в несодержащие, и наоборот. Таким образом вне зависимости от четности получаем ответ .