*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.
