Задача 109998

Темы:    [ Индукция (прочее) ] [ Математическая логика (прочее) ] [ Объединение, пересечение и разность множеств ] [ Разбиения на пары и группы; биекции ]

Сложность: 4 Классы: 7,8,9,10,11

Условие

Автор: Берлов С.Л.

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

Решение

Докажем утверждение индукцией по числу n учеников в классе. Для n=3 утверждение очевидно. Предположим, что оно верно при n N . Пусть n=N+1 . Утверждение верно, если в классе ровно один молчун. Пусть их не менее двух. Выделим молчуна A и его друзей – болтунов B₁,..,B_k . Для оставшихся n-1-k учеников утверждение верно, т.е. можно выделить группу M , в которой каждый болтун дружит с нечетным числом молчунов и в M входит не менее учеников. Предположим, что болтуны B₁,..,B_m дружат с нечетным числом молчунов из M , а B_m+1,..,B_k – с четным числом. Тогда, если m , то добавим к группе M болтунов B₁,..,B_m , а если m< , то добавим к группе M болтунов B_m+1,..,B_k и молчуна A . В обоих случаях мы получим группу учеников, удовлетворяющую условию задачи.

Источники и прецеденты использования

web-сайт
задача
олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1999
Этап
Вариант	4
Класс
Класс	11
задача
Номер	99.4.11.3