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.
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.
– (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
“pombos” para colocar em
“casas” e
, então em pelo menos uma casa cabem dois ou mais pombos. Em outras palavras, não é possível distribuir
itens em
recipientes sem que algum recipiente receba pelo menos
itens. No caso
, 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
ou seja, há
possibilidades. Cada número inteiro dos
dados é um “pombo” e cada valor de dígito (de
a
) é uma “casa”. Como
, 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
itens em
recipientes com
, pelo menos um recipiente conterá dois ou mais itens.
(b) Como o último dígito de um inteiro tem apenas
possibilidades
, ao escolhermos
inteiros
, dois deles devem necessariamente cair na mesma “casa” (mesmo último dígito).