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
Soit={ , ,..., } l'ensemble de n personnes verifiant ces conditions. WLOG , , sont les 3 ennemies de donc ce sont exactement les ennemies de l'ensemble { , , .., } de elements , donc est au plus 3, i.e
D'ouou ou
-
À 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
-
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