RES: Canos

["Marcos Paulo" <mparaujo@xxxxxxxxxxxxx>]

Esse problema eh classico de grafos mas ouvi dizer q se os elementos
estivessem num toro isso seria possivel!
-----Mensagem original-----
De: owner-obm-l@mat.puc-rio.br [mailto:owner-obm-l@mat.puc-rio.br]Em
nome de Nicolau C. Saldanha
Enviada em: quinta-feira, 30 de março de 2000 18:38
Para: obm-l@matinta.mat.puc-rio.br
Assunto: Re: Canos




On Thu, 30 Mar 2000, Eduardo Casagrande Stabel wrote:

> Faz um tempao que eu nao mando mensagem para a lista.
> Tem um problema que nao sei resolver.
>
> Temos 3 asteriscos e 3 ozinhos, temos que ligar com uma linha (pode ser
> curva) cada asterisco a cada ozinho sem que uma linha cruze uma outra.
> A disposicao e' a seguinte:
> *        *         *
>
> o        o         o
> Pelo que sei nao da pra fazer, mas como que se prova isso?
>
> Eduardo Casagrande Stabel.
>

A localização dos pontos não é importante.
Suponha por absurdo que fosse possível com três o e três * na esfera.
Obtemos assim uma decomposição da esfera com 6 vértices e 9 arestas.
Pela fórmula de Euler devemos ter 5 faces.
Cada face tem um número par de vértices
(pois eles alternam entre o e *), donde pelo menos 4.
Assim, o número total de lados de todas as faces é pelo menos 5*4 = 20.
Cada aresta corresponde a 2 lados, donde temos pelo menos 10 arestas,
contradição.