Сюжетные математические задачи и логика · Combinatorics & Pigeonhole Principle
Визуализатор принципа Дирихле и наихудшего сценария
Интерактивный визуализатор принципа Дирихле: гарантированный выбор пар носков и шаров
- В браузере
- Без регистрации
- Вывод формул
- Режим проектора
- Печатный лист A4
Окно математической демонстрации● 60 FPS
Параметры эксперимента
Расчёты и показатели в реальном времени
Гарантированный минимум в одном ящике
--
Неполное частное q
--
Остаток r
--
Порог худшего случая
--
Вывод формул в реальном времени
Основная формула:
--Подстановка значений:
--Вывод: --
Разбор типовых задач и анализ экзаменационных ошибок
Worked Problem
Условие задачи: 370 students graduate. At least how many share a birth month? A birthday?
Пошаговый вывод формул:
- Months: 370 / 12 = 30 R 10 => at least 30 + 1 = 31 in same month. Days: 370 / 366 = 1 R 4 => at least 1 + 1 = 2 share birthday.
Worked Problem
Условие задачи: Bag has 8 red, 7 yellow, 5 blue, 3 white balls. Minimum draws to guarantee: 1) a matching pair; 2) at least 1 blue ball?
Пошаговый вывод формул:
- 1) Matching pair: 4 colors + 1 = 5 draws. 2) Blue guaranteed: exhaust all non-blue (8+7+3 = 18), then draw 1 = 18 + 1 = 19 draws.
Рабочий лист для урока и домашние задания
Q1. Variant 1: Does any set of 5 consecutive integers contain a multiple of 5? Why?
Answer Key: Always! Remainders modulo 5 are {0, 1, 2, 3, 4} (5 drawers). 5 consecutive integers map to all 5 remainders, including remainder 0.
Q2. Variant 2: Standard 52-card deck (4 suits of 13). Minimum draws to guarantee at least 3 cards of the same suit?
Answer Key: Worst case: draw 2 cards of each of the 4 suits = 4 * 2 = 8 cards. Next card makes a triplet: 8 + 1 = 9 cards.
Q3. Variant 3: Prove that placing 5 points inside an equilateral triangle of side 1 guarantees two points closer than 0.5.
Answer Key: Connect midpoints of sides to divide into 4 smaller equilateral triangles of side 0.5. 5 points into 4 triangles forces 2 into one triangle.
Часто задаваемые вопросы и типичные заблуждения
If division has remainder 2 or 3, is the pigeonhole formula still Quotient + 1?
Yes, strictly Quotient + 1! Any non-zero remainder ceiling-rounds up. Only when remainder is exactly 0 does it equal Quotient.
How do Worst-Case Scenario and Pigeonhole Principle interrelate?
They are dual inverses! Pigeonhole takes inputs and derives minimum guarantees. Worst-case takes target goals and back-calculates required sample size.
Do two people in Beijing have the exact same number of hairs? Prove via pigeonhole.
Human scalp has <300,000 hairs. Beijing has >20,000,000 people. 20M people in 300K drawers forces multiple people to share the exact hair count.
How does the pigeonhole principle dictate hash table collisions in computer science?
Mapping keys to finite buckets inevitably produces collisions when keys exceed bucket capacity, mandating collision resolution chains.