20 теннисистов устроили между собой соревнование из 14 игр. В каждой игре участвует 2 человека и каждый из этой компании теннисистов принял участие хотя бы в одной игре. Докажите, что в некоторых 6 играх участвовало 12 различных теннисистов.

задан 16 Янв '14 13:13

изменен 16 Янв '14 20:17

Deleted's gravatar image


126

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

Рассмотрим максимальное паросочетание, то есть максимально возможное число $%m$% такое, что в $%m$% играх участвовало $%2m$% различных теннисистов. Очевидно, что $%m\ge1$%. Предположим, что $%m\le5$%. Тогда в паросочетание не вошли $%20-2m$% теннисистов. Из них каждый с кем-то играл, но никто не играл между собой, так как в противном случае можно увеличить паросочетание ещё на одну пару. Для каждого из $%20-2m$% теннисистов рассмотрим его игру с кем-то из $%2m$% участников паросочетания. Тогда все эти поединки будут попарно различными, и к ним добавятся ещё $%m$% поединков между участниками пар. Всего получится $%20-m$% игр, что не должно превосходить $%14$%, откуда $%m\ge6$% -- противоречие.

ссылка

отвечен 16 Янв '14 15:47

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,113
×547
×501

задан
16 Янв '14 13:13

показан
691 раз

обновлен
16 Янв '14 15:47

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

по почте:

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

по RSS:

Ответы

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

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