Le principe des tiroirs

Application directe du cours · niveau 2 · mathématiques (PTSI), chapitre 15 — Dénombrement · A. Cardinaux et opérations

Énoncé

Montrer que dans un groupe de $367$ personnes, deux au moins ont le même jour d'anniversaire. Montrer que dans toute réunion de $n \geq 2$ personnes, deux personnes connaissent exactement le même nombre de participants.

Corrigé

Anniversaires : l'application « personne $\mapsto$ jour d'anniversaire » va d'un ensemble de cardinal $367$ vers un ensemble de cardinal au plus $366$ : elle ne peut être injective.

Connaissances : chaque personne connaît entre $0$ et $n - 1$ participants, soit $n$ valeurs possibles pour $n$ personnes — les tiroirs semblent suffire ! Mais les valeurs $0$ (quelqu'un ne connaît personne) et $n - 1$ (quelqu'un connaît tout le monde) sont incompatibles : au plus $n - 1$ valeurs sont effectivement prises, pour $n$ personnes. Le principe des tiroirs conclut : deux personnes ont le même nombre de connaissances.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.