TwiddleLab / Математика / Счёт и закономерности
Ящики и голуби
Что ты узнаешь
- Принцип Дирихле: положи больше n вещей в n ящиков, и в каком-то ящике окажется хотя бы две.
- В общем виде в каком-то ящике окажется хотя бы N ÷ k, округлённое вверх: 25 голубей в 12 дырках дают 3.
- Он говорит, что обязано случиться, а не что вероятно. Готовься к худшему случаю.
- Хеш-таблицы живут с этим: имён больше, чем корзин, значит, коллизии неизбежны.
Как идёт урок
В школе на 400 человек обязаны ли двое делить день рождения?
Не вероятно. Обязаны. Какая твоя ставка?
7 голубей, 6 дырок. Дай каждому голубю свою дырку.
Перетаскивай их по одному.
Теперь 12 дырок, по одной на месяц. Сколько голубей заставят 3 оказаться в одном месяце?
Голуби распределяются как можно ровнее. Двигай, чтобы найти наименьшее число.
Если в месяце не больше 2, 12 месяцев вмещают 24. Поэтому 25 заставляют какой-то месяц вместить 3: 25 ÷ 12, округлённое вверх, это 3.
Это принцип Дирихле.
Принцип Дирихле: n + 1 вещей в n ящиках, и в каком-то ящике хотя бы 2.
В общем виде N вещей в k ящиках: в каком-то ящике хотя бы N ÷ k, округлённое вверх.
Он говорит, что обязано случиться при любой раскладке.
Игра: носки против машины.
В ящике темно, а машина всегда выдаёт самые неудачные носки. Задай, сколько вытащить, потом «Вытащить».
5 точек в квадрате 2 на 2. Попробуй держать их подальше друг от друга.
Тяни их куда угодно, потом раздели квадрат.
Обязано случиться или только может?
Перетащи каждую карточку в её коробку.
Хеш-таблица кладёт каждое имя в корзину по формуле.
Нажимай на имена, чтобы добавлять их. Жди двух имён в одной корзине.
В классе 32 ученика. Сколько как минимум обязаны делить месяц рождения?
При 2 на месяц 12 месяцев вмещают только 24 ученика, поэтому при 32 в каком-то месяце обязано быть хотя бы 3.
Вещей больше, чем ящиков: в каком-то ящике две.
Вернёмся к началу. Высыпь всю школу в календарь.
Предыдущий урок: Доказательство домино · Следующий урок: Часовая арифметика: остатки · Часть курса: Счёт и закономерности
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
