MathGURU
УрокиВойти
← К уроку
Олимпиадная математика • 3 класс
Урок 3 из 3
Худший случай
(Перебор и подсчёт)
Фамилия, имя: ______________________________Класс: ______Дата: ________

1. Цель урока

Цель урока
Научиться решать задачи перебором и подсчётом вариантов.

2. Разминка

Повторение пройденного: устно, быстро, без записи в тетради.
  1. 1) Сколько существует двузначных чисел, сумма цифр которых равна 1111?
  2. 2) Сколько двузначных чисел с разными цифрами можно составить из цифр 11, 66, 99?
  3. 3) Сколько существует двузначных чисел, у которых первая цифра на 33 больше второй?

3. Изучаем новый материал

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

  • Представьте самое невезучее развитие событий.
  • kk цветов — чтобы наверняка была пара одного цвета, нужно k+1k + 1 предметов.
  • Принцип Дирихле: если nn клеток и больше n⋅mn \cdot m кроликов, то в какой-то клетке больше mm.
Разберём пример
В мешке 33 красных шара и 44 синих. Какое наименьшее число шаров нужно достать не глядя, чтобы среди них наверняка было хотя бы по два шара каждого цвета?
  1. Худший случай — сначала достаём все шары одного цвета, которых больше: 44.
  2. Потом нужно ещё два шара другого цвета.
  3. 4+2=64 + 2 = 6.
Ответ: 6.

4. Тренировка

Каждое задание тренирует свой образовательный результат — по возрастанию сложности.
Результат: решать задачи перебором и подсчётом вариантов.
Время на выполнение: ≈30 мин
1) Базовый уровень. В ящике носки 22 цветов, каждого цвета много. Сколько носков нужно взять не глядя, чтобы среди них наверняка нашлись два одного цвета?
2) Средний уровень. В мешке 99 красных и 55 синих шариков. Сколько шариков нужно достать не глядя, чтобы среди них наверняка было 66 шариков одного цвета — красного?
3) Средний уровень. В коробке 77 пар одинаковых перчаток. Какое наименьшее число перчаток нужно достать не глядя, чтобы среди них наверняка оказались левая и правая?
4) Средний уровень. В коробке 1010 красных карандашей, 77 синих и 1313 зелёных. Какое наименьшее число карандашей нужно взять не глядя, чтобы среди них наверняка были два карандаша разного цвета?
5) Повышенный уровень. Карточки с числами от 11 до 3737 перевернули и перемешали. Какое наименьшее число карточек нужно взять не глядя, чтобы среди них наверняка была карточка с числом, которое делится на 22?
6) Повышенный уровень. В мешке 1111 красных шаров и 55 синих. Какое наименьшее число шаров нужно достать не глядя, чтобы среди них наверняка было хотя бы по два шара каждого цвета?
7) Повышенный уровень. В мешке 33 красных шара, 1111 синих и 66 зелёных. Какое наименьшее число шаров нужно достать не глядя, чтобы среди них наверняка были шары всех трёх цветов?
8) Повышенный уровень. Есть 55 чемоданов и столько же ключей к ним, но какой ключ от какого чемодана — неизвестно. Какое наименьшее число проб нужно, чтобы наверняка подобрать ключи ко всем чемоданам?
9) Повышенный уровень. В кошельке 1010 монет по 11 р. и 33 монеты по 55 р. Какое наименьшее число монет нужно достать не глядя, чтобы наверняка набралось не меньше 1111 р.?
10) Повышенный уровень. Какое наименьшее количество чисел из 1,2,3,…,121, 2, 3, \ldots, 12 нужно взять, чтобы среди них наверняка нашлись два числа с суммой 1313?
Запиши решение в клетчатом поле: