2001-gre-vs-practice.pdf/Q41 — различия между версиями
Илья52 (обсуждение | вклад) |
Илья52 (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | == Вопрос: Q41-e5724f == | + | {{checkme|[[Участник:Илья52|илья52]] 19:23, 21 декабря 2024 (UTC)}}== Вопрос: Q41-e5724f == |
{{reserve-task|[[Участник:Илья52|илья52]] 11:05, 21 декабря 2024 (UTC)}} | {{reserve-task|[[Участник:Илья52|илья52]] 11:05, 21 декабря 2024 (UTC)}} | ||
<blockquote> | <blockquote> | ||
| Строка 14: | Строка 14: | ||
=== Объяснение === | === Объяснение === | ||
<i>{{cstest-source|2001-gre-vs-practice.pdf|34|41}} | <i>{{cstest-source|2001-gre-vs-practice.pdf|34|41}} | ||
| + | |||
Количество подмножеств, какого - либо конечного множества равно <m>2^{n}</m>, где <m>n</m> мощность множества. Докажем данную формулу. Упорядочим каким - либо образом все элементы множества <m>A</m>. Сопоставим последовательность нулей и единиц каждому подмножеству следующим образом: если j-ый элемент <m>a_j</m> множества <m>A</m> содержится в подмножестве <m>S \subseteq A </m>, то в последовательности из нулей и единиц будет стоять 1, в противном случае 0. Таким образом, получено взаимно однозначное соответствие между битовыми последовательностями и подмножествами. Битовых последовательностей <m>2^{n}</m>. | Количество подмножеств, какого - либо конечного множества равно <m>2^{n}</m>, где <m>n</m> мощность множества. Докажем данную формулу. Упорядочим каким - либо образом все элементы множества <m>A</m>. Сопоставим последовательность нулей и единиц каждому подмножеству следующим образом: если 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> | + | Пусть <m>n</m> четное. Установим биекцию между четными и нечетными подмножествами. <m>f(S) = A \setminus S</m>. Таким образом получаем, что количество четных и нечетных подмножеств одинаковое количество. |
| + | |||
| + | Пусть <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>. | ||
| + | Правильный ответ: 3. | ||
</i> | </i> | ||
Текущая версия на 11:41, 22 декабря 2024
Решено: илья52 19:23, 21 декабря 2024 (UTC)== Вопрос: Q41-e5724f ==
Задача зарезервирована: илья52 11:05, 21 декабря 2024 (UTC)
Пусть - конечное множество мощности . Чему равно количество подмножеств нечетной мощности (число количества элементов множества нечетное)?
Ответы
- определенной формулы нет
Объяснение
Исходники — вопрос 41 на 34 странице книги «2001-gre-vs-practice.pdf»
Количество подмножеств, какого - либо конечного множества равно , где мощность множества. Докажем данную формулу. Упорядочим каким - либо образом все элементы множества . Сопоставим последовательность нулей и единиц каждому подмножеству следующим образом: если j-ый элемент множества содержится в подмножестве , то в последовательности из нулей и единиц будет стоять 1, в противном случае 0. Таким образом, получено взаимно однозначное соответствие между битовыми последовательностями и подмножествами. Битовых последовательностей .
Докажем, что четных и нечетных множеств одинаковое количество.
Пусть четное. Установим биекцию между четными и нечетными подмножествами. . Таким образом получаем, что количество четных и нечетных подмножеств одинаковое количество.
Пусть нечетное. Построим разбиение для .
Выберем произвольный элемент . Тогда подмножеств содержащих столько же сколько и не содержащих: (вспоминаем битовую последовательность описанную выше). Тогда можно по тому же правилу как и с четным описать биекцию между подмножествами, т.е. из содержащих в несодержащие, и наоборот. Таким образом вне зависимости от четности получаем ответ .
Правильный ответ: 3.