DESAFIO: paridade e apertos de mão

Um desafio interessante para alegrar o seu dia:

Considere que todas as pessoas vivas já trocaram apertos de mão com outras pessoas. Prove que o número de pessoas que trocaram apertos de mão uma quantidade ímpar de vezes é, necessariamente, um número par.

Recomendo imensamente que o leitor tente resolver o desafio sem ler a resposta. Mas, de qualquer maneira, deixo a solução logo abaixo.

SOLUÇÃO:

Vamos propor uma contagem não do número de apertos de mão, mas, sim, do número de perspectivas de apertos de mão. A ideia é mais simples do que parece. Se a pessoa A dá a mão para a pessoa B, vamos contar que houve dois apertos de mão: o da pessoa A para a pessoa B e o da pessoa B para a pessoa A. Assim, nossa contagem resultará sempre em um número par, afinal apertos de mão envolvem exatamente duas pessoas.

Seria possível que um número ímpar de pessoas trocassem apertos de mão uma quantidade ímpar de vezes? Vamos supor, por absurdo, que isso fosse possível. Nessa hipótese, teríamos uma quantidade ímpar de perspectivas de apertos de mão, já que a soma de uma quantidade ímpar de parcelas ímpares resulta em um número ímpar (o qual chamaremos de "i").

Por outro lado, considerando a contagem das perspectivas de apertos de mão das pessoas que trocaram apertos de mão uma quantidade par de vezes, teremos, com toda certeza, um número par (o qual chamaremos de "p"), já que a soma de números pares resulta em um número par, qualquer que seja a quantidade de parcelas.

Ora, mas a soma de um ímpar (i) com um par (p) é sempre ímpar. E isso é um absurdo, já que havíamos deduzido que a contagem proposta sempre resultava em um número par.

Caso o leitor queira mais detalhes...

A forma de contagem indicada acima pode ser visualizada em um grafo.

Imagine que os vértices do grafo sejam as pessoas e que as linhas que ligam um vértice a outro sejam os apertos de mão. Se o vértice A estiver ligado ao vértice B, significa que houve aperto de mão entre a pessoa A e a pessoa B; caso contrário, não houve aperto de mão entre A e B. Obviamente, um vértice não pode estar ligado a ele mesmo (uma pessoa não dá a mão a si mesma).

Neste exemplo, A aperta a mão de B e C; B aperta a mão de A e D; C aperta a de A; D aperta a de B; E não aperta a mão de ninguém. Há três pessoas dando uma quantidade par de de apertos de mão: A, B e E (lembre que 0 é par!) e duas dando uma quantidade ímpar de apertos de mão: D e C.

Nessa analogia geométrica, as perspectivas de apertos de mão são as ligações de uma linha com um vértice. Como uma mesma linha sempre liga exatamente dois vértices, essa contagem leva, com certeza, a um número par.

Quando há uma quantidade par de linhas saindo de um vértice, essa quantidade não afeta a paridade da contagem geral. Contudo, quando há uma quantidade ímpar de linhas saindo de um vértice, a paridade da contagem geral somente não vai ser ser afetada se houver outro vértice do qual saia uma quantidade ímpar de linhas. Logo, as pessoas que deram as mãos uma quantidade ímpar de vezes sempre existem aos pares.

Fonte:

Esse desafio foi extraído do livro "The USSR Olympiad Problem: Selected Problems and Theorems of Elementary Mathematics", de D. O. Shklarsky, N. N. Chentzov e I. M. Yaglom.