Re: [obm-l] Problemas em Aberto III

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

On Thu, Feb 27, 2003 at 03:04:48PM -0300, Cláudio (Prática) wrote:
> 24) Prove que a soma dos comprimentos dos lados de um poliedro 
> convexo qualquer é maior que 3 vezes a maior distancia entre dois vertices 
> do poliedro.

Sejam x e y vértices a distância máxima. Queremos construir três
caminhos formados por arestas indo de x até y, e estes caminhos
devem ser disjuntos (exceto por x, y e possivelmente algum vértice
no meio). Ora, por maxflow-mincut estes três caminhos só *não*
existem se existir um corte feito por duas arestas, ou seja,
se existirem duas arestas que, se removidas, desconectam o grafo
formado por vértices e arestas. Mas isso estaria em contradição
com o fato de termos um poliedro convexo.

> 25) Um alienígena move-se na superfície de um planeta com velocidade 
> não superior a U. Uma espaçonave que procura pelo alienígena move-se com 
> velocidade V. Prove que a espaçonave sempre  poderá encontrar o alinígena  
> se V > 10U.

Não entendi nada. Quando é que a nave encontra o alienígena?

[]s, N.
=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================