Análise Combinatória e Princípio de Dirichlet

Prévia do material em texto

Análise Combinatória, Probabilidades e Aplicações
Curso de Verão 2024 - IME/USP
Análise Combinatória:
Tópicos adicionais de combinatória
Binômio de Newton
Se x e y são números reais e n é um número natural, vale que
(x+ y)n =
n∑
k=0
(
n
k
)
xkyn−k
Demonstração por argumento combinatório: Vale que
(x+ y)n = (x+ y)(x+ y)...(x+ y)
Cada termo do produto é obtido escolhendo, em cada parênteses, um x ou um y e multiplicando
os escolhidos. Para cada valor de k, 0 ≤ k ≤ n, há
(
n
k
)
modos de escolhemos x em k dos parênteses e
por consequência, y em n− k dos parênteses; nesse caso, o produto será xkyn−k.
Polinômio de Leibniz
Generalização do Binômio de Newton. Se (xi)i∈{1,...,p} são números reais e n é um número natural,
vale que
(x1 + x2 + ...+ xp)
n =
∑
(a1,...,ap)∈A
n!
a1!a2!...ap!
xa1
1 xa2
2 ...xap
p ,
em que A = {(a1, ..., ap) ∈ {0, 1, ...}p|
∑p
i=1 ai = n}
Demonstração por argumento combinatório: Vale que
(x1 + x2 + ...+ xp)
n = (x1 + x2 + ...+ xp).(x1 + x2 + ...+ xp)...(x1 + x2 + ...+ xp)
Cada termo do produto é obtido escolhendo, em cada parênteses, ou x1 ou x2 ou ... ou xp e
multiplicando os escolhidos. Para cada valor de (a1, ..., ap) ∈ A, há n!
a1!...ap!
modos de escolhemos xi
em ai dos parênteses, i ∈ {1, ..., p}; nesse caso, o produto será xa1
1 xa2
2 ...x
ap
p .
O Prinćıpio de Dirichlet
Se n objetos forem colocados em no máximo n−1 gavetas, pelo menos uma gaveta conterá pelo menos
2 objetos.
Exemplo 1: Em um grupo de pelo menos 13 pessoas, há no mı́nimo duas pessoas que fazem
aniversário no mesmo mês.
Exemplo 2: 4000 pessoas foram fazer uma prova com 5 questões de múltipla escolha com 5
alternativas cada. Mostre que pelo menos duas pessoas responderam a prova de modo idêntico.
Resposta:
Existem 55 = 3125 modos de responder a prova. Como 4000 pessoas foram fazer a prova, pelo
menos duas delas responderam a prova de maneira idêntica.
1
Exemplo 3: Escolhem-se 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 ou igual a 2
Resposta:
Podemos interpretar as gavetas como sendo 4 quadrados menores de lado 1, dentro do quadrado de
lado 2. Como há 5 pontos e 4 quadrados, pelo menos 1 quadrado terá mais de 1 ponto. Dois pontos
em um mesmo quadrado tem distância de, no máximo,
√
2 (o tamanho da diagonal do quadrado de
lado 1).
Exemplo 4: Considere uma reunião com n pessoas. Supondo que se A conhece B, então B conhece
A, mostre que existem duas pessoas que conhecem a mesma quantidade de pessoas na reunião.
Resposta:
Note que há dois casos: existe uma pessoa que não conhece qualquer outra, ou não existe pessoa
que não conheça qualquer outra.
• Primeiro caso: existe alguém que conhece 0 pessoas:
Note que o número de pessoas que qualquer um pode conhecer é 0 ou 1 ou ... ou n-2. Não é
posśıvel alguém conhecer n − 1 pessoas, pois isso implicaria que esse alguém deveria conhecer
também o indiv́ıduo que conhece 0 pessoas (imposśıvel).
Coloque em uma ”gaveta” os indiv́ıduos que conhecem 0 pessoas, em outra os indiv́ıduos que
conhecem 1 pessoa, etc. Haverá um total de n − 1 gavetas e n pessoas, portanto o resultado
segue pelo Prinćıpio de Dirichlet.
• Primeiro caso: não existe alguém que conhece 0 pessoas:
Note que o número de pessoas que qualquer um pode conhecer nesse caso é 1 ou 2 ou... ou n-1.
Fazemos n−1 gavetas de maneira análoga ao caso anterior, tendo um total de n pessoas, portanto
o resultado segue pelo Prinćıpio de Dirichlet.
Exemplo 5: Há 5 equipes em um torneio no qual duas equipes se enfrentam a cada jogo. Qual
a quantidade mı́nima de jogos que devem ter ocorrido para que tenhamos certeza de que existam 2
equipes que se enfrentaram pelo menos duas vezes?
Resposta: Há
(
5
2
)
= 10 jogos diferentes, já que esses são os modos de escolher 2 das equipes para
se enfrentarem. Pelo Prinćıpio de Dirichlet, com 11 jogos, existem duas equipes que se enfrentaram
pelo menos duas vezes. A mesma conclusão não vale para menos de 11 jogos, já que é posśıvel ter(
5
2
)
= 10 jogos diferentes. Portanto, a resposta é 11.
2