в группе 8 человек

[daogiauvang]

Доказать, что в любой группе из 8 чел. всегда найдется 2 человека, у которых есть количество общих знакомых четное.

[DeBill]

daogiauvang
От противного: пусть у любой пары - нечетное число общих знакомых.
Пусть $Z$ - знакомые $a$, а $N$ - незнакомые.
1. Пусть $z\in Z$. Тогда для $x\in Z$ условие "$x$ знаком с $z$" равносильно тому, что $x$ - общий знакомый для $z,a$ . Поэтому $z$ знаком в группе $Z$ с нечетным кол-вом чел. Значит, $\left\lvert Z\right\rvert$ -четно (число нечетных вершин подграфа $Z$- четно). Тогда $\left\lvert N\right\rvert$ - нечетно.
Значит, каждый $a$ знаком с четным кол-вом чел.
2. Каждый из $Z$ знаком с $a$, в группе $Z$ имеет нечетное число знакомых, и общее число его знакомых - четно (по п. 1). Значит, у каждого из них - четное число знакомых в группе $N$.
Значит, из $Z$ в $N$ идет четное число ребер.
3. Пусть $n\in N$. У них с $a$ - нечетное число общих знакомых, и все они - в группе $Z$. Значит, из каждой вершины $n\in N$ в группу $Z$ идет нечетное число ребер. Но в группе $N$ нечетное число чел.
Значит, из $N$ в $Z$ идет нечетное число ребер.
Противоречие с 2.

[daogiauvang]

DeBill в сообщении #1185999 писал(а):

daogiauvang
От противного: пусть у любой пары - нечетное число общих знакомых.
Пусть $Z$ - знакомые $a$, а $N$ - незнакомые.
1. Пусть $z\in Z$. Тогда для $x\in Z$ условие "$x$ знаком с $z$" равносильно тому, что $x$ - общий знакомый для $z,a$ . Поэтому $z$ знаком в группе $Z$ с нечетным кол-вом чел. Значит, $\left\lvert Z\right\rvert$ -четно (число нечетных вершин подграфа $Z$- четно). Тогда $\left\lvert N\right\rvert$ - нечетно.
Значит, каждый $a$ знаком с четным кол-вом чел.
2. Каждый из $Z$ знаком с $a$, в группе $Z$ имеет нечетное число знакомых, и общее число его знакомых - четно (по п. 1). Значит, у каждого из них - четное число знакомых в группе $N$.
Значит, из $Z$ в $N$ идет четное число ребер.
3. Пусть $n\in N$. У них с $a$ - нечетное число общих знакомых, и все они - в группе $Z$. Значит, из каждой вершины $n\in N$ в группу $Z$ идет нечетное число ребер. Но в группе $N$ нечетное число чел.
Значит, из $N$ в $Z$ идет нечетное число ребер.
Противоречие с 2.

У меня возник несколько вопросов:
1. Откуда $\left\lvert Z\right\rvert$ -четно (число нечетных вершин подграфа $Z$- четно)?
2. По моему $\left\lvert Z\right\rvert +\left\lvert N \right\rvert =8$ поэтому они либо вместе четны, либо вместе нечетны.

[DeBill]

daogiauvang в сообщении #1186023 писал(а):

1. Откуда $\left\lvert Z\right\rvert$ -четно (число нечетных вершин подграфа $Z$- четно)?
2. По моему $\left\lvert Z\right\rvert +\left\lvert N \right\rvert =8$ поэтому они либо вместе четны, либо вместе нечетны.

1. Мы выяснили, что в подграфе $Z$ все вершины - нечетной степени. Но в любом графе число вершин нечетной степени четно. Поэтому в $Z$ - четное число вершин.
2. Не 8, а 7 : вершина $a$ не входит ни туда, ни сюда.