Flashcard FC317415
Como aplicar o princípio da casa dos pombos para garantir que, num grafo completo com 17 vértices e 3 cores nas arestas, existe um vértice com pelo menos 6 arestas da mesma cor?
Princípio da Casa dos Pombos
Com. Org. (IFSP) · 2018
Como aplicar o princípio da casa dos pombos para garantir que, num grafo completo com 17 vértices e 3 cores nas arestas, existe um vértice com pelo menos 6 arestas da mesma cor?
Mostrar resposta e comentário
Resposta
Pela casa dos pombos, um vértice ligado a 16 outros tem \( \lceil16/3\rceil=6\) arestas da mesma cor.Considere um vértice \(v\). Ele tem 16 arestas para os demais vértices. Dividindo essas 16 arestas em 3 cores, o princípio da casa dos pombos garante uma cor com ao menos \( \lceil16/3\rceil=6\) arestas incidentes em \(v\). Seja \(S\) o conjunto dos 6 vértices ligados a \(v\) por essa cor. Se entre dois vértices de \(S\) houver uma aresta desta mesma cor, então esses dois mais \(v\) formam um triângulo monocromático. Se não houver tal aresta, então todas as arestas internas a \(S\) usam apenas as outras duas cores; mas sabe-se que com 6 vértices e 2 cores sempre existe um triângulo monocromático (fato de Ramsey \(R(3,3)=6\)). Portanto, em 17 vértices existe sempre um triângulo monocromático.
Exemplo:
17 cidades conectadas por estradas rotuladas A, B ou C. Escolha uma cidade \(X\); ela tem 16 estradas para as demais. Pelo princípio da casa dos pombos, ao menos \( \lceil16/3\rceil=6\) dessas estradas são do tipo A. Se entre essas 6 cidades houver uma estrada A, então \(X\) e esse par formam um triângulo A. Se não, as estradas entre essas 6 usam apenas B e C, e entre 6 cidades com 2 tipos de estrada existe sempre um triângulo monocromático; logo, há um triângulo todo B ou todo C.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/317116
Conteúdo do catálogo FC Concursos · Atualizado em