В чем заключается принцип Дирихле в комбинаторике?

Принцип Дирихле в комбинаторике заключается в следующем утверждении: mit.spbau.ru если в n ящиков положить k > n предметов (в n клеток посадить k > n голубей), то хотя бы в одном ящике будут лежать по крайней мере два предмета (будут сидеть по крайней мере два голубя). mit.spbau.ru

Более обобщённая формулировка принципа Дирихле: если m кроликов рассажены в n клеток, то хотя бы в одной клетке находится не менее m/n кроликов, а также хотя бы в одной клетке находится не более m/n кроликов. klub-kod.ru

Принцип Дирихле является эффективным способом решения многих комбинаторных задач. mit.spbau.ru

Пример применения: если в тёмном ящике шкафа разбросаны четыре пары носок различных цветов, то среди выбранных не глядя пяти носков всегда найдётся пара одного цвета. uroki-sovy.ru