Задачи по теории множеств

[provincialka]

Вот как бы я это описала, если я правильно поняла ваше рассуждение:

(Оффтоп)

Выделим в заданном множестве из 2010 элементов элемент $a$, множество остальных 2009 элементов обозначим через $A$. Тогда все подмножества $\{a\}\cup A$ разделяются на те, которые входят в $A$ и те, которые содержат $a$.
Подмножеств из $A$ всего $2m=2^{2009}$ штук, и их можно разбить на пары "четное" - "нечетное", $X$ и $A\setminus X$. Множеств каждого типа будет по $m$. Теперь, добавляя к каждому из них элемент $a$ получим еще $m$ "четных" и $m$ "нечетных" подмножеств. Их опять поровну!

[iifat]

provincialka в сообщении #1062634 писал(а):

Вот как бы я это описала

Э, нет! Вы описываете изначальное доказательство ТС, с которым он сразу сюда пришёл. Ну, приблизительно. Он в шаге индукции обошёлся без того факта, что множество из 2009 тоже разбивается пополам.
Словами это описывается так: выбираем некий элемент. Каждому множеству сопоставляем другое по закону: если в нашем множестве присутствует выбранный элемент, сопоставляем ему его же с вычеркнутым элементом, если отсутствует — сопоставляем его же с добавленным. Легко доказывается, что наше сопоставление полно и взаимно однозначно, так что множество подмножеств разбивается на пары подмножеств разной чётности.
Аналогично (если выбрать нечётный элемент) решается и вторая задача, с суммами.
Мне сначала показалось, что исходное доказательство ТС неправильное, потому я и написал про выбор. Я ошибся.

[provincialka]

iifat
Вы гений! Вы смогли разобраться в описаниях ТС!

[Olivka]

nou в сообщении #1062566 писал(а):

Рассмотрим $A=\left\lbrace x_1,x_2,...,x_n\right\rbrace$, тогда можно рассмотреть такие классы подмн-в $A$:
$X=\left\lbrace B\subset A:\left\lvert B\right\rvert\equiv1 (\bmod 2)\right\rbrace$, $Y=\left\lbrace C\subset A:\left\lvert C\right\rvert\equiv0 (\bmod 2)\right\rbrace$
Выберем какой-нибудь $x_k: x_k\in A, k\in [1;n]$, а дальше построим отображение $f: X\to Y$.

На этом моменте всё хорошо.

nou в сообщении #1062566 писал(а):

$X_1\subset X, X_1=\left\lbrace B\subset A:\left\lvert B\right\rvert\equiv1 (\bmod 2) \wedge x_k \notin B\right\rbrace$

Одно из условий, связанных конъюнкцией, оказывается избыточным, догадайтесь какое. Зачем вводить условия, которые уже введены?

nou в сообщении #1062566 писал(а):

$Y_1\subset Y, Y_1=\left\lbrace C\subset A:\left\lvert C\right\rvert\equiv0 (\bmod 2) \wedge x_k \in B\right\rbrace$

А что такое $x_k \in B$? Вероятно, вы опечатались, имея в виду $x_k \in C$.

nou в сообщении #1062566 писал(а):

$X_2\subset X, X_2=\left\lbrace B\subset A:\left\lvert B\right\rvert\equiv0 (\bmod 2) \wedge x_k \in B\right\rbrace$

$X$ уже определено так, что содержит только подмножества нечетной мощности: $\left\lvert B\right\rvert\equiv1 (\bmod 2)$ Теперь вы пытаетесь выбрать в нем лишь такие, мощность у которых была бы четной: $\left\lvert B\right\rvert\equiv0 (\bmod 2)$. Разумеется, таким способом вы получите пустое множество. Уберите первое условие, оно вам мешает же!

nou в сообщении #1062566 писал(а):

$Y_2\subset Y, Y_2=\left\lbrace C\subset A:\left\lvert C\right\rvert\equiv1 (\bmod 2) \wedge x_k \notin B\right\rbrace$

Помимо повторения ситуации с разной мощностью, вы, вероятно, второй раз опечатались, имея в виду $x_k \notin C$.

nou в сообщении #1062566 писал(а):

$$(1): f(B)=\begin{cases} (B\cup \left\lbrace x_k\right\rbrace)\in Y_1,&\text{если $B\in X_1$;}\\(B\setminus \left\lbrace x_k\right\rbrace)\in Y_2,&\text{если $B\in X_2$;}\end{cases}$$

Этой одной записи вполне будет достаточно. Функции $f_1$ и $f_2$ у вас не используются, они не нужны. Тогда незачем их определять.

[iifat]

(Оффтоп)

provincialka в сообщении #1062769 писал(а):

Вы гений!

А, вы тоже заметили? А я давно подозревал!

provincialka в сообщении #1062769 писал(а):

Вы смогли разобраться в описаниях ТС!

Ну, я надеюсь. Вроде бы похоже

[nou]

Так, я исправлюсь.
Задача 5 (исправленный вариант):
Рассмотрим $A=\left\lbrace x_1,x_2,...,x_n\right\rbrace$, тогда можно рассмотреть такие классы подмн-в $A$:
$X=\left\lbrace B\subset A:\left\lvert B\right\rvert\equiv1 (\bmod 2)\right\rbrace$, $Y=\left\lbrace C\subset A:\left\lvert C\right\rvert\equiv0 (\bmod 2)\right\rbrace$
Выберем какой-нибудь $x_k: x_k\in A, k\in [1;n]$, а дальше построим отображение $f: X\to Y$.
$X_1\subset X, X_1=\left\lbrace B\subset A: x_k \notin B\right\rbrace$, $Y_1\subset Y, Y_1=\left\lbrace C\subset A: x_k \in C\right\rbrace$,
$X_2\subset X, X_2=\left\lbrace B\subset A: x_k \in B\right\rbrace$, $Y_2\subset Y, Y_2=\left\lbrace C\subset A: x_k \notin C\right\rbrace$
Отображение $f$ построим так: $f: X\to Y$; $X=X_1\cup X_2, Y=Y_1\cup Y_2$.

$$(1): f(B)=\begin{cases} (B\cup \left\lbrace x_k\right\rbrace)\in Y_1,&\text{если $B\in X_1$;}\\(B\setminus \left\lbrace x_k\right\rbrace)\in Y_2,&\text{если $B\in X_2$;}\end{cases}$$

Отображение $f$ - биекция. Действительно, $\forall B_1,B_2\in X: B_1 \ne B_2\Rightarrow f(B_1)\ne f(B_2)$ легко проверить, рассмотрев четыре варианта. (инъективность)
Проверить сюръективность отображения $f$ тоже несложно, действительно, $\forall C f^{-1}(C)\ne\varnothing$ легко проверить, воспользовавшись (1).
Из биективности $f$ следует то, что $\left\lvert X\right\rvert=\left\lvert Y\right\rvert$, что и нужно было доказать.

Рассматриваем $n$-элементное мн-во - мн-во $A$, мн-во $X$ ($Y$), состоящее из подмн-в $A$ c нечётным (чётным) числом элементов. Далее выбираем в $A$ какой-нибудь элемент, фиксируем его. Принадлежность фиксированного элемента подмн-ву $A$ - свойство, делящее мн-ва $X$ ($Y$) на два класса. Строим отображение $f: X\to Y$, которое подмн-вам $A$ с нечётным числом элементов ставит в соответствие подмн-ва $A$ с чётным числом элементов. Отображение $f$ такое, что если мн-во $B$ из $X$ содержит выбранный элемент, то f(B) - мн-во $B$ без выбранного элемента. А если мн-во $B$ из $X$ не содержит выбранный элемент, то $f(B)$ - мн-во $B$ с этим элементом. Потом проверяем, что $f$ - биекция, тогда мн-ва $X$ и $Y$ равномощны, а это и требуется доказать.

[ewert]

А почему всё так долго?... Для 2009-элементного множества вроде всем всё с самого начала было очевидно. У 2010-элементного же множества каждое подмножество либо не содержит 2010-й элемент, либо содержит. В первом классе чётных и нечётных подмножеств поровну, ну а между первым и вторым классами очевидна биекция, инвертирующая чётность.

[provincialka]

ewert
Собственно, примерно это мы и говорили ранее: первое решение ТС практически такое. Но дальше пошли варианты.

[ewert]

provincialka в сообщении #1063136 писал(а):

Но дальше пошли варианты.

Слишком уж лаконичны все те варианты. Диссертацию ни на одном из них не сделаешь!

[provincialka]

nou
А зачем вам непременно надо выделять "какой-то $x_k$"? Просто $x_1$ нельзя? Или вообще его $x$ обозначить? Все-таки формулы будут менее громоздкими...

[nou]

ewert, provincialka, не знаю, так вышло.
Я придумал ещё одно доказательство с помощью чисел сочетаний, используя такое равенство:
${n\choose 0}+{n\choose 1}+\ldots+{n\choose n}=2^n$, как говорил Neos.
Относительно того, что сказал ASH я ничего не придумал.
Однако я проверил верность своего первого доказательства, поработал с числами сочетаний, отображениями.
Всем спасибо, тему считаю исчерпанной.
Буду решать листочки дальше.

[Geen]

nou в сообщении #1063153 писал(а):

Всем спасибо, тему считаю исчерпанной.

На закуску. Пусть есть $n$-элементное подмножество целых чисел. Каких его подмножеств больше, с положительным или отрицательным произведением элементов. (для пустого множества произведение равно 1).

[nou]

Geen, пусть данное подмн-во - мн-во $A$. Уберём из мн-ва $A$ произвольный отрицательный элемент, получив мн-во $B$, состоящее из $(n-1)$ элементов. Понятно, что мн-ва, которые являются подмн-вами $B$ - подмн-ва $A$. Пусть у мн-ва $B$ $k$ подмн-в таковы, что произведение элементов положительно, а $m$ подмн-в таковы, что произведение элементов отрицательно. Ясно, что у $A$ есть подмн-ва, которые не являются подмн-вами $B$. Они получаются добавлением к мн-вам $C$: $C\subset B$ изъятого элемента. Понятно, что среди таких подмн-в $k$ имеют отрицательное произведение элементов, а $m$ - положительное. Откуда следует, что у $A$ одинаковое кол-во подмн-в, имеющих положительное/отрицательное произведение.
Если же в $A$ нет ни одного отрицательного элемента, то тогда понятно, что произведение элементов любого подмн-ва $A$ положительно. Подмн-в, имеющих положительное произведение элементов, будет больше.

[Aritaborian]

nou, пусть данное подмножество $A=\{-2,-1,1\}$...

[ASH]

Например, если у нас одно отрицательное число и $n-1$ положительных, то, очевидно, у нас будет $1+2^{n-1}$ подмножеств с отрицательным произведением (отрицательных подмножеств) и $2^{n-1}-1$ с положительным произведением (положительных подмножеств). Так что отрицательных подмножеств получается больше. Если у нас два отрицательных числа, то это, очевидно, добавит 2 подмножества к отрицательным и 1 к положительным, так что отрицательных станет снова больше чем положительных. Получается, что отрицательных подмножеств будет, во всяком случае, не меньше, чем положительных.