CultureMath
- Généralités
- Logique
- Mathématiques discrètes, algorithmique
- Algèbre
- Arithmétique
- Géométrie
- Topologie
- Analyse
- Probabilités
- Statistique
- Analyse numérique
- Interactions des mathématiques
- Mathématiques et physique
- Mathématiques et sciences de la vie
- Mathématiques et économie
- Mathématiques et autres disciplines
- Histoire des mathématiques
- Histoire : généralités
- Histoire : Mésopotamie
- Histoire : Grèce
- Histoire : autres mathématiques anciennes
- Histoire : Europe (jusqu'au dix-huitième siècle)
- Histoire : Europe (à partir du dix-neuvième siècle)
- Didactique, histoire de l'enseignement
- Épistémologie
- Ethnomathématiques
- Thèmes > Mathématiques discrètes, algorithmique ,
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.
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.
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.
- Vade-mecum Clubs de mathématiques
- Brève 35 : Publimath | 50 ans des IREM
- Les algorithmes gloutons
- Brève 34 : L’intégrale de 1981 à nos jours : deux brochures pour témoigner des réformes | 50 ans des IREM
- Les laboratoires de mathématiques à l'international
- Brève 33 : Promotion d’une perspective historique en classe | 50 ans des IREM
- Brève 32 : Agrandir, réduire | 50 ans des IREM
- Brève 31 : La formation à distance des professeurs d’école | 50 ans des IREM
- Brève 30 : Deux réformes fondamentales de l’enseignement des mathématiques | 50 ans des IREM
- Brève 29 : Interdisciplinarité | 50 ans des IREM