Question

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

Answer 1

Докажем утверждение индукцией по числу 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.
В обоих случаях мы получим группу учеников, удовлетворяющую условию задачи.

Answer 2

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

Answer 3

Предположим, что в классе всего N учеников, и M из них являются болтунами.

Возьмем одного из болтунов и обозначим его как A. По условию, у A есть хотя бы один друг-молчун, обозначим его как B.

Теперь рассмотрим всех других учеников, кроме A и B. Из условия известно, что каждый болтун дружит хотя бы с одним молчуном. Значит, среди оставшихся N-2 учеников должны быть хотя бы M-1 молчунов.

Итак, у нас есть болтун A, его друг-молчун B, и как минимум M-1 молчунов среди оставшихся N-2 учеников.

Теперь предположим, что на факультативе будут присутствовать только болтуны. Тогда чтобы все они молчали, должно быть нечетное число болтунов в кабинете. Если M-1 (количество молчунов среди оставшихся учеников) четное, то M-1+1=M будет нечетным числом болтунов, что удовлетворяет условию.

Таким образом, учитель может пригласить на факультатив всех болтунов из класса, за исключением A и B, и при этом все присутствующие будут молчать. Количество болтунов, которых можно пригласить, равно M-1.

Но по условию задачи требуется, чтобы учитель пригласил не менее половины класса на факультатив. То есть, M-1 должно быть не меньше N/2.

Если это условие выполняется (M-1 >= N/2), то учитель может пригласить не менее половины класса на факультатив так, чтобы все присутствующие были болтуны и молчали.