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

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

Пусть n — количество учеников в классе, и изначально предположим, что учитель пригласит на факультатив только одного ученика.

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

2. Предположим, что утверждение верно для n = k, то есть учитель может пригласить не менее половины класса так, чтобы все присутствующие болтуны молчали.

3. Докажем, что утверждение верно для n = k + 1. Рассмотрим два случая:

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

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

Таким образом, утверждение верно для n = k + 1, и, следовательно, верно для всех положительных целых n.

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