Imaginez un professeur qui annonce à sa classe que la moyenne au dernier devoir est 12 mais qui ne rend pas les copies. Que peuvent en déduire les élèves ? Pas grand-chose à vrai dire, il est bien connu que la moyenne est un indicateur statistique très imparfait qui ne donne que très peu d’informations sur la distribution des données. Il y a toutefois une information connue à coup sûr : un ou une élève a une note supérieure ou égale à 12 (et de manière symétrique quelqu’un a une note inférieure ou égale à 12) ; en effet, si tout le monde avait une note inférieure strictement à 12, la moyenne de toutes ces notes, c’est-à-dire la moyenne annoncée par le professeur, le serait aussi.
C’est un phénomène assez élémentaire à comprendre : dans tout jeu de données, il y en a toujours une qui est supérieure ou égale à la moyenne. On aurait sûrement tendance à négliger ce fait si Paul Erdős n’en avait fait le cœur d’un outil à la puissance redoutable : la méthode probabiliste.
Trop de poignées de main ------------------------
Pour comprendre le principe de cette méthode, détaillons un exemple en partant d’un résultat classique. Le théorème des poignées de main (appelé aussi « théorème des amis et des étrangers ») est un résultat qui indique que, lorsque l’on met 6 personnes dans une salle, on peut toujours en trouver 3 qui se sont toutes serré la main ou 3 telles qu’il n’y a eu aucune poignée de main entre elles\*. Ce résultat appartient désormais au folklore mathématique et on vous encourage à le démontrer si vous ne l’avez jamais rencontré auparavant. Vous pouvez également vérifier que le nombre 6 dans cet énoncé est optimal en exhibant une configuration de 5 personnes qui mette en défaut la propriété, c’est-à-dire telle que, pour tout groupe de 3 personnes choisies parmi les 5, il y en a toujours 2 qui se sont serré la main et 2 qui ne se sont pas serré la main d’où l’impossibilité de trouver un groupe de 3 personnes qui se sont toutes serré la main ou un groupe de 3 avec aucune poignée de main entre elles. Une telle configuration peut être construite explicitement.
(\* Ce qu’on peut également formuler : dans un groupe de 6 personnes, on peut toujours en trouver 3 qui se connaissent ou 3 qui ne se connaissent pas.)