Re: RES: Canos

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Fri, 31 Mar 2000, Marcos Paulo wrote:

> 
> Esse problema eh classico de grafos mas ouvi dizer q se os elementos
> estivessem num toro isso seria possivel!

É correto. Fica como exercício determinar o maior N tal que é possível
em um toro ligar todos os pares dentre N pontos sem criar interseções.
[]s, N.

> -----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.
> 
>