Восемь учеников 11-Ж класса смотрели восьмисерийный сериал. Оказалось, что каждую серию видело ровно пятеро из них. Докажите, что найдутся два таких ученика, что каждую серию смотрел хотя бы один из них.

задан 2 Мар '15 15:49

изменен 2 Мар '15 16:04

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
1

Рассмотрим вспомогательный граф, изображая 8 точек, соответствующих ученикам, и соединим их попарно линиями. Всего будет проведено $%8\cdot7/2=28$% линий. Будем рассуждать "от противного". Предположим, что утверждение задачи неверно. Тогда для любой пары учеников найдётся серия (хотя бы одна), которую ни один из них не видел. Номер этой серии напишем на соответствующем отрезке, который задаёт пару учеников.

Поскольку $%28/8 > 3$%, найдётся серия, номер которой будет упомянут более трёх раз, то есть как минимум 4 раза (в противном случае число отрезков с номерами будет не больше 24). Рассмотрим концевые точки всех этих отрезков. Ясно, что их как минимум 4, так как между тремя точками возможно только три соединения. Тогда мы получим 4 ученика, ни один из которых не видел данную серию, что противоречит условию.

ссылка

отвечен 2 Мар '15 18:17

Огромное вам спасибо.

(2 Мар '15 18:40) deniszpol
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×928
×145

задан
2 Мар '15 15:49

показан
772 раза

обновлен
2 Мар '15 18:40

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru