Принцип Дирихле: задача про грибы — правило для ЕГЭ по базовой математике
Коротко
Задача «среди любых 12 грибов хотя бы один рыжик» решается от противного. Если среди любых 12 грибов есть рыжик, значит, груздей не больше 11 — иначе можно было бы набрать 12 груздей. Аналогично, если среди любых 20 грибов есть груздь, рыжиков не больше 19. В корзине 30 грибов: 11 + 19 = 30, значит, груздей ровно 11, рыжиков 19. Та же идея — принцип Дирихле: если «кроликов» больше, чем «клеток», в какой-то клетке окажутся хотя бы двое. Например, из 3 носков двух цветов обязательно найдутся два одного цвета. В ЕГЭ базового уровня это задание 21.
Правило «среди любых k»
«Среди любых k предметов есть хотя бы один A» ⇔ «предметов не-A не больше k − 1».
Принцип Дирихле
Если n · m + 1 предметов разложить по n ящикам, в каком-то ящике окажется не меньше m + 1 предмета.
| Задача | Ответ |
|---|---|
| сколько носков двух цветов вытащить, чтобы была пара | 3 |
| сколько людей нужно, чтобы у троих день рождения был в одном месяце | 2 · 12 + 1 = 25 |
Где в ЕГЭ
Задание 21 базового уровня — задачи на смекалку, 1 балл.
Типичные ошибки
- Берут k, а не k − 1.
- Путают, о каком виде грибов спрашивают.
- В принципе Дирихле считают худший случай неправильно.
Как это выглядит в задании 21
Пример 1 из 3
В корзине 30 грибов: рыжики и грузди. Известно, что среди любых 12 грибов есть хотя бы один рыжик, а среди любых 20 — хотя бы один груздь. Сколько рыжиков в корзине?
- Разбор
- Груздей не больше 11, рыжиков не больше 19. 11 + 19 = 30 — значит, ровно 19 рыжиков.
- Ответ
- 19
Пример 2 из 3
Какое наименьшее число учеников должно быть в школе, чтобы среди них обязательно нашлись трое, родившиеся в одном месяце?
- Разбор
- В худшем случае по 2 человека на каждый из 12 месяцев — 24. Следующий, 25-й, даст третьего.
- Ответ
- 25
Пример 3 из 3
В ящике 10 красных и 10 синих носков. Какое наименьшее число носков нужно вытащить не глядя, чтобы среди них обязательно оказались два одного цвета?
- Разбор
- Худший случай — один красный и один синий. Третий носок создаст пару.
- Ответ
- 3
Мини-тест: 5 вопросов
- Вопрос 1 из 5
Среди любых 8 предметов есть красный. Сколько максимум не красных?
Показать ответ
Ответ: 7.
k − 1.
- Вопрос 2 из 5
Что такое худший случай в принципе Дирихле?
Показать ответ
Ответ: Максимально равномерное распределение.
Его превышаем на 1.
- Вопрос 3 из 5
Сколько носков трёх цветов вытащить для пары?
Показать ответ
Ответ: 4.
3 + 1.
- Вопрос 4 из 5
Груздей ≤ 11 и рыжиков ≤ 19, всего 30. Груздей?
Показать ответ
Ответ: 11.
Иначе сумма меньше 30.
- Вопрос 5 из 5
13 человек — есть ли двое с днём рождения в одном месяце?
Показать ответ
Ответ: Да.
13 > 12.
Проверьте всё задание 21, а не одну тему
Диагностика Upward покажет, какие задания ЕГЭ по базовой математике стоит подтянуть в первую очередь.
Уже есть аккаунт? Войти