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

[nou]

Всем привет, недавно я начал решать листки отсюда: http://www.mccme.ru/~merzon/v14/
Первые листки несложные, наверное, однако при решении у меня нет удовлетворения, складывается ощущение, что я делаю какую-то ерунду и вообще математически безвкусен.

Поэтому, я решил попросить у Вас оценить некоторые мои решения.

Итак, листок 1 задача 5: Каких подмножеств у 2010-элементного множества больше: имеющих четное или нечетное число элементов?

Пусть 2010-элементное мн-во - мн-во $A$. Уберём из $A$ какой-нибудь элемент. Получим мн-во $B$, состоящее из 2009-ти элементов.Понятно, что если $C\subset B$, то $C\subset A$. Пусть у мн-ва $B$ $k$ подмн-в имеют чётное число элементов (назовём их "чётные" подмн-ва), $m$ - нечётное. (назовём их "нечётные" подмн-ва) У мн-ва $A$ есть подмн-ва, которые не являются подмн-вами $B$. Эти оставшиеся подмн-ва получаются добавлением изъятого элемента к мн-вам $C$ : $C\subset B$. Тогда понятно, что среди таких подмн-в уже $m$ -"чётны", а $k$ -"нечётны". Получаем, что у мн-ва $A$ $(k+m)$ подмн-в, имеющих чётное число элементов, и столько же подмн-в, имеющих нечётное число элементов.

Ну как? Остальные решения выложу позже.

[provincialka]

Хм... Для 2009-элементного множества свойство очевидно: если разбить его на два множества, одно будет "четным", а другое -- "нечетным". Переход к 2010-элемнтному множеству вроде удачный.

[мат-ламер]

Ясно, что если просуммировать биномиальные коэффициенты, стоящие на чётных и нечётных местах, то получим одинаковые суммы. (Многочлен $(1-x)^n$ развернуть и подсчитать значение при $x=1$).

[Geen]

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

Ну как? Остальные решения выложу позже.

Пусть у нас $n$-элементное мн-во натуральных чисел. Каких подмножеств больше, с чётной или нечётной суммой их элементов?

[Olivka]

Geen в сообщении #1061799 писал(а):

$n$-элементное мн-во натуральных чисел

Либо $n$-элементное, либо мн-во натуральных чисел.

[Geen]

Olivka в сообщении #1061997 писал(а):

Geen в сообщении #1061799 писал(а):

$n$-элементное мн-во натуральных чисел

Либо $n$-элементное, либо мн-во натуральных чисел.

Неуклюже выразился, но, думаю, понятно.

[iifat]

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

Уберём из $A$ какой-нибудь элемент

Решение, конечно, приведено, но если вам, как мне, больше нравятся комбинаторные доказательства, можно попробовать довести это до конца. Только не надо убирать элемент; просто выберите какой-нибудь элемент. А теперь попробуйте сопоставить каждому множеству нечётной мощности множество чётной и наоборот.

[nou]

мат-ламер, $(a+b)^n=\sum\limits_{k=0}^{n} \binom{n}{k} a^{n-k}b^k$, $(1-x)^n=\sum\limits_{k=0}^{n} \binom{n}{k} (-x)^k$
При $x=1$ многочлен $(1-x)^n$ равен нулю.
Однако заметим, что при $x=1$ $(1-x)^n=\sum\limits_{k=0}^{n} (-1)^k \binom{n}{k}$
Получаем: $\sum\limits_{k=0}^{n} (-1)^k \binom{n}{k}=0$, откуда приходим к:

$$\sum\limits_{k=0, k\equiv0 (\bmod 2)}^{n} \binom{n}{k}=\sum\limits_{k=0, k\equiv1 (\bmod 2)}^{n} \binom{n}{k}$$

А так как в терминах теории множеств $\binom{n}{k}$-кол-во $k$-элементных подмн-в $n$-элементного мн-ва,то равенство выше показывает,что у $n$-элементного мн-ва число подмн-в, имеющих чётное и нечётное число элементов одинаково.

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

Доказательство практически такое же как и выше в задаче 5.

-- 13.10.2015, 18:07 --

iifat, спасибо, я подумаю над этим.

[Neos]

А воспользоваться соотношением
${n\choose 0}+{n\choose 1}+\ldots+{n\choose n}=2^n$,
где $2^n$ - общее число подмножеств ?

[ASH]

может быть еще проще - сравнить количество четных и нечетных чисел на интервале от 1 до $2^n$? По-моему, число четных равно числу нечетных.

[Geen]

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

Доказательство практически такое же как и выше в задаче 5.

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

[nou]

О, сколько людей подтянулось.
Всем спасибо за то, что предлагаете идеи, а также вообще просто это читаете.
Простите, я медленно соображаю. Я подумаю над этим всем и завтра напишу сюда свои мысли.

[nou]

iifat, я себе это так представил:

Задача 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:\left\lvert B\right\rvert\equiv1 (\bmod 2) \wedge x_k \notin B\right\rbrace$, $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$
Тогда $f_1: X_1\to Y_1$, $f_1(B)=B\cup \left\lbrace x_k\right\rbrace$.
Здесь и далее $g(X)$ - образ $X$, где $X$ - мн-во. Аналогично построим отображение $f_2$.
$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$, $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$
Тогда $f_2: X_2\to Y_2$, $f_2(B)=B\setminus \left\lbrace x_k\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$, что и нужно было доказать.

[provincialka]

О боже мой! А по русски можете пересказать, о чем это вы? Лично мне продираться сквозь символы неохота...

[nou]

provincialka, простите
Я рассматриваю $n$-элементное мн-во $A$, обозначаю мн-во $X$ ($Y$), которое состоит из подмн-в $A$ с нечётным (чётным) числом элементов. Потом пытаюсь построить отображение $f$ из мн-ва $X$ в $Y$, фиксирую для этого какой-то элемент $x_k$ из мн-ва $A$.
Строю отображения $f_1,f_2$. Отображение $f_1$ такое, что определено на мн-вах $X: x_k\notin X$ и $f(B)=B\cup \left\lbrace x_k\right\rbrace$. А отображение $f_2$ таково, что определено на мн-вах $X: x_k\in X$ и $f(B)=B\setminus \left\lbrace x_k\right\rbrace$. Потом из двух отображений собираю одно, показываю, что это биекция, заключая, что мн-ва $X$ и $Y$ равномощны, что и требуется доказать.