Что такое принцип Дирихле: определение термина
Принцип Дирихле еще называют принципом голубятни. Он говорит: если n+1объектов разложить по n ящикам, то в одном ящике будет не меньше двух объектов. Здесь важно сравнение количества: объектов больше, чем мест для них.
Принцип работает не только про настоящие ящики, он подходит для чисел, людей, дат, цветов, остатков при делении и других ситуаций. Его часто применяют в задачах, где нужно не найти точный объект, а доказать, что нужная ситуация точно существует.
Как применять принцип Дирихле
Сначала решите, что будет объектами, а что ящиками. Потом сравните их количество. Если объектов больше, вывод уже готов: где-то произойдет совпадение. Например, среди 13 человек обязательно найдутся двое, у которых день рождения в одном и том же месяце, потому что месяцев 12, а людей 13.
Другой пример: если взять 6 целых чисел, то у двух из них совпадает остаток при делении на 5, потому что возможных остатков всего 5. Иногда используют усиленную версию: если k объектов распределены по n ящикам, то в каком-то ящике будет не меньше ⌈k/n⌉объектов.
