MATEMÁTICA É ASSIM, TAMBÉM !: O PRINCÍPIO DA CASA DO POMBOS

domingo, 8 de janeiro de 2012

O PRINCÍPIO DA CASA DO POMBOS - 02

Princípio da Casa dos Pombos

Segundo João Pitombeira, a Análise Combinatória 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, esta área da Matemática trata-se de diversas questões interessantes cujos enunciados são 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.

O princípio da casa dos pombos também conhecido por princípio de Dirichlet é um princípio básico da Combinatória que possui diversas aplicações. No primeiro post apresentei alguns exemplos e exercícios, vejamos mais alguns exemplos citados no artigo do João Pitombeira.

[;1);]

Escolha, dentre os inteiros $[;1,2,\ldots, 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.

Resolução: Em primeiro lugar, observer que qualquer inteiro [;n;]

se escreve sob a forma [;n = 2^kb;]

, onde

é um número inteiro não negativo, e [;b;]

é um inteiro ímpar. Por exemplo, $[;36 = 2^2\cdot 9;]$ , $[;25 = 2^0\cdot 25;]$ , $[;16 = 2^4\cdot 1;]$ . Assim, se $[;n \in \{1,2,\ldots 200\};]$ , [;n=2^kb;]

, e

é um dos números ímpares $[;1,3,5,\ldots,199;]$ . Ora, há [;100;]

números ímpares no conjunto $[;{1,2,\ldots,200\};]$ . Logo, quando escolhemos [;101;]

números deste conjunto, dois deles terão suas partes ímpares iguais, dois deles terão suas partes ímpares iguais, pelo princípio da casa dos pombos; sejam [;n_1;]

estes números. Então $[;n_1 = 2^{k_1}b;]$ e $[;n_2 = 2^{k_2}b;]$ . Se $[;k_1 \prec k_2;]$ , então [;n_2;]

divide

, pois $[;n_2/n_1 = (2^{k_2b})/(2^{k_1b}) = 2^{k_2 - k_1};]$ . Analogamente, se $[;k_2 \prec k_1;]$ então [;n_1;]

dividirá

, o que conclui a demonstração.

[;2);]

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

conhece

, ou seja, "conhecer" é uma relação simétrica).Resoluçã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. Deste modo, dividiremos a demonstração em dois casos.

$[;1^{\circ};]$ 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. De fato, temos [;n;]

pessoas no conjunto e etiquetemos as gavetas como segue:

A $[;1^{\underline{a}};]$ , para as pessoas que conhecem exatamente uma pessoa do conjunto $[;\{a_1,a_2,\ldots,a_n\};]$ , a $[;2^{\underline{a}};]$ , para as pessoas que conhecem exatamente duas pessoas do conjunto $[;\{a_1,a_2,\ldots,a_n\};]$ e a [;(n-1);]

-ésima, para as pessoas que conhecem exatamente [;(n-1);]

pessoas do conjunto $[;\{a_1,a_2,\ldots,a_n\};]$ . Temos então [;n;]

pessoas a serem distribuídas por [;(n-1);]

gavetas, e o problema está de fato resolvido, pois, pelo princípio da casa dos pombos, duas pessoas ocuparão a mesma gaveta.
$[;2^{\circ};]$ caso: Suponha agora que uma das pessoas, que chamaremos de [;a_1;]

, conhece

pessoas, ou seja, não conhece ninguém do conjunto. Retire a pessoa [;a_1;]

do conjunto. Mostraremos que, no conjunto resultante, $[;\{a_2,a_3,\ldots a_n\};]$ , há duas pessoas que conhecem exatamente o mesmo número de pessoas de $[;\{a_1,a_2,\ldots,a_n\};]$ . De fato, suponha que isso não aconteça, e etiquetemos as gavetas como segue:

A $[;1^{\underline{a}};]$ , para as pessoas de $[;\{a_2,a_3,\ldots a_n\};]$ que conhecem [;1;]

pessoa de $[;\{a_1,a_2,\ldots,a_n\};]$ , a $[;2^{\underline{a}};]$ para as pessoas de $[;\{a_2,a_3,\ldots a_n\};]$ que conhecem [;2;]

pessoas de $[;\{a_1,a_2,\ldots,a_n\};]$ e assim por diante, de modo que a [;(n-1);]

-ésima para as pessoas $[;\{a_2,a_3,\ldots a_n\};]$ que conhecem [;n-1;]

pessoas de $[;\{a_1,a_2,\ldots,a_n\};]$ . Temos então [;(n-1);]

gavetas e se uma das gavetas contiver mais do que uma pessoa, o problema está resolvido. Suponha, portanto, que cada gaveta tém, no máximo, uma pessoa. Então como temos [;(n-1);]