Exercice 3 ( Easy)

[Mamoun]

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.

[Fahd Et-tahery]

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

[Driouiche Youness]

n=4,5 aussi

[Abdellah Elmrini]

On a necessairement $n\geq4$
Soit $E$={$A_1$,$A_2$,...,$A_n$} l'ensemble de n personnes verifiant ces conditions. WLOG $A_n$ , $A_{n-1}$,$A_{n-2}$ sont les 3 ennemies de $A_1$ donc ce sont exactement les ennemies de l'ensemble {$A_1$,$A_2$,$A_3$..,$A_{n-3}$ } de $n-3$ elements , donc $n-3$ est au plus 3, i.e $n\leq6$
D'ou $n=4$ ou $n=5$ ou $n=6$

[Fahd Et-tahery]

@Driouiche-Youness

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

[Mamoun]

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

[Fahd Et-tahery]

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

[Mamoun]

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 $G_{3,3}$

[Abdellah Elmrini]

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

[Mamoun]

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

[Ilyas ainaq]

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