Problemas matemáticos e raciocínio lógico · Combinatorics & Pigeonhole Principle
Visualizador do princípio da casa dos pombos
Visualizador do princípio da casa dos pombos (princípio de Dirichlet) e análise do pior caso
- No navegador
- Sem cadastro
- Dedução ao vivo
- Modo projetor
- Folha de exercícios A4
Janela de demonstração matemática● 60 FPS
Variáveis de controle do experimento
Deduções e métricas em tempo real
Mínimo garantido em pelo menos 1 caixa
--
Quociente inteiro q
--
Resto r
--
Limite do pior caso
--
Dedução de fórmulas em tempo real
Fórmula fundamental:
--Substituição de valores:
--Conclusão: --
Exemplos clássicos e armadilhas de exame
Worked Problem
Problema: 370 students graduate. At least how many share a birth month? A birthday?
Derivação passo a passo:
- 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
Problema: 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?
Derivação passo a passo:
- 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.
Folha de investigação em aula e exercícios
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.
Perguntas frequentes e erros comuns
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.