domingo, 22 de julho de 2012


Princípio da Casa dos Pombos

O Principio da Casa dos Pombos nos diz que para colocarmos n + 1 pombos em n gaiolas, pelo menos uma gaiola deverá conter pelo menos dois pombos. Essa ideia tão óbvia é, na realidade, uma poderosa ferramenta na demonstração de muitos resultados bastante difíceis. O que, muitas vezes, torna o problema difícil é a construção de um conjunto ou conjuntos aos quais se possa aplicar esse princípio.

Esse princípio é também conhecido como “Princípio das Gavetas de Dirichlet” por ter sido por ele enunciado como: “Se n + 1 objetos são colocados em n gavetas, então pelo menos uma gaveta deverá conter, pelo menos, dois objetos”.

Exemplo 1. Mostrar que, numa festa de aniversário com mais de 12 crianças, existem pelo menos duas nascidas no mesmo mês e que também existem pelo menos duas nascidas no mesmo dia da semana.

Solução: Como temos mais crianças (pombos) do que meses (gaiolas), pelo menos um “mês” deverá conter pelo menos duas “crianças”. Na segunda parte, sendo o número de crianças maior do que 7, necessariamente duas ou mais terão nascido no mesmo dia da semana.

Exemplo 2. Mostrar que todo subconjunto de {1, 2, 3,..., 2n}, contendo n + 1 elementos, possui um par de elementos primos entre si.

Solução: É fácil observar que os únicos subconjuntos de {1, 2, 3,..., 2n} contendo n elementos, não-consecutivos, são{1, 3, 5,..., 2n – 1} e {2, 4, 6,..., 2n}. Portanto ao tomarmos um subconjunto com n + 1 elementos teremos, necessariamente, dois elementos consecutivos que, sendo primos entre si, irão garantir nosso resultado.  

Exemplo 3. Mostrar que qualquer subconjunto S de {1, 2, 3,..., 12} contendo sete elementos possui dois subconjuntos cuja soma dos elementos é a mesma.

Solução: Um subconjunto com 7 elementos terá soma no máximo igual a 6 + 7 + 8 + 9 + 10 + 11 + 12 = 63. Disto concluímos que os possíveis valores para a soma dos elementos de um subconjunto de um conjunto contendo 7 dos elementos de {1, 2, 3,..., 12} vão de 1 a 63, ou seja, temos 63 valores possíveis. Mas um conjunto com 7 elementos possui 27 – 1 subconjuntos não-vazios. Logo, como 27 – 1 > 63, pelo menos dois deles terão a mesma soma para os seus elementos.  

Exemplo 4. Mostrar que, dentre 9 pontos quaisquer de um cubo de aresta 2, existem pelo menos dois pontos que se encontram a uma distância menor  do que ou igual a Ö3 um do outro.

Solução: Dividimos este cubo em oito cubos menores dividindo cada aresta ao meio. Cada um dos 8 cubos assim gerados, tendo aresta 1, terá diâmetro igual a Ö3. Como temos 9 pontos, pelo menos um dos 8 cubos conterá 2 pontos, o que conclui a demonstração.

Exemplo 5. Suponhamos que os números de 1 até 15 sejam distribuídos de modo aleatório em torno de um círculo. Mostrar que a soma dos elementos de pelo menos um conjunto de 5 elementos consecutivos, tem que ser maior do que ou igual a 40.

Solução: Observe que, se somarmos todos os possíveis conjuntos de 5 elementos consecutivos (são 15), cada um dos números de 1 a 15 terá sido somado 5 vezes e que, portanto, a soma total será 5.(1 + 2 + 3 + ... + 15) = 5.(15 + 1).15/2 = 600. Como são 15 conjuntos distintos de 5 elementos consecutivos, se cada um tiver soma inferior a 40, o total será no máximo 15 ´ 39 = 585. Logo, pelo menos um deve ter soma maior do que ou igual a 40.

O Princípio da Casa dos Pombos pode ser, de maneira mais geral, enunciado como: “Se n gaiolas são ocupadas por n.k + 1 pombos, então pelo menos uma gaiola deverá conter pelo menos k + 1 pombos”.

Exemplo 6. Numa festa de aniversário com 37 crianças, pelo menos 4 nasceram no mesmo mês.

Solução: De fato, como 37 = 3.12 + 1 o resultado segue pelo caso geral enunciado acima, com n = 12 e k = 3. Logo temos que pelo menos 3 + 1 = 4 crianças nasceram no mesmo mês.

Exemplo 7. Se uma urna contém 4 bolas vermelhas, 7 bolas verdes, 9 bolas azuis e 6 bolas amarelas, qual é o menor número de bolas que devemos retirar (sem olhar) para que possamos ter certeza de termos tirado pelo menos 3 de uma mesma cor?

Solução: Consideramos como gaiolas as 4 cores diferentes e, portanto, tomando k = 2 e n = 4, temos 4.2 + 1 = 9 para a resposta do nosso problema.

Exemplo 8. Num grupo de n pessoas (n ³ 2) existem pelo menos duas pessoas com o mesmo número de conhecidos. (OBS.: Neste exemplo assumimos que a relação de conhecimento é simétrica, isto é, se a conhece b, então b conhece a.)

Solução: Vamos particionar estas n pessoas em subconjuntos A0, A1,..., An – 1, onde Ai é o subconjunto que contém as pessoas que conhecem i pessoas no grupo de n. Logo, se uma pessoa não conhece nenhuma outra das n – 1 pessoas ela estará no grupo A0, se tem somente um conhecido estará em A1 e assim por diante, até An – 1, caso ela conheça todas as outras n – 1 pessoas. Mas se o subconjunto A0 possui alguém,  An – 1 não possui ninguém e vice-versa. Isto porque se alguém não conhece ninguém é porque ninguém conhece todos e se alguém conhece todos os outros não ninguém que seja desconhecido de todos. Logo, as n pessoas estão particionadas em n – 1 subconjuntos e, portanto, algum subconjunto contém pelo menos duas pessoas, o que conclui a demonstração.

Introdução à Teoria dos Números, José Plínio de Oliveira Santos, IMPA/SBM.

segunda-feira, 9 de julho de 2012


COMBINATÓRIA – Princípios básicos

O principio fundamental da contagem diz que se há x modos de tomar uma decisão D1 e, tomada a decisão D1, há y modos de tomar a decisão D2, então o número de modos de tomar sucessivamente as decisões D1 e D2 é xy.

Exemplo 1. Com 5 homens e 5 mulheres, de quantos modos se pode formar um casal?

Solução. Formar um casal equivale a tomar as decisões:
D1: Escolha do homem (5 modos).
D2: Escolha da mulher (5 modos).
Há 5 ´ 5 = 25 modos de formar um casal.

Exemplo 2. Uma bandeira é formada por 7 listras que devem ser coloridas usando apenas as cores verde, azul e cinza. Se cada listra deve ter apenas uma cor e não se pode usar cores iguais em listras adjacentes, de quantos modos se pode colorir a bandeira?

Solução. Colorir a bandeira equivale a escolher a cor de cada listra. Há 3 modos de escolher a cor da primeira listra e, a partir daí, 2 modos de escolher a cor de cada uma das outras 6 listras.
A resposta é 3 ´ 26 = 192.

Exemplo 3. Quantos são os números de três dígitos distintos?

Solução. O primeiro dígito pode ser escolhido de 9 modos, pois ele não pode ser igual a 0. O segundo dígito pode ser escolhido de 9 modos, pois não pode ser igual ao primeiro dígito. O terceiro dígito pode ser escolhido de 8 modos, pois não pode ser igual nem ao primeiro nem ao segundo dígitos.
A resposta é 9 ´ 9 ´ 8 = 648.

Você já deve ter percebido nesses exemplos qual é a estratégia para resolver problemas de Combinatória:

1) Postura. Devemos sempre nos colocar no papel da pessoa que deve fazer a ação solicitada pelo problema e ver que decisões devemos tomar. No exemplo 3, nós nos colocamos no papel da pessoa que deveria escrever o número de três dígitos; no exemplo 2, nós nos colocamos no papel da pessoa que deveria colorir a bandeira; no exemplo 1, nós nos colocamos no papel da pessoa que deveria formar o casal.

2) Divisão. Devemos, sempre que possível, dividir as decisões a serem tomadas em decisões mais simples. Formar um casal foi dividido em escolher o homem e escolher a mulher; colorir a bandeira foi dividido em colorir cada listra; formar um número de três dígitos foi dividido em escolher cada um dos três dígitos.

Vamos voltar ao exemplo anterior – Quantos são os números de três dígitos distintos? – para ver como algumas pessoas conseguem, por erros de estratégia, tornar complicadas as coisas mais simples.
Começando a escolha dos dígitos pelo último dígito, há 10 modos de escolher o último dígito. Em seguida, há 9 modos de escolher o dígito central, pois não podemos repetir o dígito já usado. Agora temos um impasse: de quantos modos podemos escolher o primeiro dígito? A resposta é “depende”. Se não tivermos usado o 0, haverá 7 modos de escolher o primeiro dígito, pois não poderemos usar nem o 0 nem os dois dígitos já usados nas demais casas; se já tivermos usado o 0, haverá 8 modos de escolher o primeiro dígito.
Um passo importante na estratégia para resolver problemas de Combinatória é:

3) Não adiar dificuldades. Pequenas dificuldades adiadas costumam se transformar em imensas dificuldades. Se uma das decisões a serem tomadas for mais restrita que as demais, essa é a decisão que deve ser tomada em primeiro lugar. No exemplo 3, a escolha do primeiro dígito era uma decisão mais restrita do que as outras, pois o primeiro dígito não pode ser igual a 0. Essa é portanto a decisão que deve ser tomada em primeiro lugar e, conforme acabamos de ver, postergá-la só serve para causar problemas.

A Matemática do Ensino Médio. Rio de Janeiro: SBM, 2001. Vol. 2 (p. 85-87).