Slide - Princípio da Casa dos Pombos - Matemática Discreta - 2023-2

Princ´ıpio da Casa dos Pombos Jeroen van de Graaf DCC - UFMG 02/2021 Intui¸c˜ao Exemplo Dan¸ca de cadeiras: uma cadeira ter´a duas pessoas. Exemplo Casa de pombos (pidgeon hole principle) Introdu¸c˜ao Teorema Se n + 1 objetos (bolas, pessoas) s˜ao divididos (colocados) em n categorias (caixas, cadeiras) ent˜ao h´a pelo menos uma categoria com 2 objetos (bolas, cadeiras). Prova 1 Bom senso. Mesmo assim, uma prova formal ´e melhor. Prova 2 Por contraposi¸c˜ao: suponha que cada categoria tem exatamente 1 objeto. Ent˜ao, o n´umero total de objetos ´e k. Contradi¸c˜ao. Prova 3 Mais pra frente. Exemplo Exemplo Em qualquer grupo de 367 pessoas, deve existir duas com a mesma data (dia+mˆes) de aniver´ario. Exemplo Em qualquer grupo de 27 palavras, deve haver pelo menos duas come¸cando (terminando) com a mesma letra. Corol´ario Corol´ario Seja f : X → Y com |Y | < |X| < ∞. Ent˜ao f n˜ao ´e injetora. Prova Podemos partitionar os elementos x de X conforme sua imagem em Y , definindo f −1[y] = {x ∈ X|f (x) = y} . J´a que |X| > |Y |, pelo Princ´ıpio da casa dos pombos deve existir um f −1[y] com dois ou mais elementos. Ou seja, existe x1 ̸= x2 tal que x1, x2 ∈ f −1[y], i.e. f (x1) = f (x2). Ent˜ao f n˜ao ´e injetora. Exemplo Seja h() uma fun¸c˜ao de hash criptogr´afica, que mapeia uma sequˆencia de bits de tamanho arbitr´ario para uma sequˆencia de 256 bits. Ent˜ao deve existir uma colis˜ao, i.e. x1 ̸= x2 tal que h(x1) = h(x2). Prova |X| = |{0,1}∗| = ∞ > |Y | = |{0,1}256| = 2256 Corol´ario Corol´ario Seja f : X → Y com |Y | < |X| < ∞. Ent˜ao f n˜ao ´e injetora. Prova Podemos partitionar os elementos x de X conforme sua imagem em Y , definindo f −1[y] = {x ∈ X|f (x) = y} . J´a que |X| > |Y |, pelo Princ´ıpio da casa dos pombos deve existir um f −1[y] com dois ou mais elementos. Ou seja, existe x1 ̸= x2 tal que x1, x2 ∈ f −1[y], i.e. f (x1) = f (x2). Ent˜ao f n˜ao ´e injetora. Exemplo Seja h() uma fun¸c˜ao de hash criptogr´afica, que mapeia uma sequˆencia de bits de tamanho arbitr´ario para uma sequˆencia de 256 bits. Ent˜ao deve existir uma colis˜ao, i.e. x1 ̸= x2 tal que h(x1) = h(x2). Prova |X| = |{0,1}∗| = ∞ > |Y | = |{0,1}256| = 2256 Mais um exemplo Exemplo Na regi˜ao metropolitana de BH deve existir duas pessoas com o mesmo n´umero de cabelos, porque a m´edia estimada ´e de 150 mil cabelos, ent˜ao usar um milh˜ao cabelos como limite superior parece razo´avel. E a RMBH tem mais que um milh˜ao de pessoas. PdCdP generalizado Teorema Se n objetos s˜ao colocados em k caixas, ent˜ao h´a pelo menos uma caixa com ⌈ n k ⌉ objetos. Prova (diferente da do livro): Define ci como o n´umero de objetos na caixa i, onde 1 ≤ i ≤ k. Sej´a m a m´edia dos ci, e m o m´aximo dos ci. Ent˜ao o maior n´umero encontrado numa caixa ent˜ao ´e M. Sabe-se que a m´edia ´e sempre menor ou igual ao m´aximo. Mas M ´e sempre um inteiro, ent˜ao m = n k ≤ ⌈ n k ⌉ ≤ M Ou seja M ≥ ⌈ n k ⌉ Casa de pombos simples: M ≥ 2 = ⌈n + 1 n ⌉ PdCdP generalizado Teorema Se n objetos s˜ao colocados em k caixas, ent˜ao h´a pelo menos uma caixa com ⌈ n k ⌉ objetos. Prova (diferente da do livro): Define ci como o n´umero de objetos na caixa i, onde 1 ≤ i ≤ k. Sej´a m a m´edia dos ci, e m o m´aximo dos ci. Ent˜ao o maior n´umero encontrado numa caixa ent˜ao ´e M. Sabe-se que a m´edia ´e sempre menor ou igual ao m´aximo. Mas M ´e sempre um inteiro, ent˜ao m = n k ≤ ⌈ n k ⌉ ≤ M Ou seja M ≥ ⌈ n k ⌉ Casa de pombos simples: M ≥ 2 = ⌈n + 1 n ⌉ PdCdP generalizado Exemplo Entre 100 pessoas, h´a pelo menos ⌈100/12⌉ = 9 que nasceream no mesmo mˆes e ⌈100/7⌉ = 15 que nasceream no mesmo dia da semana. Exemplo Quantas cartas devem ser escolhidas de um baralho de 52 cartas para garantir pelo menos 3 cartas do mesmo naipe? Resposta Com duas cartas de cada naipe estamos no limite, ent˜ao 8 + 1 = 9. Exemplo Quantas cartas devem ser escolhidas para garantir pelo menos 3 copas? Resposta 3 × 13 + 2 + 1 = 42 Demonstracoes surpreendentes O PdCdP aperece em muitas provas, e as vezes resulta em demonstracées surpreendentes Exemplo Existe um multiplo de 2023 que contém apenas Os e 1s na base decimal. Prova Defina a sequéncia a1 = 1, a2 = 11, a3 = 111,..., 2023 = 1...1, ao029 = 1...1. ; ; 2023 2024 Agora considere a sequéncia b; = a; mod 2023,... bn+1 = anti mod 2023. Temos 2024 numeros e 2023 classes de congruéncia, entdo deve existir bj e bj com bj = bj ei <j. Portanto, 0 inteiro aj — aj € um multiplo de 2023. Repare que aj — aj = 1...10...0, entado satisfaz o formato. ~ Y j-i i Demonstra¸c˜oes surpreendentes Exemplo Num torneio de xadrez todos os n participantes jogam um contra o outro. Ent˜ao em cada momento existem dois participantes que tˆem completados o mesmo n´umero de jogos. Os jogadores correspondem com as bolas; o n´umeros de jogos completados, com as caixas. Definimos ci := jogos completados por jogador i. Ent˜ao ci ∈ {0...(n − 1)}, e com n jogadores, parece que o PdCP n˜ao se aplica. Porem, podemos distinguir dois casos: 1. Nenhum jogador completou seus n − 1 jogos. Neste caso, temos que ∀i : ci ∈ {0...(n − 2)}, portanto, pelo PdCP, deve existir i e j tal que ci = cj. 2. No m´ınimo um jogador j´a completou seus n − 1 jogos. J´a que ele jogou contra todos os outros, temos que ∀i : i ≥ 1. Ent˜ao ∀i : ci ∈ {1...(n − 1)}, e o PdCP se aplica de novo. Demonstra¸c˜oes surpreendentes Exemplo Considere um quadrado unit´ario e suponha que ele tem 10 pontos. Ent˜ao existe pelo dois pontos que tˆem distˆancia menor que 0.48. Tamb´em existem 3 pontos cobertos por um disco com raio 0.5. Figura: Quadrado unit´ario Demonstra¸c˜oes surpreendentes Exemplo Durante os ultimos mil anos existia uma pessoa P que ´e ancestral de seu pai e da sua m˜ae. Prova: Por contradi¸c˜ao: Deixe uma gera¸c˜ao corresponder a 25 anos. Ent˜ao mil anos correspondem a 40 gera¸c˜oes. Vamos contar o n´umero de ancestrais, supondo que estas pessoas s˜ao todas distintas. A = 1 + 2 + 4 + 8... + 240 = 241 − 1 ∼= 241 = 2 × 240 = 2 × (210)4 ∼= 2 × (103)4 = 2 × 1012 = 2000 × 109 . Vamos definir uma cota superior ao n´umero de pessoas na terra de mil anos atr´as para c´a. Mesmo supondo 10 bilh˜oes habitantes diferentes a cada 25 anos (completamente absurdo), teriamos apenas 40 × 10 × 109 = 400 × 109 pessoas. Conclus˜ao: n˜ao viviam pessoas suficiente na terra durante os ´ultimos mil anos para todos seus ancestrais seram distintos.