Всем Привет! Хочу попросить помощи в решении двух задач на подсчет двумя способами. Если это будет возможным дайте сначала подсказки, а потом полный ответ. Так же, хотел бы получить советы о том, как искать двойной подсчет в задачах, как например в четвертой.
в задаче 4 пусть a_{i} количество клубов в которые входит ученик i, тогда попробуй оценить отношение
\frac{\sum C_{a_{i}}^2}{C_{16000}^2}. Насчет того что оно значит, попробуй подумать
2 лайка
в задаче 3 попробуй подумать про “неподвижные точки перестановки” набора, пример: если начальный набор 1, 2, 3, 4, 5, то в наборе 1, 4, 3, 5, 2, ровно две неподвижные точки: 1 и 3
2 лайка
Вот оценка. Могли бы вы мне подсказать, логику решения этой задачи. Как мы должны додуматься и прийти к выведенному вами отношению? А так же, если вам не сложно, шаги решения подобных задач.
Прошлое сообщение писал в спешке, думал инет отключат), думаю так будет лучше:
Принцип Дирихле - основная идея, напомним его.
Дано m кроликов и n клеток, тогда если мы всех кроликов посадили в эти клетки , то существует клетка в которой хотя бы \lceil \frac{m}{n} \rceil кроликов.
Как прийти к принципу Дирихле? Когда просят доказать что есть хотя бы сколько то объектов удовлетворяющих одному условию - это часто указывает на Дирихле
Данное отношение и является отношением “кроликов” и “клеток”, здесь кроликами являются парами клубов, который каждый ученик может выбрать (кстати независимо от других учеников) - \sum C_{a_{i}}^{2}.
Клетками являются всевозможные пары клубов - C_{16000}^{2}, таким образом найдется пара клубов (клетка), в которой хотя бы четыре ученика (кролика).
Кстати, при получении оценки не стоит применять компьютерные методы, могу предложить такую оценку:
\frac{\sum C_{a_{i}}^{2}}{C_{16000}^{2}} = \frac{\sum a_{i}^2 - \sum a_{i}}{16000*15999} \geq \frac{\frac{(\sum a_{i})^2}{1600} - \sum a_{i}}{16000*15999}
(Среднее квадратичное - среднее арифметическое, теперь пусть 16000 = A)
\frac{\frac{(\sum a_{i})^2}{1600} - \sum a_{i}}{16000*15999} = \frac{A^2 - 1600A}{16000*15999*1600} = \frac{A^2(80^2 - 8)}{A*(A-1)*1600} = \frac{A}{A-1}*\frac{80^2 - 8}{1600} \geq\frac{80^2 - 8}{1600} > 3
5 лайков
Спасибо вам большое за подробный ответ и уделённое вами время.
У меня остались лишь два последних вопроса, ответы на которые позволят составить уже полную картину данной задачи у меня в голове и бумажном листе моей тетради.
Как можно прийти к тому, что “кроликами” в нашем случае должны быть именно “Пары клубов, которые каждый ученик может выбрать”, а “клетками” - “Всевозможные пары клубов”?
И почему их отношения даёт число учеников, которые ходят в какие-то два клуба вместе?
Лучше представить задачу в виде графов. У нас будет две доли: в одной вершины – ученики, в другой – клубы. Если ученик ходит в какой-то клуб, между ними будет ребро.
Назовем “галочкой” пару ребер, исходящих из учеников в какие-то два клуба.
Тогда нам нужно доказать, что найдутся хотя бы 4 вершины в доле У (учеников), из которых исходят галочки в одинаковые два клуба.
Теперь, C_{1600}^2 – количество пар клубов, в которые могут исходить эти галочки
\sum С_{a_i}^2 – количество существующих галочек.
Так как нам нужно доказать, что найдется хотя бы 4 галочки, которые исходят в одну пару клубов, использование Дирихле должно показаться логичнее
5 лайков