ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109998
Темы:    [ Индукция (прочее) ]
[ Математическая логика (прочее) ]
[ Объединение, пересечение и разность множеств ]
[ Разбиения на пары и группы; биекции ]
Сложность: 4
Классы: 7,8,9,10,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 . В обоих случаях мы получим группу учеников, удовлетворяющую условию задачи.

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

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

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .