Олимпиадная задача по математической логике: болтуны и молчуны в классе (7–11 класс)
Задача
В классе каждый болтун дружит хотя бы с одним молчуном. При этом болтун молчит, если в кабинете находится нечетное число его друзей – молчунов. Докажите, что учитель может пригласить на факультатив не менее половины класса так, чтобы все болтуны молчали.
Решение
Докажем утверждение индукцией по числу n учеников в классе.
Для n=3утверждение очевидно. Предположим, что оно верно при n
N .
Пусть n=N+1. Утверждение верно, если в классе ровно один молчун.
Пусть их не менее двух. Выделим молчуна A и его друзей – болтунов B1,..,Bk . Для оставшихся n-1-k учеников утверждение верно,
т.е. можно выделить группу M , в которой каждый болтун дружит с нечетным
числом молчунов и в M входит не менее 
учеников.
Предположим, что болтуны B1,..,Bm дружат с нечетным числом молчунов из M , а Bm+1,..,Bk – с четным числом. Тогда, если m
, то добавим к группе M болтунов B1,..,Bm ,
а если m< , то добавим к группе M болтунов Bm+1,..,Bk и молчуна A . В обоих случаях мы получим группу
учеников, удовлетворяющую условию задачи.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь