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

Докажем это утверждение по индукции.

База индукции: Рассмотрим класс из 1 ученика. Он может быть либо болтуном, либо молчуном. В любом случае, учитель может пригласить его на факультатив и он будет молчать.

Шаг индукции: Пусть утверждение верно для класса из n учеников. Рассмотрим класс из n + 1 ученика.

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

Если в первой группе есть хотя бы один ученик, то у него есть друзья молчуны из второй группы.

Рассмотрим два случая:

1. Если во второй группе всего один молчун, то все болтуны из первой группы, кроме одного, будут молчать, так как они дружат с этим молчуном. И учитель может пригласить этого одного болтуна и молчуна на факультатив.

2. Если во второй группе больше одного молчуна, то выберем одного молчуна из второй группы и удалим его из класса. Теперь у нас остался класс из n учеников, для которого, по предположению индукции, утверждение верно. То есть учитель может пригласить на факультатив не менее половины этого класса так, чтобы все присутствующие болтуны молчали. Добавим к этим ученикам ранее удаленного молчуна в качестве нового ученика. Теперь у нас имеется класс из n + 1 ученика, и утверждение остается верным.

Таким образом, утверждение верно для любого класса из n учеников, и следовательно, оно верно для класса из n+1 ученика.

Следовательно, учитель может пригласить на факультатив не менее половины класса так, чтобы все присутствующие на факультативе болтуны молчали.