[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Desafio



Olá Vivi,

Vou tentar uma demonstração da impossibilidade aqui, utilizando
a fórmula de Euler. O raciocínio se faz por absurdo...

Primeiro, vamos representar o problema no plano.

O argumento segue por grafos, portanto vou chamar de vértice um
dos 6 pontos: F1, F2, F3, C1, C2, C3 (C de casa, F de fornecedora).
As ligações entre algum Ci e algum Fi serão as arestas, e as faces
do grafo serão as áreas determinadas por "loops" fechados de vértices,
sem nenhuma aresta ou vértice dentro.
Intuitivamente falando, uma face é aquela região "limpinha" que as arestas
estão cercando.

Que tipos de faces podemos ter?

Certamente não teremos nenhuma casa ligada diretamente com
outra casa, nem uma fornecedora ligada diretamente com outra fornecedora.

Então todas as conexões são do tipo Ci -> Fi -> Cj -> ... etc.

Um exemplo de face é: F1 -> C1 -> F2 -> C2 (E daí volta para F1.)

Neste caso, essa face tem 4 vértices, a saber: F1, C1, F2, C2.

Claramente, não podemos ter uma face com menos de 4 vértices, justamente
porque não vamos ligar fornecedora com fornecedora nem casa com casa.

Uma outra face seria mais longa: F1 -> C1 -> F2 -> C2 -> F3 -> C3 (Volta para F1).

Neste caso, temos 6 vértices. Estas são as únicas faces possíveis.

O Teorema de Euler no plano diz que Faces + Vértices = Arestas + 2.

Temos 6 vértices, e 9 arestas, pois estamos ligando cada uma das 3 casas
em 3 fornecedoras.

Assim, o Teorema de Euler nos dá: Faces + 6 = 9 + 2 => Faces = 5.

Agora, supomos o problema resolvido, e vamos contar de outro modo
os vértices.
Vimos acima que toda face tem pelo menos 4 vértices. Se temos 5 faces,
5 * 4 = 20 vértices. Mas nesse raciocínio contamos duas vezes cada vértice,
pois uma aresta pode ser comum à duas faces distintas, e aí os dois vértices
extremos desta aresta foram contados duas vezes.

Ainda assim, temos 20 / 2 = 10 vértices, contrariando o fato de só termos 9.

Abraço,

- Leandro.