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 é <[EMAIL PROTECTED]> =========================================================================