Разделы 
Дополнительно
Задача по математике - 9151
2022-11-02 
В классе поровну мальчиков и девочек. Каждый мальчик дружит с четным числом девочек. Докажите, что можно выбрать группу из нескольких мальчиков (не менее одного) так, чтобы с каждой девочкой дружило четное число мальчиков из этой группы.
Решение:
Каждой группе мальчиков поставим в соответствие группу девочек, образованную теми девочками, которые дружат е нечетным числом мальчиков из исходной группы. Общее число знакомств мальчиков из исходной группы со всеми девочками четное и равно сумме числа знакомств вошедших в подгруппу девочек е мальчиками исходной группы и числа знакомств не вошедших в группу девочек е мальчиками исходной группы. Второе слагаемое как сумма четных чисел является четным числом, поэтому и первое число является четным. Отсюда получаем, что количество девочек в сформированной группе должно быть четным числом, так как каждая девочка из этой группы дружит с нечетным числом мальчиков из исходной группы.
Пусть в классе $n$ мальчиков и столько же девочек. Тогда число всевозможных непустых групп мальчиков равно $2^{n} - 1$. Число всевозможных групп, состоящих из четного числа девочек, равно $2^{n-1}$. Так как $2^{n-1} < 2^{n} - 1$ при $n > 1$, то каким-то двум группам мальчиков мы поставили в соответствие одну и ту же группу девочек. Это означает, что для каждой девочки класса количество друзей - мальчиков в этих группах имеют одинаковую четность,
В качестве искомой группы можно взять мальчиков, входящих ровно в одну из рассматриваемых групп. В самом деле, рассмотрим некоторую девочку класса. Пусть она дружит с $k$ мальчиками, которые входят только в первую рассматриваемую группу, с $m$ мальчиками, которые входят только во вторую рассматриваемую группу и с $s$ мальчиками, которые входят одновременно в первую и вторую группу. Тогда по доказанному числа $k + s$ и $m + s$ имеют одинаковую четность. Отсюда получаем, что $k + m$ является четным числом.
Случай $n = 1$ очевиден.
В классе поровну мальчиков и девочек. Каждый мальчик дружит с четным числом девочек. Докажите, что можно выбрать группу из нескольких мальчиков (не менее одного) так, чтобы с каждой девочкой дружило четное число мальчиков из этой группы.
Решение:
Каждой группе мальчиков поставим в соответствие группу девочек, образованную теми девочками, которые дружат е нечетным числом мальчиков из исходной группы. Общее число знакомств мальчиков из исходной группы со всеми девочками четное и равно сумме числа знакомств вошедших в подгруппу девочек е мальчиками исходной группы и числа знакомств не вошедших в группу девочек е мальчиками исходной группы. Второе слагаемое как сумма четных чисел является четным числом, поэтому и первое число является четным. Отсюда получаем, что количество девочек в сформированной группе должно быть четным числом, так как каждая девочка из этой группы дружит с нечетным числом мальчиков из исходной группы.
Пусть в классе $n$ мальчиков и столько же девочек. Тогда число всевозможных непустых групп мальчиков равно $2^{n} - 1$. Число всевозможных групп, состоящих из четного числа девочек, равно $2^{n-1}$. Так как $2^{n-1} < 2^{n} - 1$ при $n > 1$, то каким-то двум группам мальчиков мы поставили в соответствие одну и ту же группу девочек. Это означает, что для каждой девочки класса количество друзей - мальчиков в этих группах имеют одинаковую четность,
В качестве искомой группы можно взять мальчиков, входящих ровно в одну из рассматриваемых групп. В самом деле, рассмотрим некоторую девочку класса. Пусть она дружит с $k$ мальчиками, которые входят только в первую рассматриваемую группу, с $m$ мальчиками, которые входят только во вторую рассматриваемую группу и с $s$ мальчиками, которые входят одновременно в первую и вторую группу. Тогда по доказанному числа $k + s$ и $m + s$ имеют одинаковую четность. Отсюда получаем, что $k + m$ является четным числом.
Случай $n = 1$ очевиден.
