Олимпиадная математика • 4 класс
Урок 2 из 3
Принцип Дирихле
(Комбинаторика и графы)
Фамилия, имя: ______________________________Класс: ______Дата: ________
1. Цель урока
Цель урока
Научиться решать задачи перебором и подсчётом вариантов; решать логические задачи, рассуждая по шагам.
2. Разминка
Повторение пройденного: устно, быстро, без записи в тетради.
- 1) В группе 21 ученик. Сколькими способами можно выбрать дежурного и его помощника?
- 2) Сколько двузначных чисел с разными цифрами можно составить из цифр 2, 3, 6, 7, 8?
- 3) У Маши 4 юбки и 2 кофты. Сколько разных нарядов «юбка + кофта» она может составить?
3. Изучаем новый материал
Худший случай
- Представьте самое невезучее развитие событий.
- k цветов — чтобы наверняка была пара одного цвета, нужно k+1 предметов.
- Принцип Дирихле: если n клеток и больше n⋅m кроликов, то в какой-то клетке больше m.
Разберём пример
В мешке 15 красных и 6 синих шариков. Сколько шариков нужно достать не глядя, чтобы среди них наверняка было 5 шариков одного цвета — красного?- В худшем случае сначала вытащим все 6 синих.
- Затем нужно ещё 5 красных: 6+5=11.
Ответ: 11.
4. Тренировка
Каждое задание тренирует свой образовательный результат — по возрастанию сложности.
Результат: решать задачи перебором и подсчётом вариантов.
Время на выполнение: ≈26 мин
1) Базовый уровень. В ящике носки 7 цветов, каждого цвета много. Сколько носков нужно взять не глядя, чтобы среди них наверняка нашлись два одного цвета? 2) Средний уровень. Сколько карандашей нужно разложить в 9 коробок, чтобы наверняка в какой-то коробке оказалось не меньше 4 карандашей? 3) Средний уровень. В школе 302 ученика. Какое наибольшее число учеников можно гарантировать, родившихся в одном и том же месяце (при любых днях рождения)? 4) Средний уровень. В коробке 8 пар одинаковых перчаток. Какое наименьшее число перчаток нужно достать не глядя, чтобы среди них наверняка оказались левая и правая? 5) Средний уровень. В коробке 4 красных карандаша, 5 синих и 13 зелёных. Какое наименьшее число карандашей нужно взять не глядя, чтобы среди них наверняка были два карандаша разного цвета? 6) Повышенный уровень. В мешке 13 красных и 5 синих шариков. Сколько шариков нужно достать не глядя, чтобы среди них наверняка было 13 шариков одного цвета — красного? 7) Повышенный уровень. В мешке 3 красных шара, 7 синих и 8 зелёных. Какое наименьшее число шаров нужно достать не глядя, чтобы среди них наверняка были шары всех трёх цветов? 8) Повышенный уровень. В кошельке 6 монет по 1 р. и 4 монеты по 5 р. Какое наименьшее число монет нужно достать не глядя, чтобы наверняка набралось не меньше 17 р.? 9) Повышенный уровень. Какое наименьшее количество чисел из 1,2,3,…,14 нужно взять, чтобы среди них наверняка нашлись два числа с суммой 15? Запиши решение в клетчатом поле:
Результат: решать логические задачи, рассуждая по шагам.
Время на выполнение: ≈9 мин
10) Повышенный уровень. Можно ли утверждать, что среди любых 5 натуральных чисел найдутся два, разность которых делится на 7? В ответ запишите «да» или «нет». 11) Повышенный уровень. Можно ли утверждать, что среди любых 9 натуральных чисел найдутся два, разность которых делится на 9? В ответ запишите «да» или «нет». 12) Повышенный уровень. Можно ли утверждать, что среди любых 8 натуральных чисел найдутся два, разность которых делится на 6? В ответ запишите «да» или «нет». Запиши решение в клетчатом поле:
