Seja
um inteiro positivo ímpar. Em um campo aberto estão
crianças posicionadas de tal modo que para cada uma delas as distâncias às outras
crianças são todas distintas. Cada criança tem uma pistola d’água e, ao som de um apito, atira na criança mais próxima de si. Mostre que uma das crianças permanecerá enxuta.
Passo 1
O enunciado diz que temos
crianças num campo aberto, com
ímpar, de modo que para cada criança as distâncias às outras
são todas distintas. Ao sinal do apito, cada criança atira na sua vizinha mais próxima (distância única garante um único alvo). Queremos mostrar que existe pelo menos uma criança que não leva nenhum tiro, ou seja, que permanece enxuta. Modelamos a situação por um grafo direcionado
cujos vértices são as crianças, e colocamos uma seta de
para
sempre que
atira em
.
- Cada vértice tem grau de saída igual a
(pois cada criança atira em exatamente uma outra). - O grau de entrada de um vértice é o número de vezes que essa criança é atingida.
Passo 2
Se existir um vértice com grau de entrada zero, está provado que essa criança não leva tiro e ficamos felizes. Suponha, para chegar a contradição, que todos os vértices tenham grau de entrada pelo menos
. Como a soma dos graus de entrada em
é igual ao número total de setas, que é
, concluímos que cada grau de entrada vale exatamente
. Quando em um grafo direcionado cada vértice tem saída
e entrada
,
é a união disjunta de ciclos dirigidos. Não pode haver ciclos de tamanho
(laços) porque não existe criança cuja menor distância seja zero. Logo todo ciclo tem tamanho
. Como
é ímpar, a soma dos comprimentos dos ciclos (todos
) é ímpar, o que obriga a existência de pelo menos um ciclo de comprimento ímpar.
Passo 3
Suponha que exista um ciclo ímpar de vértices
com
ímpar e
. Pelo modo de construção, cada
atira em
porque
para todo outro vértice
. Em particular, tomando o predecessor
naquele ciclo, temos
Somando essa desigualdade para
, com índices entendidos módulo
, dá
Mas como
, o somatório à esquerda é exatamente igual ao da direita (só troca a ordem), o que é impossível numa desigualdade estrita. Contradição.
Passo 4
Chegamos à contradição ao supor que não existia vértice de grau de entrada zero. Logo deve haver pelo menos uma criança que não leva tiro.
Resposta
Existe pelo menos uma criança que permanece enxuta.