Vous pouvez retrouver cette question au format pdf.

Question du jeudi #8 : Sur le réseau social Friendface, chacun des $n$ membres peut être ami avec n'importe quel autre membre (mais pas avec lui-même). La relation est symétrique : si Moss est ami avec Roy, Roy est ami avec Moss. Montrer que deux des membres de Friendface ont exactement le même nombre d'amis.

À première vue, la clef de cette question semble être le principe des tiroirs (aussi appelé principe de Dirichlet) : si on essaie de mettre $p$ chaussettes dans $q < p$ tiroirs, un des tiroirs contiendra au moins deux chaussettes. De manière plus mathématique, aucune fonction $f : E_p \to E_q$ entre un ensemble de cardinal $p$ et un ensemble de cardinal $q$ ne peut être une injection.

Ici, on a très envie d'appliquer le principe des tiroirs en prenant l'ensemble des membres du réseau social comme ensemble de départ et les nombres d'amis possibles comme ensemble d'arrivée. L'ensemble de départ a donc exactement $n$ éléments ; combien en a l'ensemble d'arrivée ? Chacun des membres peut a priori être ami avec tous les autres (ce qui fait $n-1$ amis), n'être ami avec personne ($0$ ami) ou n'importe quelle situation intermédiaire. La fonction « nombre d'amis »

$$ N : \{\textrm{membres du réseau social}\} \to \{0, 1, \ldots, n - 1\}$$

est donc une fonction entre ensembles à $n$ éléments et le principe des tiroirs ne s'applique pas.

Puisque les deux ensembles ont $n$ éléments, deux choses peuvent se passer :

• La fonction $N$ envoie deux éléments sur la même image. Autrement dit, deux membres du réseau social ont le même nombre d'amis. C'est ce que l'on veut démontrer.
• La fonction $N$ est une bijection : il existe exactement un membre du réseau social sans ami, exactement un membre n'ayant qu'un ami, ..., exactement un membre ayant $n-2$ amis et exactement un membre ayant $n-1$ amis. Il n'y a plus qu'à montrer que cette hypothèse est impossible. L'argument est simple : si un des membres du réseau a $n-1$ amis, il est ami avec tous les autres. En particulier, aucun des membres du réseau ne peut avoir $0$ ami. Cette hypothèse est donc absurde.

Ainsi, deux membres du réseau ont le même nombre d'amis.

Remarquons que ce que l'on vient de démontrer peut en fait se reformuler comme un résultat de théorie des graphes : dans un graphe (simple) fini, il existe deux sommets de même degré.