Голосование за лучший ответ
Максим Сатанист
Ученик
(216)
1 год назад
Из предоставленных условий следует что каждый ученик посещает не более 100 кружков а общее количество учеников составляет 2023 мальчика и 2023 девочки. Мы хотим доказать что существует кружок в котором посещается не менее 11 девочек и не менее 11 мальчиков.
Допустим противное - предположим что такого кружка не существует. Каждый ученик может посещать не более 100 кружков следовательно общее количество возможных кружков составляет не более 100 * 2023 = 202300.
Теперь рассмотрим количество возможных пар между девочками и мальчиками. У нас есть 2023 девочки и 2023 мальчика поэтому всего имеется 2023 * 2023 = 4092529 возможных пар.
Учитывая что всего возможно 4092529 пар и не более 202300 кружков по принципу Дирихле (принципу ящиков как минимум одному кружку должно соответствовать более одной пары учеников.
Теперь рассмотрим этот кружок. Так как любые два ученика противоположного пола которые посещают один и тот же кружок должны посещать один и тот же кружок значит в этом кружке должно быть как минимум 11 девочек и 11 мальчиков.
Таким образом мы доказали что существует кружок в котором посещается не менее 11 девочек и не менее 11 мальчиков.
Даниил Кукин
Ученик
(131)
1 год назад
Из предоставленных условий следует что каждый ученик посещает не более 100 кружков а общее количество учеников составляет 2023 мальчика и 2023 девочки. Мы хотим доказать что существует кружок в котором посещается не менее 11 девочек и не менее 11 мальчиков.
Допустим противное - предположим что такого кружка не существует. Каждый ученик может посещать не более 100 кружков следовательно общее количество возможных кружков составляет не более 100 * 2023 = 202300.
Теперь рассмотрим количество возможных пар между девочками и мальчиками. У нас есть 2023 девочки и 2023 мальчика поэтому всего имеется 2023 * 2023 = 4092529 возможных пар.
Учитывая что всего возможно 4092529 пар и не более 202300 кружков по принципу Дирихле (принципу ящиков как минимум одному кружку должно соответствовать более одной пары учеников.
Теперь рассмотрим этот кружок. Так как любые два ученика противоположного пола которые посещают один и тот же кружок должны посещать один и тот же кружок значит в этом кружке должно быть как минимум 11 девочек и 11 мальчиков.
Таким образом мы доказали что существует кружок в котором посещается не менее 11 девочек и не менее 11 мальчиков.