[obm-l] Intervalos Intersectantes

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Aqui vai um interessante:

Seja n um inteiro >= 0.
Dados n^2+1 intervalos (distintos, Niski!) na reta real, ou existem n+1
intervalos mutuamente disjuntos ou n+1 intervalos cuja interseccao (dos n+1)
eh nao-vazia.

O interessante eh que se voce usar um grafo completo com n^2+1 vertices, no
qual cada vertice representa um intervalo, pintar de azul as arestas que
ligam vertices correspondentes a intervalos intersectantes e de vermelho as
outras, a construcao falha para n = 2, pois eh possivel pintar as arestas de
um grafo completo com 5 vertices sem que se forme um triangulo
monocromatico.

[]s,
Claudio.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================