Процессы и алгоритмы

Отсортируем лекции в порядке уменьшения числа записавшихся и поместим по одной лекции на день. Рассмотрим лекцию на которую записалось человек, которая запланирована позже, чем на день. Организуем процесс, где каждым шагом мы выбираем лекцию, запланированную на ближайшую дату после дня, и передвигаем ее на один из дней так, чтобы условие задачи не нарушалось. Ясно, что такой процесс конечен, и в конце все лекции будут распределены по не более чем дням.

Докажем, что мы сможем продолжать процесс (до тех пор, пока не закончатся лекции, запланированные на день). Предположим противное. Допустим, мы хотим передвинуть лекцию но не можем этого сделать. Тогда среди лекций, запланированных на дни можно выбрать по одной пересекающейся с по участникам. Согласно принципу Дирихле, хотя бы из выбранных пересекаются с по одному и тому же записавшемуся, которого мы обозначим Тогда, поскольку никакие две лекции не пересекаются более чем по одному ученику, если исключить из списков участников то лекций не будут пересекаться по участникам. В исходном расписании каждая из них стояла раньше, чем а чем раньше была запланирована лекция, тем больше на нее записавшихся учеников. Поэтому на любую из рассматриваемых лекций записалось хотя бы по человек. Таким образом, количество различных участников рассматриваемых лекций и лекции составляет хотя бы Однако,

для всех ( по условию). Поскольку в Сириусе в принципе только учеников, такого быть не может, и мы достигли противоречия.