O Princípio da Casa dos Pombos, também conhecido como O Princípio das Gavetas de Dirichlet, surgiu em 1834, o conceito foi utilizado pelo matemático alemão Johann Peter Gustav Lejeune Dirichlet, estudante da Universidade de Paris, que trabalhou nas Universidades de Breslau e Berlim, posteriormente sendo escolhido como sucessor de Johann Carl Friedrich Gauss na Universidade de Göttingen. Dirichlet foi responsável por grandes avanços na Matemática, especialmente na área de Teoria dos Números.
Figura2.5.1.Johann Peter Gustav Lejeune Dirichlet, fonte: gigantesdamatematica.wordpress.com/
Subseção2.5.21ª versão do Princípio da Casa dos Pombos
Teorema2.5.2.
Se \(k+1\) pombos forem colocados em \(k\) casas, então existe pelo menos uma casa contendo dois ou mais pombos.
Demonstração.
Suponha que nenhuma das \(k\) casas contém mais de um pombo. Então o número total de pombos seria no máximo \(k\text{.}\) Isto é uma contradição, já que existem pelo menos \(k+1\) pombos.
Nota2.5.3.
Podemos interpretar o princípio usando funções da seguinte forma: Sejam \(\mathcal{P}\) e \(\mathcal{C}\text{,}\) dois conjuntos. Se o número de elementos de \(\mathcal{P}\) for maior que o números de elementos de \(\mathcal{C}\text{,}\) então não existe uma função injetiva de \(\mathcal{P}\) para \(\mathcal{C}\text{,}\) ou seja, pelo menos dois elementos do domínio terão a mesma imagem, independente da função entre \(\mathcal{P}\) e \(\mathcal{C}\text{.}\)
Essencialmente, para usar este princípio, precisamos identificar dois conjuntos, que chamaremos sugestivamente de \(\mathcal{P}\) e \(\mathcal{C}\) para representarem o conjunto dos pombos e o conjunto das casas, respectivamente. Em seguida comparamos o número de elementos entre eles.
Exemplo2.5.4.
Mostre que, em um grupo de 367 pessoas, pelo menos duas fazem o aniversário no mesmo dia.
Solução.
Chame de \(\mathcal{P}\) o conjunto das pessoas e \(\mathcal{C}\) o conjunto dos dias do ano. Desta forma como temos mais elementos em \(\mathcal{P}\) do que em \(\mathcal{C}\text{,}\) pelo princípio da casa dos pombos, pelo menos duas pessoas fazem aniversário no mesmo dia.
Exemplo2.5.5.
Mostre que entre nove números que não possuem divisores primos maiores que cinco, existem dois cujo produto é um quadrado.
Solução.
Inicialmente observe que, qualquer número inteiro que não possui divisor primo maior que cinco, se escreve na forma \(2^a3^b5^c\text{,}\) com \(a, b\) e \(c\) inteiros não negativos.
Defina um conjunto com 9 números arbitrários que satisfaçam as hipóteses do enunciado:
Como os expoentes \(a_i, b_i\) e \(c_i\) só podem ser pares ou ímpares, seja \(\mathcal{C}\) um conjunto que represente todas as paridades possíveis para os expoentes de 2, 3 e 5 em \(2^a3^b5^c\text{.}\) Este conjunto possui 8 elementos, pois temos duas possibilidades para a paridade de cada um dos 3 expoentes.
Como o conjunto \(\mathcal{P}\) é formado por nove elementos, pelo princípio da casa dos pombos, teremos dois elementos em \(\mathcal{P}\text{,}\) cujos expoentes possuem a mesma paridade, digamos que \(2^{a_i}3^{b_i}5^{c_i}\) e \(2^{a_j}3^{b_j}5^{c_j}\text{.}\)
O produto entre eles é da forma \(2^{a_i+a_j}3^{b_i+b_j}5^{c_i+c_j}=2^{2x}3^{2y}5^{2z}\text{,}\) com \(x, y, z \in \mathbb{N}\text{,}\) que é um quadrado, pois pode ser escrito na forma
(IMO 1972) Prove que, de qualquer conjunto de dez números naturais distintos de dois dígitos, podemos escolher dois subconjuntos A e B (disjuntos) cuja a soma dos elementos é a mesma em ambos.
Solução.
Seja \(S\) um conjunto com 10 números naturais distintos de dois dígitos. A soma de todos os elementos de \(S\) pode ser no máximo 945, no caso em que \(S=\{90, 91, \ldots, 99\}\text{.}\)
Considere o conjunto das partes de \(S\text{,}\) ou seja, o conjunto formado por todos os subconjuntos de \(S\text{.}\) Este conjunto possui \(2^{10}\) elementos, sendo um deles o conjunto vazio, pois para formar um subconjunto de \(S\text{,}\) precisamos decidir se cada elemento de \(S\) vai pertencer ou não a este subconjunto.
Defina \(\mathcal{C} = \{ 1, 2, \ldots, 945 \}\) e \(\mathcal{P}\) como o conjunto das partes de \(S\text{,}\) menos o conjunto vazio. Desta forma \(\mathcal{P}\) possui \(2^{10}-1 = 1023\) elementos.
Observe que um elemento de \(\mathcal{P}\) é um subconjunto de \(S\) e que a soma dos elementos de um elemento de \(\mathcal{P}\) será um número que pertence a \(\mathcal{C}\text{.}\) Pelo princípio da casa dos pombos, como temos mais elementos em \(\mathcal{P}\) do que em \(\mathcal{C}\text{,}\) pelo menos dois elementos \(A, B \in \mathcal{P}\) possuem a mesma soma.
Se \(A\) e \(B\) forem disjuntos, acabou. Se não, considere \(A' = A- A\cap B\) e \(B' = B - A \cap B\text{.}\) Logo, os conjuntos \(A'\) e \(B'\) são disjuntos e a soma dos seus elementos é a mesma.
Subseção2.5.32ª versão do Princípio da Casa dos Pombos
Nota2.5.7.
Para uma versão mais geral do princípio da casa dos pombos, vamos usar a função teto:
ou seja, é o menor inteiro que é maior ou igual a \(x\text{.}\) Observe que \(\lceil x \rceil \lt x +1 \text{,}\) para qualquer \(x \in \mathbb{R}\text{.}\)
na qual, a desigualdade \(\left\lceil \frac{n}{k} \right\rceil \lt \frac{n}{k} +1 \) foi usada. Esta é uma contradição, pois existem um total de \(n\) pombos.
Exemplo2.5.10.
Nove pontos são colocados no interior de um triângulo de área 4\(cm^2\text{,}\) de forma que não tenha 3 pontos colineares. Mostre que podemos escolher três deles para serem os vértices de um triângulo de área no máximo igual a 1\(cm^2\text{.}\)
Solução.
Sejam \(A, B\) e \(C\) os vértices do triângulo de área 4\(cm^2\text{.}\) Considere três pontos \(D_1, D_2\) e \(D_3\) na arestas \(BC\text{,}\) de forma que \(ABD_1, AD_1D_2, AD_2D_3\) e \(AD_3C\) formem quatro triângulos, cada um com área de 1\(cm^2\text{.}\)
Desta forma ao colocar os pontos no triâgulo \(ABC\text{,}\) pelo princípio da casa dos pombos, existem pelo menos \(\lceil 9/4 \rceil = 3\) pontos em um dos quatro triângulos: \(ABD_1, AD_1D_2, AD_2D_3\) e \(AD_3C\text{.}\)
Figura2.5.11.Triângulo subdividido.
Logo os três pontos que estão dentro de um destes 4 triângulos, por não serem colineares, formam um triângulo de área no máximo igual a 1\(cm^2\text{.}\)
Exemplo2.5.12.
(Putnam 1953). Assuma que em um grupo de 6 pessoas, cada par de pessoas consistem em dois amigos ou dois inimigos. Mostre que ou existem 3 amigos mútuos ou 3 inimigos mútuos.
Solução.
Seja \(A\) uma das 6 pessoas. Sejam \(\mathcal{C}=\{\{\mbox{amigo de }A\}, \{\mbox{inimigo de }A\}\}\) e \(\mathcal{P} = \{B, C, D, E, F\}\) o conjunto com as outras 5 pessoas.
Pela 2ª versão do princípio da casa dos pombos, dividindo as 5 pessoas de \(\mathcal{P}\) nos 2 conjuntos de \(\mathcal{C}\text{,}\) um desses conjuntos possui pelo menos \(\lceil 5/2 \rceil = 3\) elementos. Então, ou existem 3 ou mais que são amigos de \(A\text{,}\) ou 3 ou mais que são inimigos de \(A\text{.}\)
Suponha sem perda de generalidade que \(B, C\) e \(D\) sejam amigos de \(A\text{.}\) Se quaisquer duas destas 3 pessoas são amigas, então estas duas pessoas e \(A\) formam um conjunto de 3 amigos mútuos.
Nota2.5.13.
A solução do Exemplo 2.5.12, é equivalente a demonstração de que o número de Ramsey \(R(3,3)\leq 6\text{.}\) A Teoria de Ramsey é uma área importante da Combinatória, mais especificamente da teoria dos Grafos. O número de Ramsey, \(n = R(v, a)\text{,}\) é o menor inteiro \(n\) tal que o grafo completo bicolorido \(K_n\text{,}\) nas cores vermelho e azul para arestas, possui um subgrafo completo monocromático vermelho \(K_v\) ou um subgrafo completo monocromático azul \(K_a\text{.}\) Para mais informação sobre a Teoria de Ramsey, veja [6.14]. Determinar um número de Ramsey em geral é muito difícil e é um problema em aberto. Para determinar o número \(R(4,5) = 25\text{,}\) que foi descoberto em 1993, foram necessários 11 anos de tempo de processamento em 110 computadores desktop.
Exercícios2.5.4Exercícios
1.
Qual é o número mínimo de pessoas que deve haver em um grupo para que possamos garantir que nele haja pelo menos 5 pessoas nascidas no mesmo mês?
Resposta.
49
Solução.
Pelo Teorema 2.5.9 basta encontrar o menor número inteiro \(n\text{,}\) tal que
Como \(4\times 12=48\text{,}\) o valor de \(n\) é 5.
2.
Escolhem-se ao acaso 5 pontos sobre a superfície de um quadrado de lado 2. Mostre que pelo menos um dos segmentos que eles determinam tem comprimento menor ou igual a \(\sqrt{2}\text{.}\)
Solução.
Dividindo o quadrado de lado 2 em 4 quadrados de lado 1 ficamos com quatro regiões, nas quais, a maior distância possível entre dois pontos é determinado pelas diagonais, cujo comprimento mede \(\sqrt{2}\text{.}\) Se os segmentos determinados pelos quatro primeiros pontos ainda não satisfazem a condição do enunciado, necessariamente, ao escolher o quinto ponto, ele ficará em um dos quatro quadrados que já possuem um ponto cada um. Portando dentre todos os segmentos determinados pelos cinco pontos, a menor distância será menor ou igual a \(\sqrt{2}\text{.}\)
3.
(IMO 1964) 17 pessoas se comunicam por cartas. Em todas a cartas, eles discutem apenas um dos três tópicos possíveis. Cada par de pessoas discute apenas um tópico. Mostre que há pelo menos três pessoas que discutiram apenas um tópico.
Solução.
Selecione uma pessoa qualquer e chame de \(P_1\text{.}\) Como \(P_1\) se comunica com 16 outras pessoas e são apenas 3 tópicos possíveis, pelo Teorema 2.5.9\(P_1\) deve discutir sobre um mesmo tópico com pelo menos 6 pessoas, pois
Suponha que \(P_1\) discute o tópico I com 6 pessoas. Se qualquer uma dessas seis pessoas discutir com outra dessas 6 pessoas sobre o tópico I, então há 3 escritores correspondentes no tópico I. (O triângulo verde da Figura 2.5.14 representa as 3 pessoas que discutem o mesmo tôpico.)
Figura2.5.14.3 pessoas que discutem o tópico 1.
Portanto, suponha que dentre essas seis pessoas apenas os tópicos II e III são discutidos. Se \(P_2\) for um desses seis, então pelo Teorema 2.5.9\(P_2\) deve discutir com pelo menos 3 dos outros 5 um dos dois tópicos, digamos II, pois
Ainda, existem duas possibilidades para essas três últimas pessoas.
Figura2.5.15.3 pessoas que discutem o tópico II ou o tópico III. Se alguém escreve para outra pessoa sobre o tópico II, então encontramos três pessoas discutindo sobre o tópico II. Caso contrário, se nenhum dos três escreve para outro sobre o tópico II, então todos os três devem escrever um para o outro sobre o tópico III. Isso prova o afirmação.
4.
(IMO 1985) Seja \(A\) um conjunto com 1985 inteiros positivos, de modo que nenhum possui um divisor primo maior que 23. Mostre que em \(A\) existem 4 inteiros, cujo produto é o quarta potência de um inteiro.
Solução.
Existem nove primos menores ou iguais a \(23\text{:}\)\(2, 3, 5, 7, 11, 13, 17, 19\) e \(23\text{.}\) Considere uma lista, com \(9\) entradas, para cada um dos 1985 números, de modo que cada entrada seja a potência do respectivo primo que aparece na fatoração do número. Por exemplo, se o número
Para que existam 4 interios, cujo produto seja a quarta potência de um inteiro, é suficiente mostrar que é possível encontrar 4 listas, tais que, se forem somadas entrada a entrada, cada uma dessas novas entradas será divisível por 4.
Para cada uma das 1985 listas \(L_n\text{,}\) considere uma nova lista \(L_n^2\text{,}\) na qual, cada entrada será o resto da divisão por 2, da entrada da lista original (ou seja, módulo 2). Por exemplo:
Assim, cada nova lista \(L_n^2\) estará entre as 512 possíveis listas distintas. Dessa forma, pelo Princípio da Casa dos Pombos, para cada 513 listas \(L_n^2\text{,}\) haverão duas idênticas. Considere quaiquer 513 listas \(L_n^2\text{,}\) separe o par idêntico e repita esse processo até sobrarem 511 listas. No final desse processo, foram separadas 737 pares de listas.
Para cada um dos 737 pares, considere uma lista \(L_{n+m}^2\) formada pela soma \(L_n^2+L_m^2\text{.}\) Observe que cada entrada das 737 listas \(L_{n+m}^2\) é igual a zero ou a dois. Como só existem 512 listas diferentes, com entradas 0 ou 2, pelo Princípio da Casa dos Pombos, pelo menos duas das listas \(L_{n+m}^2\) serão idênticas. Digamos que \(L_{n+m}^2\) e \(L_{p+q}^2\text{,}\) então o número \(n\times m\times p\times q\) é a quarta potência de um inteiro.
5.
(Vietnam 2007) Dado um polígono regular com \(2007\) lados, encontre o menor inteiro positivo \(k\) tal que entre quaisquer \(k\) vértices do polígono existam \(4\) com a propriedade: o quadrilátero convexo que eles formam compartilha \(3\) lados com o polígono.
Solução.
Numere os vértices do polígono de \(1\) a \(2007\text{.}\) O que queremos descobir é o menor valor de \(k\text{,}\) tal que, qualquer conjunto com \(k\) vértices possua pelo menos \(4\) vértices consecutivos.
Considere o conjunto das \(4\)-tuplas de vértices consecutivos:
Cada vértice do polígono está presente em 4 elementos do conjunto \(T_4\text{.}\) Desse modo, cada vértice escolhido no polígono correspondem a 4 elementos de \(T_4\text{.}\) Como \(T_4\) possui \(2007\) elementos, escreva uma lista \(L\) com os números de todas as \(4\)-tuplas de forma consecutiva, formando uma lista com \(4\times 2007\) números.
Na lista \(L\) podemos escolher até \(3\times 2007\) números, de forma que não tenham \(4\) elementos consecutivos. Então, como cada vértice do polígono correspondem a \(4\) elementos de \(L\text{,}\) se \(4k>3\times 2007\text{,}\) teremos a condição satisfeita: qualquer conjunto de \(k\) vértices possui pelo menos \(4\) vértices consecutivos. Fazendo as contas,
Agora precisamos monstrar que o menor valor de \(k\) é \(1506\text{.}\) Vamos escolher \(1505\) vértices de forma que não tenham \(4\) vértices consecutivos. Considere todos os vértices do polígono, menos o vértice \(2007\) e os vértices que são múltiplos de \(4\text{.}\) Como \(2007 = 501\times 4+3\text{,}\) temos \(501\) múltiplos de \(4\text{,}\) dessa forma temos \(2007-501-1 = 1505\) vértices sem que \(4\) deles sejam consecutivos.
6.
(OMM 2003) Há \(n\) meninos e \(n\) meninas em uma festa. Cada menino gosta de \(a\) meninas e cada menina gosta de \(b\) meninos. Encontre todos os pares \((a, b)\) de forma que sempre deve haver ser um menino e uma menina que gostam um do outro.
Solução.
Considere os pares \((r, s)\text{,}\) na qual \(r\) é um menino que gosta da menina \(s\text{.}\) Para cada menino, existem \(a\) pares, então existem \(a\times n\) pares. Portanto existe uma menina em \(a\) desses pares, ou seja, existe uma menina que pelo menos \(a\) meninos gostam dela. Se essa menina gosta de mais que \(n-a\) meninos, então podemos encontrar o par desejado. Portanto, se \(a+b>n\text{,}\) podemos encontrar um par.
Se \(a+b \leq n\) vamos mostar que nem sempre é possível encontrar um par satisfazendo a condição do enunciado. Vamos numerar os meninos e as meninas de \(1\) a \(n\text{.}\) Dado um par \((i, j)\text{,}\) com a primeira entrada correspondendo a menina e a segunda entrada correspondendo ao menino. Diremos que \(i\) gosta de \(j\text{,}\) se \(i+j\) deixar resto que pertence ao conjunto \(\{1, 2, 3, \ldots, b\}\text{,}\) na divisão por \(n\text{.}\) Diremos que \(j\) gosta de \(i\text{,}\) se \(i+j\) deixar resto que pertence ao conjunto \(\{0, n-1, \ldots, n-a+1\}\text{,}\) na divisão por \(n\text{.}\) Com isso, cada menino gosta de \(a\) meninas, cada menina gosta de \(b\) meninos e não existe um par que os dois se gostem.
