Bonjour

1) Tu as décrit un tel graphe

2) "Deux personnes A et B connaissent le même nombre de personnes" signifie que A et B ont le même degré. Supposons que ce ne soit jamais le cas ; ça signifierait alors que tous les sommets ont des degrés différents.

Plaçons-nous dans cette dernière hypothèse et appelons n le nombre de sommets. Il est clair que chaque sommet a un dégré strictement inférieur à n. Comme tous les degrés sont distincts et qu'il y a n sommets, il y a forcément un sommet de degré 0, un sommet de degré 1, un sommet de degré 2, ..., un sommet de degré n-1.

Mais alors il existe donc un sommet de degré n-1, c'est-à-dire un sommet relié à tous les autres, et en particulier au sommet de degré 0 !! Ce qui est absurde puiqu'il est de degré 0.

L'hypothèse de départ est donc à rejeter, et par conséquent il existe au moins deux sommets de même degré.

Conclusion : dans une assemblée de n personnes, il y a toujours au moins deux personnes qui connaissent le même nombre de personnes.

Sauf erreur.

c'est vraiment une approche à laquelle nous sommes peu habitués.... et c'est un beau raisonnement! je ne l'avais pas encore trouvé!!....

Merci garnouille (et bonjour). Je me suis intéressé aux graphes quand ils sont apparus au programme de TES (en 2002 je crois), et il m'en est resté quelques bribes.

moi, je suis en plein dedans cette année, c'est intéressant mais c'est pas toujours évident de tirer la bonne "ficelle"...