2001-gre-vs-practice.pdf/Q41 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 1: Строка 1:
{{checkme|[[Участник:Илья52|илья52]] 19:23, 21 декабря 2024 (UTC)}}== Вопрос: Q41-e5724f ==
+
== Вопрос: Q41-e5724f ==
 
{{reserve-task|[[Участник:Илья52|илья52]] 11:05, 21 декабря 2024 (UTC)}}
 
{{reserve-task|[[Участник:Илья52|илья52]] 11:05, 21 декабря 2024 (UTC)}}
 
<blockquote>
 
<blockquote>
Строка 30: Строка 30:
  
 
{{question-ok|}}
 
{{question-ok|}}
 +
 +
{{Badsol}}
 +
 +
[[Участник:StasFomin|StasFomin]] 19:04, 23 декабря 2024 (UTC):  Илья, если вы невнимательно посмотрели постановку квеста, просмотрите сначала [https://t.me/c/2489499765/78/191 все замечания по оформлению в канале], уже нет сил переделывать за всеми.
  
 
[[Категория:Надо не забыть выбрать тему]]
 
[[Категория:Надо не забыть выбрать тему]]

Текущая версия на 19:08, 23 декабря 2024

Вопрос: Q41-e5724f

Задача зарезервирована: илья52 11:05, 21 декабря 2024 (UTC)

Пусть - конечное множество мощности . Чему равно количество подмножеств нечетной мощности (число количества элементов множества нечетное)?

Ответы

  • определенной формулы нет

Объяснение

Исходники — вопрос 41 на 34 странице книги «2001-gre-vs-practice.pdf»

Количество подмножеств, какого - либо конечного множества равно , где мощность множества. Докажем данную формулу. Упорядочим каким - либо образом все элементы множества . Сопоставим последовательность нулей и единиц каждому подмножеству следующим образом: если j-ый элемент множества содержится в подмножестве , то в последовательности из нулей и единиц будет стоять 1, в противном случае 0. Таким образом, получено взаимно однозначное соответствие между битовыми последовательностями и подмножествами. Битовых последовательностей .

Докажем, что четных и нечетных множеств одинаковое количество.

Пусть четное. Установим биекцию между четными и нечетными подмножествами. . Таким образом получаем, что количество четных и нечетных подмножеств одинаковое количество.

Пусть нечетное. Построим разбиение для .

Выберем произвольный элемент . Тогда подмножеств содержащих столько же сколько и не содержащих: (вспоминаем битовую последовательность описанную выше). Тогда можно по тому же правилу как и с четным описать биекцию между подмножествами, т.е. из содержащих в несодержащие, и наоборот. Таким образом вне зависимости от четности получаем ответ .

Правильный ответ: 3.

BrokenSolution.png
StasFomin 19:04, 23 декабря 2024 (UTC): Илья, если вы невнимательно посмотрели постановку квеста, просмотрите сначала все замечания по оформлению в канале, уже нет сил переделывать за всеми.