6 pessoas: Imaginando grafos, vou chamar um trio de pessoas de um triangulo. 1. Note que em um determinado grupo que satisfaz uma das condições, se todas as relações entre as pessoas se “inverterem” (ou seja, pessoas que se conhecem passam a não se conhecer e vice versa), agora o grupo passa a satisfazer a outra condição, afinal um “triângulo” em que 3 pessoas se conhecem vira um em que 3 pessoas não se conhecem
2. Se as condições não são satisfeitas e a pessoa A conhece B, C, e D, no triangulo ABC, AB se conhecem, e AC se conhecem, então BC não podem se conhecer, analogamente, CD, e BD também não podem, mas então existiria o triangulo BCD, em que ninguém se conhece, satisfazendo uma condição, logo: Se uma pessoa conhece 3 outras, a condição obrigatoriamente é satisfeita 3. Consideremos um grupo de 6 pessoas, A,B,C,D,E e F, Agora, vamos analisar a relação da pessoa A com todas as outras, uma relação só pode ser Conheçe, ou Não conhece, que representarei com C e N, A relação de A com BCDE, respectivamente, pode ter 2 C e 2 N (se não for isso, a condição já estaria satisfeita apenas analisando essas 4 relações), mas a relação de A com a pessoa F precisa obrigatoriamente ser C ou N, fazendo com que A conheça 3 outras pessoas, ou não conheça 3 outras pessoas (no segundo caso, basta “inverter” todas as relações e o lema no segundo ponto se aplica), assim, em um grupo com 6 pessoas, precisa existir alguém que conhece outras 3 pessoas simultaneamente, então, aplicando o lema no segundo ponto, precisa existir um triangulo de pessoas que não se conhece entre si (ou ao contrario, como foi discutido no primeiro ponto). Finalmente 4. Existem grupos de 5 pessoas em que as condições não se satisfazem: para isso, basta mostrar um exemplo, considere o grupo de pessoas A,B,C,D e E e suponha que todas as arestas no pentágono ABCDE sejam relações “Conhece” e que todas as arestas no pentágono ACEBD sejam relações “Não conhece”, aqui as condições não são satisfeitas (oara ver isso mais facilmente, basta imaginar ABCDE como um pentágono regular e ACEBD como a estrela que se forma dentro dele) Um Abraço, Pedro Cardoso De: Pedro Chaves Enviado:terça-feira, 1 de agosto de 2017 17:43 Para: [email protected] Assunto: [obm-l] Amigos comuns (um probleminha) Caros Colegas, Solicito ajuda para a questão abaixo. Abraços do Pedro Chaves. --- Amigos comuns --- Helena é uma perfeita anfitriã. Quando organiza uma festa, se assegura de que ao menos três pessoas se conheçam entre si. Ou, se isso não for possível, que ao menos haja três pessoas que não se conheçam (para assim poder apresentá-las). Qual é o menor número de pessoas que Helena precisa convidar, para assegurar-se de que se dê alguma dessas duas condições? --------------------------------------------------xxx---------------------------------------------------------------------------------------- -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
