Princípio das Casas de Pombo e Análise Combinatória

Prévia do material em texto

UNIVERSIDADE FEDERAL DE MINAS GERAIS
ICEx-Departamento de Matemática
Sétima lista de Análise Combinatória - Prinćıpio das casas de pombo
Professora: Aniura Milanés
Data de publicação: 07/10/2020 Data de entrega: 16/10/2020
Exerćıcio 1.
(a) Prove que se n + 1 inteiros são escolhidos do conjunto {1, 2, 3, . . . , 2n}, então sempre haverá pelo
menos dois deles cuja diferença é igual a 1.
(b) Prove que se n + 1 inteiros são escolhidos do conjunto {1, 2, 3, . . . , 3n}, então sempre haverá pelo
menos dois deles cuja diferença é menor o igual a 2.
(c) Formule uma afirmação que generalize as duas afirmações anteriores. Não precisa prová-la.
Solução 1.
(a) {1, 2, 3, . . . , 2n} pode ser particionado como união dos conjuntos {1, 2}, {3, 4}, {5, 6}, ..., {2n−1, 2n}.
Estes são n conjuntos (casas) Se escolhermos n+ 1 inteiros em {1, 2, 3, . . . , 2n} (pombos) pelo menos
dois deles devem estar no mesmo conjunto e a diferença entre eles será 1.
(b) De maneira similar, podemos particionar o conjunto {1, 2, 3, . . . , 3n} como união dos conjuntos {1, 2, 3},
{4, 5, 6}, {7, 8, 9}, ..., {3n−2, 3n−1, 3n}. Estes são n conjuntos (casas). Se escolhermos n+1 inteiros
em {1, 2, 3, . . . , 3n} (pombos) pelo menos dois deles devem estar no mesmo conjunto e a diferença
entre eles será no máximo 2.
(c) Se n + 1 inteiros são escolhidos do conjunto {1, 2, 3, . . . , kn}, então sempre haverá pelo menos dois
deles cuja diferença é menor o igual a k − 1.
Exerćıcio 2.
Numa compra feita para o lanche de uma creche, foram adquiridas 100 bananas, 100 laranjas, 100 maçãs
e 100 pêras. Uma pessoa está guardando as frutas na geladeira. Ela guarda uma fruta escolhida ao acaso
a cada dois segundos.
(a) Após quantos segundos podemos garantir que essa pessoa guardou uma fruta de cada tipo?
(b) Após quantos segundos podemos garantir que essa pessoa guardou uma dúzia de frutas de cada tipo?
Solução 2.
(a) Ela teria que ter guardado 301 frutas e faria isso em 602 segundos, ou seja, uma hora, 4 minutos e 2
segundos.
(b) Ela teria que ter guardado 312 frutas e faria isso em uma hora, 4 minutos e 2 segundos.
Exerćıcio 3.
Prove que para quaisquer 4 números inteiros a1, a2, a3 e a4 existem pelo menos dois ai e aj , com i 6= j
cuja diferença ai − aj é diviśıvel por 3.
1
Solução 3.
Chamemos de A0 = {a ∈ {a1, a2, a3, a4}|a ≡ 0 mod 3}, A1 = {a ∈ {a1, a2, a3, a4}|a ≡ 1 mod 3}, A2 =
{a ∈ {a1, a2, a3, a4}|a ≡ 2 mod 3}. Estas são as “casas”. Os pombos são os elementos a1, a2, a3 e a4.
Como eles são quatro, podemos garantir que pelo menos dois deles estão no mesmo conjunto. Nesse caso
a diferença desses elementos será congruente com 0 módulo 3, e portanto será múltiplo de 3.
Exerćıcio 4.
Prove que, entre 5 pontos de um triângulo equilátero de lado 1 cm, sempre haverá pelo menos dois deles
que distem entre si não mais de
1
2
cm.
Solução 4.
Podemos dividir o triângulo em quatro triângulos equiláteros de lado 1/2 cm como mostra a figura a
seguir.
Se distribuirmos os 5 pontos, haverá pelo menos dois deles em alguma dessa quatro regiões. A máxima
distância entre dois pontos numa dessas regiões é 1/2 cm.
2