*36. Suponha que para cada par de cidades em um país, há uma estrada direta conectando-as em uma direção ou na outra. Use a indução matemática para mostrar que há uma cidade que pode ser alcançada a partir de qualquer outra cidade ou diretamente ou através de outra cidade.
Passo 1
Resumindo o enunciado: temos um país com
cidades e, para cada par de cidades, há uma estrada direta ligando-as em uma direção ou na outra. Em termos de grafos, isso é um tournament em
vértices. Precisamos mostrar que existe uma cidade
tal que, para qualquer outra cidade
, existe um caminho dirigido de comprimento no máximo 2 que vai de
até
(isto é, alcança-se
direta ou passando por uma cidade intermediária). Para conseguir isso vamos usar indução matemática para provar antes um lema sobre indegrados em tournaments.
Passo 2
Lema: em qualquer tournament com
vértices existe um vértice cujo indegrado é pelo menos
.
Prova por indução em :
Prova por indução em
- Caso base
: trivial, o único vértice tem indegrado 0 e . - Passo indutivo: suponha o lema verdadeiro para
. Dado um tournament com vértices, remova uma cidade ; pelo HI existe um vértice no sub-tournament com
.
Ao reintroduzir, ou (então ) ou (então ). Em ambos os casos
Assim o lema vale para
.
Passo 3
Escolha uma cidade
de indegrado
. Defina
Então
e
, e como
segue
.
- Para cada
há o caminho direto . - Para cada
, note que se todo vértice de apontasse para , então , contradizendo a maximalidade de . Logo existe ao menos um com , e daí
é um caminho de comprimento 2 de
até
.
Passo 4
Portanto toda cidade
alcança
ou diretamente
ou por meio de uma intermediária
, o que mostra que
pode ser atingida de qualquer outra em no máximo dois trechos.
Resposta
Uma cidade
cujo indegrado satisfaz
é alcançável de qualquer outra cidade ou diretamente ou através de uma cidade intermediária.