Outra solucao, mais direta IMHO, usa o teorema de Turan: "Dado um grafo (G,V), se não existem subgrafos k-completos nele, entao o numero de arestas maximo e obtido em uma configuracao desta forma: k-1 grupos de vertices, cada um contendo o mesmo numero de vertices (ou o mais proximo disso, usando uma divisao euclidiana). Cada vertice conecta-se a todos os vertices que nao sejam de seu grupo."
De certo modo, isto demonstra que a solucao que o WGAP mostrou para o maximo e unica. Bem, depois eu envio uma solucao do teorema de turan. Nao e dificil demonstra-lo para o caso acima (o grafo nao contem triangulos). Para quem for curioso, o famoso livro Proofs from THE BOOK contem tres ou quatro provas. Em 18/08/10, Willy George do Amaral Petrenko<wgapetre...@gmail.com> escreveu: > *O planeta Walrus possui 20 países. Sabe-se que, dentre quaisquer três > desses países, existem dois sem relações diplomáticas. Prove que Walrus > possui no Maximo 200 embaixadas*. > > O número mínimo de embaixadas é zero. O enunciado diz "existem 2 sem > relações", e não "existem EXATAMENTE 2 sem relações". De fato, se nenhum > país faz diplomacia com ninguém, o enunciado é satisfeito. > > Mas vamos à idéia da demonstração: > > Notação: Chamarei de amigos os países que tiverem relações diplomáticas e de > inimigos os que não tiverem. > > Repare que se um país A é amigo de B e C, então B é inimigo de C. > Repare também que se um país é amigo de todos os outros, então todos os > outros são inimigos entre si, fazendo um total de 38 embaixadas. > Agora, veja que se nenhum país tem mais de 10 amigos então o enunciado é > satisfeito. > > Suponha agora por absurdo que existam + de 200 embaixadas e que algum país A > tenha 11 amigos. > Então esses 11 amigos de A serão inimigos mútuos, fazendo com que cada um > deles tenha um máximo de 9 amigos. > Esses 12 países (A + os 11) terão um máximo de 11 + 9*11 = 110 embaixadas. > Os outros 8 países então devem ter mais de 90 embaixadas (para satisfazer o > mais de 200). Pelo princípio da casa dos pombos algum terá 12 amigos. > > Provamos então que se o total de embaixadas é maior que 200 e alguém tem 11 > amigos então alguém tem 12 amigos. > *A idéia agora é provar que se o total de embaixadas é maior que 200 e > alguém tem 10+n amigos, onde n natural pertencente a [1,8], então alguém tem > 10+n+1 amigos. [é fácil, a mesma idéia, só trabalhar com letrinhas].* > Com isso completa-se a indução. > > A indução mostra que se existem +de 200 embaixadas e alguém tem 11 amigos > então alguém tem 19 amigos e logo o número de embaixadas é 38, absurdo. > E se ninguém tem +de 10 amigos então o número de embaixadas é <= 200. > > Isso completa a prova. > > Dá para dar um exemplo onde existem 200 embaixadas (embora o enunciado não > peça): > Países de 1 a 10 inimigos entre si e amigos de todos os países de 11 a 20. > Países de 11 a 20 inimigos entre si e amigos de todos os países de 1 a 10. > > Espero que tenha entendido a idéia. Se vc não conseguir completar a prova > avisa que eu escrevo. > -- /**************************************/ Quadrinista e Taverneiro! http://tavernadofimdomundo.blogspot.com >> Quadrinhos, histórioas e afins http://baratoeletrico.blogspot.com />> Um pouco sobre elétrons em movimento http://bridget-torres.blogspot.com/ >> Personal! Do not edit! ========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
