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

Главное

Принцип Дирихле: если n + 1 предмет разложить в n ящиков, то хотя бы в одном ящике окажется не меньше двух предметов. Обобщение: если больше k · n предметов разложить в n ящиков, то в каком-то ящике больше k предметов.

Правила

1. n + 1 предмет в n ящиков → в каком-то ящике ≥ 2
2. Больше k·n предметов в n ящиков → где-то больше k
3. Сначала найди ящики
4. «Наверняка» — рассмотри худший случай и добавь один

Разберём пример

В ящике носки трёх цветов. Сколько носков нужно вытащить не глядя, чтобы наверняка была пара одного цвета?

4 носка

Частые ошибки

• Путать «хотя бы два» и «ровно два».
• Не рассматривать худший случай и отвечать по «удачному» варианту.

Потренироваться

Задания с проверкой и подсказками, схема темы и разбор ошибок с ИИ-репетитором — в уроке на платформе.