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

Докажем утверждение индукцией по числу n учеников в классе.

Для n = 3 утверждение очевидно.

Предположим, что оно верно при n ≤ N. Пусть n = N + 1.

Утверждение верно, если в классе ровно один молчун. Пусть их не менее двух.

Выделим молчуна A и его друзей - болтунов B1, ..., Bk.

Для оставшихся n - 1 - k/2 учеников утверждение верно, т. е. можно выделить группу M, в которой каждый болтун дружит с нечётным числом молчунов и в M входит не менее учеников.

Предположим, что болтуны B1, ..., Bm дружат с нечётным числом молчунов из M, а Bm + 1, ..., Bk - с чётным числом.

Тогда, если, m больше k+1/2 то добавим к группе M болтунов B1, ..., Bm,

а если, m меньше k+1/2 то добавим к группе M болтунов Bm + 1, ..., Bk и молчуна A.

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