UFPE, Final, 2018.2, 4.
a) Pretende-se distribuir os 250 alunos de uma escola por 7 equipes para uma feira de ciências. Qual o maior valor de k para o qual se pode afirmar que necessariamente pelo menos uma equipe terá pelo menos k alunos?
b) Enuncie o teorema de Euler para um grafo planar qualquer e sua versão para uma
árvore (justifique).
Passo 1
E aiii, galerinhaa!!
Em a, queremos distribuir os 250 alunos de uma escola por 7 equipes e encontrar o maior valor de k que garante que pelo menos uma equipe terá k alunos? Bom, pelo princípio da casa dos pombos, nós teremos que:
Se fizermos 35*7, temos o resultado de 245 e restariam 5 alunos, já que temos 250. Com esses 5 alunos restando, pelo menos uma equipe receberia ao menos 1 aluno. Ou seja, teria pelo menos 36 alunos.
Passo 2
Em b, teremos que:
, em que v(G) é o número de vértices, E(G) é o número de arestas, f são as faces e p+1 é o número de conexões.
Para uma árvore, teremos que p = 1, já que é conexa. Como não tem circuitos, f = 1, tendo apenas a face externa. Assim, em uma árvore, teríamos que
Resposta
a) 36 alunos.
b) e