Условие
В эксперименте №4 есть шары 8 цветов. Сколько шаров минимум вынуть вслепую, чтобы гарантировать 3 шаров одного цвета?
Подсказка
В худшем случае каждого цвета по k−1.
Следующий шар создаст нужную группу.
Показать ответ
17
Пошаговое решение
- Строим случай без нужной группы
Можно получить по 2 шаров каждого из 8 цветов: 8·2=16 шаров. При этом 3 шаров одного цвета ещё нет.
- Добавляем следующий шар
Следующий шар имеет один из этих 8 цветов. У этого цвета станет как минимум 3 шаров, поэтому 16+1=17 уже достаточно.
- Обосновываем минимальность
Для 16 шаров построен неподходящий случай, а 17 гарантирует нужную группу по принципу Дирихле. Значит минимум 17.
Ответ: 17