a) Descreva o princípio da casa dos pombos.
b) Explique como o princípio da casa dos pombos pode ser usado para mostrar que entre 11 números inteiros quaisquer, pelo menos dois devem ter o último dígito igual.

Passo 1

O enunciado pede duas coisas:
– (a) descrever o princípio da casa dos pombos (princípio do “Dirichlet”).
– (b) usar esse princípio para mostrar que, dados 11 números inteiros quaisquer, sempre existem dois com o mesmo último dígito.
O conteúdo envolvido é combinatória básica e o raciocínio de particionar elementos em “caixas” para forçar repetições.

Passo 2

O princípio da casa dos pombos diz que, se temos n “pombos” para colocar em m “casas” e n>m, então em pelo menos uma casa cabem dois ou mais pombos. Em outras palavras, não é possível distribuir n itens em m recipientes sem que algum recipiente receba pelo menos \bigl\lceil n/m\bigr\rceil itens. No caso n>m, isso garante obrigatoriamente pelo menos dois itens no mesmo recipiente.

Passo 3

Para aplicar ao problema dos 11 inteiros, observe que o último dígito de um inteiro pode ser apenas um dos elementos do conjunto
\{0,1,2,\dots,9\},
ou seja, há 10 possibilidades. Cada número inteiro dos 11 dados é um “pombo” e cada valor de dígito (de 0 a 9) é uma “casa”. Como 11>10, o princípio da casa dos pombos garante que em algum valor de dígito haverá pelo menos dois inteiros cujo último dígito coincide.

Resposta

(a) O princípio da casa dos pombos afirma que, ao distribuir n itens em m recipientes com n>m, pelo menos um recipiente conterá dois ou mais itens.
(b) Como o último dígito de um inteiro tem apenas 10 possibilidades \{0,1,\dots,9\}, ao escolhermos 11 inteiros 11>10, dois deles devem necessariamente cair na mesma “casa” (mesmo último dígito).

Exercícios de Livros Relacionados