Raisonnements de graphes

Exercice 1. (qui se connaît?)
Montrer qu’à une soirée réunissant au moins six personnes, il y a au moins trois personnes qui se connaissent mutuellement, ou au moins trois qui sont étrangères les unes aux autres.
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Exercice 2. (langage commun dans un meeting)
On suppose que {2018} personnes prennent part à un meeting international.
Chacun des participants parle au plus cinq langages différents.
Enfin, on suppose que dans chaque groupe de trois congressistes, deux au moins parlent le même langage. Prouver qu’il y a au moins {200} personnes qui parlent le même langage.
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Exercice 3. (un problème de coloriage)

  1. Les {15} segments joignant six points distincts d’un cercle sont colorés en bleu ou en rouge. Montrer que l’un au moins des triangles définis par ces points est monochrome.
  2. On suppose que les {36} segments joignant neuf points distincts d’un même cercle sont colorés en bleu ou en rouge. On suppose aussi que le triangle défini par trois quelconques de ces neuf points contient toujours au moins un coté rouge. Prouver qu’il y a au moins quatre points tels que les six segments qui les joignent soient rouges.

Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Exercice 4. (re-coloriages d’un octogone)
On colorie les différents cotés d’un octogone, soit en bleu, soit en jaune.
On recolorie simultanément les huit cotés de la manière suivante : si les deux voisins d’un coté sont de couleur différente, alors il est re-colorié en bleu sinon en jaune.
Montrer qu’au bout d’un nombre fini de tels re-coloriages, tous les cotés sont jaunes.
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez :