Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Помогите пожалуйста очень срочно надо

Григорий Акмурзин Ученик (112), на голосовании 8 месяцев назад
В школе учатся 2023 мальчика и 2023 девочки. Каждый ученик посещает не более чем 100 кружков. Известно, что любые два школьника противоположного пола посещают один и тот же кружок. Покажите, что существует кружок, который посещают не менее 11 девочек и не менее 11 мальчиков.
Голосование за лучший ответ
Максим Сатанист Ученик (206) 9 месяцев назад
Из предоставленных условий следует что каждый ученик посещает не более 100 кружков а общее количество учеников составляет 2023 мальчика и 2023 девочки. Мы хотим доказать что существует кружок в котором посещается не менее 11 девочек и не менее 11 мальчиков.

Допустим противное - предположим что такого кружка не существует. Каждый ученик может посещать не более 100 кружков следовательно общее количество возможных кружков составляет не более 100 * 2023 = 202300.

Теперь рассмотрим количество возможных пар между девочками и мальчиками. У нас есть 2023 девочки и 2023 мальчика поэтому всего имеется 2023 * 2023 = 4092529 возможных пар.

Учитывая что всего возможно 4092529 пар и не более 202300 кружков по принципу Дирихле (принципу ящиков как минимум одному кружку должно соответствовать более одной пары учеников.

Теперь рассмотрим этот кружок. Так как любые два ученика противоположного пола которые посещают один и тот же кружок должны посещать один и тот же кружок значит в этом кружке должно быть как минимум 11 девочек и 11 мальчиков.

Таким образом мы доказали что существует кружок в котором посещается не менее 11 девочек и не менее 11 мальчиков.
Даниил Кукин Ученик (124) 9 месяцев назад
Из предоставленных условий следует что каждый ученик посещает не более 100 кружков а общее количество учеников составляет 2023 мальчика и 2023 девочки. Мы хотим доказать что существует кружок в котором посещается не менее 11 девочек и не менее 11 мальчиков.

Допустим противное - предположим что такого кружка не существует. Каждый ученик может посещать не более 100 кружков следовательно общее количество возможных кружков составляет не более 100 * 2023 = 202300.

Теперь рассмотрим количество возможных пар между девочками и мальчиками. У нас есть 2023 девочки и 2023 мальчика поэтому всего имеется 2023 * 2023 = 4092529 возможных пар.

Учитывая что всего возможно 4092529 пар и не более 202300 кружков по принципу Дирихле (принципу ящиков как минимум одному кружку должно соответствовать более одной пары учеников.

Теперь рассмотрим этот кружок. Так как любые два ученика противоположного пола которые посещают один и тот же кружок должны посещать один и тот же кружок значит в этом кружке должно быть как минимум 11 девочек и 11 мальчиков.

Таким образом мы доказали что существует кружок в котором посещается не менее 11 девочек и не менее 11 мальчиков.
Похожие вопросы