Ensino Médio ⇒ Análise Combinatória: Princípio das Gavetas de Dirichlet

[paulo testoniMOD]

Um armário tem [tex3]4[/tex3] cadeados denominados [tex3]A,B,C[/tex3] e [tex3]D.[/tex3] Seis pessoas têm chaves desses cadeados de uma forma muito curiosa:

[tex3]\bullet[/tex3] Todos têm chaves de exatamente dois cadeados;
[tex3]\bullet[/tex3] Duas dessas pessoas nunca têm as mesmas duas chaves.

Qual o número mínimo de pessoas desse grupo necessário para que possamos ter certeza de que o cadeado A poderá ser aberto?

a) [tex3]6[/tex3]
b) [tex3]5[/tex3]
c) [tex3]4[/tex3]
d) [tex3]3[/tex3]
e) [tex3]2[/tex3]

[Eduardo]

Bom esse exercício pode ser pensado da seguinte maneira:

Cada pessoa possui um par de chaves [tex3](A\text{ e } B,[/tex3] [tex3]B\text{ e } C,[/tex3] [tex3]A\text{ e } C,[/tex3] etc.) e nós queremos encontrar uma maneira de distribuir os pares entre um número de pessoas de maneira que, sempre pelo menos uma possua a chave do cadeado [tex3]A.[/tex3] como fazer isso?

Achamos o número máximo de pessoas que podem existir sendo impossível abrir o cadeado [tex3]A[/tex3] e somamos [tex3]1.[/tex3]

As combinações de chaves diferentes usando as chaves [tex3]B, C \text{ e } D[/tex3] são 3 [tex3](B C, B D\text{ e } C D)[/tex3] então, após darmos essas [tex3]3[/tex3] chaves, a próxima pessoa com certeza terá uma chave que contém [tex3]A.[/tex3]

Resposta: [tex3]4,[/tex3] letra c.