Разделы 
Дополнительно
Задача по математике - 1574
2019-01-19 
В классе каждый болтун дружит хотя бы с одним молчуном. При этом болтун молчит, если в кабинете находится нечетное число его друзей - молчунов. Докажите, что учитель может пригласить на факультатив не менее половины класса так, чтобы все болтуны молчали.
Решение:
Докажем утверждение индукцией по числу $n$ учеников в классе. Для $n = 3$ утверждение очевидно. Предположим, что оно верно при $n \leq N$. Пусть $n = N + 1$. Утверждение верно, если в классе ровно один молчун. Пусть их не менее двух. Выделим молчуна $A$ и его друзей - болтунов $B_1,\cdots,B_k$. Для оставшихся $n - 1 - к$ учеников утверждение верно, т. е. можно выделить группу $M$, в которой каждый болтун дружит с нечетным числом молчунов и в $М$ входит не менее $\frac {n-1-k}{2}$ учеников. Предположим, что болтуны $B_1,\cdots, B_m$ дружат с нечетным числом молчунов из $М$, а $В_{m+1},\cdots ,В_к$ - с четным числом. Тогда, если $m \geq \frac{k+1}{2}$, то добавим к группе $М$ болтунов $В_{m+1},\cdots,B_k$ - с четным числом. Тогда, если $m < \frac{k+1}{2}$, то добавим к группе $M$ болтунов $B_{m+1}, \cdots, B_k$ и молчуна $A$. В обоих случаях мы получим группу учеников, удовлетворяющую условию задачи.
В классе каждый болтун дружит хотя бы с одним молчуном. При этом болтун молчит, если в кабинете находится нечетное число его друзей - молчунов. Докажите, что учитель может пригласить на факультатив не менее половины класса так, чтобы все болтуны молчали.
Решение:
Докажем утверждение индукцией по числу $n$ учеников в классе. Для $n = 3$ утверждение очевидно. Предположим, что оно верно при $n \leq N$. Пусть $n = N + 1$. Утверждение верно, если в классе ровно один молчун. Пусть их не менее двух. Выделим молчуна $A$ и его друзей - болтунов $B_1,\cdots,B_k$. Для оставшихся $n - 1 - к$ учеников утверждение верно, т. е. можно выделить группу $M$, в которой каждый болтун дружит с нечетным числом молчунов и в $М$ входит не менее $\frac {n-1-k}{2}$ учеников. Предположим, что болтуны $B_1,\cdots, B_m$ дружат с нечетным числом молчунов из $М$, а $В_{m+1},\cdots ,В_к$ - с четным числом. Тогда, если $m \geq \frac{k+1}{2}$, то добавим к группе $М$ болтунов $В_{m+1},\cdots,B_k$ - с четным числом. Тогда, если $m < \frac{k+1}{2}$, то добавим к группе $M$ болтунов $B_{m+1}, \cdots, B_k$ и молчуна $A$. В обоих случаях мы получим группу учеников, удовлетворяющую условию задачи.
