João Bosco Pitombeira
PUC – Rio de Janeiro - SP

A “Análise Combinatória”, que poderia ser chamada de “arte de contar”, inspira em geral temor ou desagrado aos alunos do segundo grau, às voltas, mecanicamente, com combinações, permutações, arranjos, etc.

No entanto, sob o nome mais geral e abrangente de Combinatória, trata-se de uma parte fascinante da Matemática; existem nela problemas de enunciado extremamente simples, mas que exigem, por vezes, para sua solução, raciocínios penetrantes e engenhosos, embora no nível de um aluno do segundo grau.

Grandes matemáticos, como Euler, atacaram problemas de Combinatória. Hoje, com o rápido desenvolvimento da chamada Matemática Finita, principalmente devido ao aparecimento dos computadores eletrônicos, a Combina­tória cresce rapidamente, atraindo a atenção de muitos matemáticos jovens e promissores.

Um dos princípios básicos da Combinatória é o chamado “princípio da casa dos pombos”, ou ainda “principio das gavetas de Dirichlet”, que diz simplesmente:

Se forem dados n objetos, a serem colocados em, no máximo, (n - 1) gavetas, então uma delas conterá necessariamente mais do que um objeto.

Ou, equivalentemente, se forem dados n objetos, a serem colocados em, no máximo, 
(n - 1) gavetas, então uma delas conterá pelo menos dois objetos.

Certamente todos aceitam este principio como verdadeiro. Para os mais céticos, que insistirem em uma demonstração formal, faremos uma por redução ao absurdo. Se cada uma das gavetas contiver, no máximo, um objeto, o numero total de objetos colocados nelas será, no máximo, (n - 1), o que é uma contradição.

Uma aplicação trivial deste princípio é:

Dado um conjunto de 13 pessoas, pelo menos duas delas terão aniversários no mesmo mês.

No entanto, o principio da casa dos pombos se presta a aplicações mais interessantes e significativas do que esta; de outra maneira, não valeria a pena apresentá-lo.

Escolha, dentre os inteiros 1, 2,...,200, 101 números ao acaso. Mostre que, entre os números escolhidos, há dois números tais que um deles é divisível pelo outro.

Demonstração: Em primeiro lugar, observe que qualquer inteiro n se escreve sob a forma n = 2^kb, onde k é um inteiro não negativo, e b é um inteiro ímpar. Por exemplo,         
36 = 2².9, 25 = 2⁰.25, 16 = 2⁴.1.

Assim, se n  {1, 2,..., 200}, n = 2^kb, e b é um dos números ímpares 1, 3, 5,..., 199. Ora, há 100 números ímpares no conjunto {1, 2,..., 200}. Logo, quando escolhemos 101 números deste conjunto, dois deles terão suas partes ímpares iguais, pelo princípio da casa dos pombos; sejam n₁ e n₂ estes números. Então, n₁ = 2^k1b e n₂ = 2^k2b. Se k₁ < k₂, então n₂ divide n₁ pois n₂ / n₁ = (2^k2b)/ (2^k1b) = 2^k2. Se k₁ < k₁ então n₁ dividirá n₂, o que conclui a demonstração.

Exercícios:

-    Demonstre que em qualquer conjunto com 367 pessoas há, pelo menos, duas que terão aniversários no mesmo dia do ano.

-    Mostre que se do conjunto {1, 2,..., 2n} retirarmos (n + 1) números ao acaso, então um deles dividirá um outro.

Mostre que em um conjunto de n pessoas há duas pessoas que conhecem exatamente o mesmo número de pessoas do conjunto (obs.: se a conhece b, b conhece a, ou seja, “conhecer” é uma relação simétrica).

Demonstração: Observe, em primeiro lugar, que qualquer das pessoas do conjunto conhece no mínimo 0 e no máximo (n-1) das outras pessoas.

Dividiremos a demonstração em dois casos.

1.º caso: Mostraremos, em primeiro lugar, que se todas as pessoas conhecem pelo menos uma outra pessoa do conjunto, então o problema está resolvido pelo princípio da casa dos pombos.

Com efeito, temos n pessoas no conjunto e etiquetemos as gavetas como segue:

- A 1ª , para pessoas que conhecem exatamente uma pessoa do conjunto

{a₁,a₂,...,a_n}

- A 2ª, para as pessoas que conhecem exatamente duas pessoas do conjunto

{a₁,a₂,...,a_n}

..........................................................................................

- a (n - 1) -ésima, para as pessoas que conhecem exatamente (n - 1) pessoas do conjunto

Temos então n pessoas a serem distribuídas por (n - 1) gavetas, e o proble­ma está de fato resolvido, pois, pelo princípio da casa dos pombos, duas das pessoas ocuparão a mesma gaveta.

2º caso. Suponha agora que uma das pessoas, que chamaremos de a1, conhece 0 pessoas (ou seja, não conhece ninguém do conjunto).

Retire a pessoa a₁ do conjunto. Mostraremos que, no conjunto resultante, {a₂, a₃ ..., a_n}, há duas pessoas que conhecem exatamente o mesmo número de pessoas de {a₁, a₂,... a_n}.

Com efeito, suponha que isso não aconteça, e etiquetemos as gavetas como segue.

— A 1ª, para as pessoas de {a₂, a₃,... a_n} que conhecem 1 pessoa de {a₁, a₂, a₃,..., a_n }

— a 2ª, para as pessoas de {a₂, a₃,... a_n}  que conhecem 2 pessoas de {a₂, a₂,... a_n}

..........................................................................................

— a (n — 1) -ésima para as pessoas de {a₂, a₃,... a_n} que conhecem n - 1 pessoas de {a₁, a₂,... a_n}

Temos então (n — 1) gavetas. Se uma das gavetas contiver mais do que uma pessoa, o problema está resolvido. Suponha, portanto, que cada gaveta contém, no máximo, uma pessoa. Então como temos (n - 1) pessoas, a₂, a₃, ,... a_n cada gaveta conterá exatamente uma pessoa, ou seja, há uma pessoa que conhece (n - 1) pessoas de {a₁, a₂,... a_n}, o que é uma contradição, pois ela não pode conhecer a₁ (lembre-se de que a₁ não conhece ninguém!).

Sejam dados um inteiro m e o conjunto A = {a₁, a₂,..., a_n} de números inteiros;existem então

Demonstração: Com efeito, considere as m somas

Se algumas destas somas (por exemplo, Sj) for divisível por m, a demonstração está concluída (neste caso, k = 1 e  = j).

Suponha então que m não é divisor de nenhuma das somas, ou seja, todas elas, ao serem divididas por m, deixam resto não nulo. Os restos possíveis são, portanto, 1, 2,..., m - 1. Como há m somas, duas delas, que chamaremos de S_i e S_j deixam o mesmo resto. Suponha i > j. Então S_i – S_j (a₁ + a₂ + ... +a_j)  - (a₁ +a₂+...+a_j) = a_j + 1 + a_j + 2 +... +a_i deixa resto 0 na divisão por m, ou seja, m é divisor de S_i – S_j.  O resultado está demonstrado, com k = j + 1 e
= i.

O princípio da casa dos pombos pode ser reformulado como segue:

Se m pombos ocupam n casas, então pelo menos uma casa contém [(m - 1)/n] + 1 pombos. (obs.: [x] é o maior inteiro menor do que ou igual a x.)

Demonstração: Se cada casa contiver, no máximo, [(m - 1)/n] pombos, então o número máximo de pombos será n[(m - 1)/n] m - 1 < m, uma contradição, já que temos m pombos.

Ainda outra formulação possível para o princípio da casa dos pombos é a seguinte:

Sejam n gavetas e r um inteiro positivo dado. Coloquemos a₁ objetos na primeira gaveta, a₂ objetos na segunda, e assim sucessivamente, até a_n objetos na n-ésima gaveta. Então, se a média (a₁ + a₂ + ... +a_n )/n for maior do que r – 1, uma das n gavetas conterá pelo menos r objetos.

Demonstração: A demonstração deste fato é bem simples. Se todos os a_i forem menores do que r, então

Observação: Este teorema pode ser apresentado sem nenhuma referência a objetos e gavetas, mas tão somente como uma propriedade simples da media: se a média dos números naturais a₁, a₂,...,a_n, for maior do quer r - 1 então um dos a_i deverá ser maior do que ou igual   a r.

O princípio da casa dos pombos pode ser deduzido deste último teorema. Com efeito, se tivermos n objetos para distribuir entre (n - 1) gavetas, então a média n /(n - 1) certamente será maior do que 1. Logo, fazendo r = 2, teremos que uma das gavetas deve conter pelo menos 2 objetos.

O teorema que acabamos de apresentar pode ser usado para demonstrar o seguinte resultado, que parece pouco provável.

São dados dois discos, A e B, cada um deles dividido em 200 setores iguais. Os setores dos discos são pintados de branco ou de preto. Sabe-se que no disco A há 100 setores brancos e 100 pretos, em ordem desconhecida. O número de setores brancos de B é arbitrário e desconhecido por nós.

Coloquemos o disco A sobre o disco B de modo que cada setor de A fique exatamente sobre um setor de B (obs: sempre que dissermos que o disco A foi colocado sobre o disco B, fica convencionado que há esta coincidência de setores).

É então possível escolher a posição de A de maneira que existam pelo menos 100 setores de A que tenham a mesma cor que os correspondentes setores de B.

Demonstração: Coloque A sobre B. Seja a₁ o número de setores sobrepostos com cores coincidentes.

Mantendo B fixo, gire A de um setor (ou seja, de um ângulo ) no sentido dos ponteiros do relógio. Seja então a₂ o número de setores sobrepostos coincidentes.

Continue com este processo, girando A sempre de no sentido dos ponteiros dos relógios e obtendo a₃, a₄,...,  a₂₀₀.

É então verdade que o número total de coincidências é a₁ + a₂ +... + a₂₀₀ = (200 x 100) =  2 x x (l00)².

Com efeito, fixado um setor do disco B, (preto por exemplo), como o disco A tem exatamente 100 setores pretos, haverá 100 posições em que este setor de B terá a mesma cor que o setor correspondente de A. Assim, o número total de coincidências será o número de setores de B (200) vezes 100 (o número de setores vezes o número de coincidências por setor).

Então, pelo teorema, temos

(a₁ + a₂ +... + a₂₀₀ )/ 200 = 100 > 100 - 1 (neste caso r = 100)

Logo, pelo menos um dos a₁ deve ser igual a ou maior do que 100, ou seja, para uma das posições o número de coincidências é de pelo menos 100.

Esperamos que os exemplos apresentados tenham dado uma idéia de como aplicar o princípio da casa dos pombos. Como Matemática só se aprende fazendo, propomos a seguir alguns exercícios sobre o assunto. As soluções mais originais destes exercícios, ou outras soluções dos exemplos que apresentamos, poderão ser publicadas e comentadas nesta Revista. Principalmente, tente generalizar os enunciados e demonstrar suas generalizações.

-  Escolha 5 pontos ao acaso sobre a superfície de um quadrado de lado 2. Mostre que pelo menos um dos segmentos que eles determinam tem comprimento menor do que ou igual a .

-   Mostre que, se do conjunto {1,2,..., 2n} retirarmos (n + 1) números ao acaso, então dois dos números serão relativamente primos (ou seja, primos entre si).

-   Em uma gaveta, há 12 meias brancas e 12 meias pretas. Quantas meias de­vemos retirar ao acaso para termos certeza de obtermos um par de meias da mesma cor?

-   Chame um ponto B(x, y, z) de R³ de bom se todas as suas coordenadas forem inteiras (isto é, x, y, z E Z). Considere nove pontos bons de R³. Mostre que o ponto médio de algum dos segmentos que ligam estes pontos é bom.

-   Seja x um número real e n um inteiro positivo. Mostre que entre os números x, 2x, 3x,..., 
(n – 1)x existe um cuja distância a algum inteiro é, no máximo, 1/n.

Referência

Encontram-se capítulos ou seções dedicadas ao princípio da casa dos pombos em grande número de livros sobre Combinatória, dos quais citamos os seguintes:

[1] Cohen, D. I. A. – Basic Techniques of Combinatorial Theory, John Wiley & Sons, 1978.

[2] Brualdy, R. A. – Introductory Combinatories, North Holland, 1977.

Encontram-se, além disso, muitos problemas sobre o princípio da casa dos pombos em periódicos que publicam seções de problemas, como o American Mathematical Monthly, e o Crux Mathematicorum.