[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[obm-l] Re:traduçao de um problema



  Ola Niski , Eder,
 
 
             ....acho que é isso mesmo, se nao for, fica entao uma interpretaçao alternativa (e bonita) do enunciado.
      Uma estrategia simples que eu usei foi considerar hipoteticamente que nao houvesse quaisquer duas pessoas com numero de conhecidos semelhantes, visando encontrar alguma contradiçao.
     
      *Vamos supor que o numero de conhecidos de cada pessoa seja distinto do numero de conhecidos de qualquer outro, ou melhor, que os elementos de S={ x(1) , x(2) , ...... , x(n) }
que representam o numero de conhecidos de cada um, sejam tais que x(1)<x(2)<......<x(n)
     
 1 Caso) x(1)<x(2)<......<x(n) com x(1)=0, implica x(2)>=1, que implica x(n)>=(n-1)         absurdo!Pois o individuo An no minimo nao pode escolher nem a si mesmo nem a pessoa A1 como companheiros, logo x(n) no maximo vale (n-2).Existe entao algum x(i)=x(j) para x(1)=0
pois como vimos acima é impossivel existir x(1)<x(2)<......<x(n).
 
2 Caso) x(1)<x(2)<......<x(n) com x(1)>0, implica x(1)>=1, que implica x(n)>=n, absurdo novamente!Pois o individuo An  tem no maximo (n-1) conhecidos.Logo existe algum x(i)=x(j) para x(1)>0, dado que nao é possivel se ter x(1)<x(2)<......<x(n).
 
              Conclusao:Em um grupo de n pessoas, sempre existe ao menos 2 pessoas que possuem um mesmo numero de conhecidos ou amigos.
 
 
                              Por hoje é só....
 
                                                 Um abraço
 
                                                                  Felipe Mendonça                Vitória-ES
 
 
 
 


MSN Hotmail, o maior webmail do Brasil. Faça o seu agora. ========================================================================= 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 =========================================================================