Le nombre de mains : solution.
Publié le 25/01/2013

Nous allons voir que l'on dispose en fait de tous les renseignements nécessaires pour décrire la situation, à permutation près entre les couples (et à l'intérieur de chaque couple). Tout d'abord, le maître de maison à interrogé exactement 2n+1 personnes (n couples, plus sa femme), qui lui ont tous donné une réponse différente. Or un personne donnée ne peut serrer au maximum que 2n mains (celle des personne qui ne sont pas son conjoint...). Les 2n+1 réponses sont donc les entiers de 0 à 2n.


On représente les 2n+2 personnes comme les sommets d'un graphe dont les arrêtes sont les poignées demain échangées. Une des personnes, que nous appellerons A, a serré exactement 2n, soit toutes celles des autres couples. La personne qui n'a serré aucune main est alors nécessairement son conjoint : toutes autre personne a serré la main de A. Par élimination, le conjoint de A est la seule personne possible qui n'en a serré aucune.

couples1.gif

On peut alors conclure presque immédiatement : parmis les 2n personnes restantes, toutes ont déjà serré exactement une main. La personne qui a serré 2n-1 mains a donc serré toutes les mains possibles en dehors de la personne qui en a serré zéro. Par le même raisonnement, c'est son conjoint qui en a serré une seule, toutes les autres personnes ayant serré au moins deux mains.

couples2.gif

De proche en proche, on a ainsi la propriété suivante : le conjoint de la personne ayant serré 2n-i mains en a serré exactement i (où, si l'on préfère, le total des mains serrées par un couple fait exactement 2n). De proche en proche, on va ainsi épuiser tous les entiers de 0 à 2n, jusqu'à arriver au dernier couple, dont les deux conjoints ont donc serré n mains chacun.

Comme seulement une personne a déclaré avoir serré n mains, c'est que le maître de maison a lui-même serré n mains, tout comme, donc, sa femme.


Le maître de maison, tout comme sa femme, a serré exactement n mains.

N.B. Pour un peu plus de rigueur, on pourrait montrer notre résultat par récurrence sur n. Supposons le résultat établi pour n couples. Alors, lorsque l'on a n+1 couples invités, on se ramène à la situation précédente en éliminant le couple formé des personnes ayant serré respectivement 2n+2 et 0 mains, tous en enlevant une poignée de main à chacun des autres convives (celle échangée avec la personne en ayant serré 2n+2).
En utilisant notre hypothèse de récurrence, le maître de maison a donc échangé n poignées de main avec les personnes restantes, plus une avec la personne en ayant serré 2n+2, soit n+1 au total, ce qui achève la récurrence.

 
Retour à l'article: Le nombre de poignées de main
 
 
 
 
Dernières publications