Принцип Дирихле

Худший случай

• •Представьте самое невезучее развитие событий.
• •$k$ цветов — чтобы наверняка была пара одного цвета, нужно $k + 1$ предметов.
• •Принцип Дирихле: если $n$ клеток и больше $n \cdot m$ кроликов, то в какой-то клетке больше $m$.