Exercice 3 ( Easy)



  • Dans une classe de n personnes , on a les conditions suivantes qui sont vérifiées.
    2 élevés sont soit amis soit ennemis.
    Chaque élève a exactement 3 ennemis .
    L' ami de ton ennemi est ton ennemi.
    Trouver les valeurs possibles de n.



  • @Mamoun
    chaque personne a exactement 3 ennemis et 2 amis et dans ce cas n=6 et n=4,5



  • n=4,5 aussi



  • On a necessairement n4n\geq4
    Soit EE={A1A_1,A2A_2,...,AnA_n} l'ensemble de n personnes verifiant ces conditions. WLOG AnA_n , An1A_{n-1},An2A_{n-2} sont les 3 ennemies de A1A_1 donc ce sont exactement les ennemies de l'ensemble {A1A_1,A2A_2,A3A_3..,An3A_{n-3} } de n3n-3 elements , donc n3n-3 est au plus 3, i.e n6n\leq6
    D'ou n=4n=4 ou n=5n=5 ou n=6n=6



  • @Driouiche-Youness

    À oui j ai oublié les cas où 4=<n<=5



  • Il faut donner un exemple de configuration dans ce genre d exercices . Et toutes les solutions données jusqu'à maintenant sont erronées carr elle n ont pas prise en compte une condition



  • @Mamoun
    Moi j ai donné le résultat final



  • Clairement n>=4 . On considere le graphe G tel que chaque eleve est représente par un sommet et la relation d amitié par une arete . Chaque eleve a n-4 amis donc il y a n(n-4)/2 aretes . Donc n est pair.
    Prenons un eleve quelconque il a 3 ennemis et n-4 amis. Prenons un ennemi de cet eleve alors par la condition de l exercice il a au moins n-3 ennemis. Donc n<=6.
    Pour n=4 On considere un graphe complet a 4 sommets.
    Pour n=6 le graphe bipartite G3,3 G_{3,3}



  • ok ! pour 4 on prend 4 personnes ennemies ,, et pour 6 , 3 amis qui sont les ennemis de 3 autres amis



  • Pour montrer que n est pair . On peut aussi remarquer que si n impair alors les degres de chaque sommets sont impairs. On aura donc le nombre de sommets à degrés impairs dans ce graphe est impair . Ce qui est absurde



  • @Mamoun hahahhah la première démonstration f théorie de graphe


Log in to reply
 

Looks like your connection to Expii Forum was lost, please wait while we try to reconnect.