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

Предположим, что в классе всего n учеников. Разделим их на две группы: болтунов и молчунов. Пусть в классе m болтунов, тогда среди них существует хотя бы m друзей-молчунов (по условию задачи). По правилу сложения, мы можем представить всех учеников в классе так: n = m + k, где k - количество молчунов.

Применим метод от противного и предположим, что учитель не сможет пригласить на факультатив не менее половины класса, чтобы все присутствующие болтуны молчали. Тогда, если бы пригласили f болтунов на факультатив, то они должны были бы молчать. Значит, в кабинете было бы нечётное количество их друзей-молчунов. Так как у каждого болтуна друзей-молчунов минимум m, то f > m.

Теперь рассмотрим следующую ситуацию: Мы выбираем f молчунов из общего количества k молчунов и доказываем, что сумма их (f) друзей-болтунов нечётна. Если это не так и сумма друзей-болтунов f молчунов чётна, то это означает, что среди оставшихся k-f молчунов удалось выбрать чётное количество их друзей-болтунов. Так как у каждого молчуна есть хотя бы по 1 другу-болтуну, то количество друзей-болтунов среди всех молчунов не меньше k. Значит, при выборе f молчунов для факультатива, количество друзей-болтунов в кабинете будет k+f, что равняется k+f (mod 2), где mod 2 - означает остаток от деления на 2. И так как k+f (mod 2) = k(mod 2) + f(mod 2), то это значение будет нечётным. Противоречие.

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