Em uma festa, os convidados se cumprimentaram com apertos de mão. Mostre que a quantidade de pessoas que apertaram mãos um número ímpar de vezes é par.
Passo 1
O enunciado pede para mostrar que, em uma festa em que os convidados se cumprimentam com apertos de mão, a quantidade de pessoas que deram um número ímpar de apertos de mão é par. Para isso, vamos usar a teoria de grafos e o Lema das Mãos Dadas, que relaciona o grau dos vértices ao número de arestas.
Passo 2
Modelamos cada pessoa por um vértice
de um grafo simples e cada aperto de mão por uma aresta. O número de apertos de mão feitos pela pessoa
corresponde ao seu grau
.
Passo 3
Pelo Lema das Mãos Dadas, a soma dos graus de todos os vértices é o dobro do número de arestas:
Como
é um número par, segue que
é par.
Passo 4
Seja
a quantidade de vértices com grau ímpar. Podemos escrever
A soma dos graus pares é um número par e a soma de
inteiros ímpares tem a mesma paridade de
. Como o total da soma é par, a parte correspondente aos graus ímpares também deve ser par, o que só ocorre se
for par.
Resposta
A quantidade de pessoas que apertaram mãos um número ímpar de vezes é par.