> Num pr�dio de apartamentos h� 7 elevadores que param > em n�o mais que 6 andares. > � poss�vel ir de um andar a qualquer outro sem > trocar de elevador. Qual � o > n�mero m�ximo de andares que esse pr�dio pode ter? > (RPM/IME/USP)
Se considerarmos cada andar como um v�rtice de um grafo, temos que cada elevador conecta 6 v�rtices, formando um sub--grafo com arestas entre todos os 6 v�rtices, ou seja 6*5/2 = 15 arestas. Temos 7 elevadores, ent�o temos 105 arestas. Se N � o n�mero de andares, N satisfaz 105 >= N*(N-1)/2 para satisfazer a condi��o do enunciado. N � m�ximo quando 105 = N*(N-1)/2 ent�o: N^2 - N - 210 = 0 (N+14)*(N-15) = 0 ent�o N = 15 []'s, H�lder T. Suzuki _______________________________________________________________________ Yahoo! Mail Mais espa�o, mais seguran�a e gratuito: caixa postal de 6MB, antiv�rus, prote��o contra spam. http://br.mail.yahoo.com/ ========================================================================= 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 =========================================================================
