В классе каждый ученик — либо болтун, либо молчун,
причем каждый болтун дружит хотя бы с одним молчуном.
Болтун молчит, если в кабинете находится нечётное число его друзей — молчунов.
Докажите, что учитель может пригласить на факультатив не менее половины класса так,
чтобы все присутствующие на факультативе болтуны молчали.

Докажем утверждение индукцией по числу n учеников в классе.Для n = 3 утверждение очевидно.Предположим, что оно верно при n ≤ N. Пусть n = N + 1.Утверждение верно, если в классе ровно один молчун. Пусть их не менее двух.Выделим молчуна A и его друзей — болтунов B1, … ,Bk.Для оставшихся n – 1 – k учеников утверждение верно, т.е. можно выделить группу M, в которой каждый болтун дружит с нечётным числом молчунов и в M входит не менее  учеников.Предположим, что болтуны B1, … ,Bm дружат с нечётным числом молчунов из M, а Bm + 1, … ,Bk — с чётным числом.Тогда, если , то добавим к группе M болтунов B1, … ,Bm,а если , то добавим к группе M болтунов Bm + 1, … ,Bk и молчуна A.В обоих случаях мы получим группу учеников, удовлетворяющую условию задачи.