Муниципалка 10 - 11 класс
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Двадцать одна девочка и двадцать один мальчик принимали участие в математическом конкурсе. Каждый участник решил не более шести задач. Для любых девочки и мальчика найдётся хотя бы одна задача, решённая обоими. Докажите, что была задача, которую решили не менее трёх девочек и не менее трёх мальчиков.
Источники:
Подсказка 1
Пойдём от противного, чтобы добавить себе условие на то, что каждую задачу решили не более двух девочек или не более двух мальчиков. Для удобства будем считать задачу «красной», если её решили не более двух девочек и «чёрной»» в противоположном случае (тогда её решили не более двух мальчиков). Давайте так же перейдём к шахматной доске 21х21, где каждый столбец это мальчик, а строка - девочка, чтобы каждая клетка отражала ту задачу, которую они оба решили.
Подсказка 2
Давайте попробуем отталкиваться от тех условий, которые мы ещё не использовали, например: "Каждый участник решил не более шести задач". Если мы рассматриваем строку, то не больше, чем 2 чёрные клетки относятся к одной задачке, потому что иначе бы как минимум 3 мальчика решили задачу с чёрной клетки. Хорошо было бы найти строку с большим кол-вом чёрных клеток, чтобы воспользоваться условием на 6 задач, а какой факт помогает нам так оценивать?
Подсказка 3
Верно, это принцип Дирихле, попробуйте как-то оценить кол-во чёрных клеток в строке и красных клеток в столбцах.
Подсказка 4
Да, в какой-то строке обязательно будет как минимум 11 чёрных клеток, что мы тогда можем сказать про кол-во задач, которые решила эта девочка? А сколько тогда мальчиков имеют общую решённую задачу с этой девочкой?
Представим шахматную доску с 
-й строкой, каждая из которых соответствует девочке, и 
-м столбцом, каждый из которых
соответствует мальчику. Тогда каждая клетка соответствует паре «мальчик-девочка».
Предположим, что каждую задачу решили не более двух девочек или не более двух мальчиков. Будем считать задачу «красной», если её решили не более двух девочек и «чёрной»» в противоположном случае (тогда её решили не более двух мальчиков). Каждую клетку покрасим в цвет какой-нибудь из задач, которую решили и мальчик-столбец, и девочка-строка.
По принципу Дирихле в каком-нибудь столбце найдётся 
красных клеток, или в какой-нибудь строке найдутся 
чёрных клеток
(потому что иначе получится, что всего клеток не более чем 
).
Рассмотрим для определённости найденную девочку-строку, содержащую хотя бы 
чёрных клеток. Аналогично разбирается случай,
если вместо этого (чёрных клеток в строке) найдутся 
красных клеток в каком-нибудь столбце и разбирать нужно для
мальчика.
Каждой из найденных чёрных клеток соответствует задача, решённая максимум двумя мальчиками. Тогда мы можем указать не менее 6
различных задач, решённых этой девочкой. В силу первого условия из задачи никаких других задач девочка не решала, но
тогда максимум 
мальчиков имеют общие решённые задачи с этой девочкой, что противоречит второму условию из
задачи.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
