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

Допустим, в классе есть N учеников, где n из них являются болтунами, а N-n являются молчунами. По условию, каждый болтун дружит хотя бы с одним молчуном, значит каждый болтун имеет хотя бы одного друга - молчуна.

Предположим, что учитель пригласил на факультатив k болтунов (k <= n). Тогда количество молчунов, дружащих с этими болтурами, будет не меньше, чем k, так как каждый болтун имеет хотя бы одного друга - молчуна.

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

Рассмотрим случай, когда k > n/2. Если выбрать k болтуна среди n учеников, то в худшем случае каждый из болтуна будет дружить с n/2 молчунами (в случае, если k > n/2, то не у всех болтунов будет нечетное количество друзей-молчунов). Таким образом, количество друзей-молчунов каждого болтуна будет четным числом. Это означает, что даже если учитель пригласит больше половины класса на факультатив, все присутствующие болтуны не будут молчать.

Рассмотрим случай, когда k <= n/2. В этом случае, если выбрать k болтунов среди n учеников, то каждый из болтуна будет дружить с не менее, чем k молчунами. Так как k <= n/2, то количеством друзей-молчунов каждого болтуна будет нечетное число. То есть при таком выборе болтунов на факультативе будут только молчуны.

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