Dans cet article, nous verrons que le regroupement par paires (présenté dans l’article précédent) peut être utilisé pour comparer le nombre d’éléments de deux ensembles.
Dans un troisième article, nous utiliserons des arrangements d’objets en groupes qui ne sont pas forcément des paires.
Les solutions des problèmes clés de l’article sont dans des blocs dépliants, pour vous donner la possibilité d’essayer de résoudre ces problèmes vous-mêmes. Il est fortement conseillé de lire les solutions avant de poursuivre la lecture de l’article. Les solutions des autres problèmes ne sont données qu’une quinzaine de jours après la parution de l’article pour vous laisser le temps de les chercher.
Problème 1. La somme des chiffres
Frédéric a écrit tous les nombres entiers entre 0 et 999 dont la somme des chiffres est paire. Frédérique a écrit tous les nombres entiers entre \(0\) et \(999\) dont la somme des chiffres est impaire. Qui a écrit le plus de nombres, Frédéric ou Frédérique ?
Solution (à lire avant de poursuivre la lecture de l’article).
Frédéric a écrit autant de nombres que Frédérique. En effet, à chaque nombre \(A\) écrit par Frédérique, on peut associer le nombre \(999 \; – A\). La somme des chiffres de \(999 \; – A\) est égale à \(27 – S(A)\), où \(S(A)\) est la somme des chiffres du nombre \(A\). Puisque le nombre \(A\) a été écrit par Frédérique, la somme \(S(A)\) est impaire. Par conséquent, \(27 – S(A)\) est pair ; le nombre \(999 \; – A\) a donc été écrit par Frédéric.
Inversement, chaque nombre écrit par Frédéric est de la forme \(999 \; – A\), où \(A\) est un nombre écrit par Frédérique. Par conséquent, Frédéric et Frédérique ont écrit autant de nombres chacun.
L’idée principale de la solution du problème 1 est un regroupement par paires, chaque paire étant formée par un nombre de Frédérique et un nombre de Frédéric. On peut formuler cette idée d’une autre manière : il existe une correspondance « un à un » entre les nombres de Frédérique et ceux de Frédéric.
Problème 2. Dominos sur l’échiquier
Considérons les recouvrements d’un échiquier de 8 × 8 cases par des dominos (chaque domino couvre deux cases et les dominos ne se chevauchent pas). Montrez que le nombre de recouvrements ayant un domino qui couvre les cases a1 et a2 est égal au nombre de recouvrements ayant un domino qui couvre les cases a1 et b1.
Solution.
À chaque recouvrement \(R\) de l’échiquier par des dominos, on peut associer le recouvrement \(s(R)\) symétrique à \(R\) par rapport à la diagonale reliant les cases \(\ a1\) et \(\ h8\).
Si le recouvrement \(R\) contient un domino \(a1 – a2\), alors le recouvrement \(s(R)\) contient un domino \(a1 – b1\) et inversement. Donc, le nombre de recouvrements ayant un domino \(a1 – a2\) est égal au nombre de recouvrements ayant un domino \(a1 – b1\).
Problème 3. Inférieur ou égal à 10
On considère les collections de nombres entiers strictement positifs dont la somme vaut 1000. Deux collections qui ne se distinguent que par l’ordre des éléments sont considérées comme identiques. Nous dirons qu’une collection est de type 1 si elle contient au plus 10 nombres et de type 2 si chaque nombre de la collection est inférieur ou égal à 10. Boris affirme qu’il y a plus de collections de type 1 que de type 2. Boris a-t-il raison ?
Solution (à lire avant de poursuivre la lecture de l’article).
Non, le nombre de collections de type 1 est égal au nombre de collections de type 2. Pour démontrer cette affirmation, associons à chaque collection de type 1 une collection de type 2 de la façon suivante.
Soit \(X = \{x_1, x_2, \ldots, x_k\}\) une collection du type 1. On a
\[
k \leq 10 \; \text{et} \; x_1 + x_2 + \ldots + x_k = 1000.
\]
En renumérotant, s’il le faut, les nombres de la collection, on peut supposer que
\[
x_1 \geq x_2 \geq \ldots \geq x_k.
\]
Représentons chaque nombre \(x_i\) sur une feuille quadrillée par une colonne de \(x_i\) petits carrés. La collection sera ainsi représentée par une suite de \(k\) colonnes rangées dans l’ordre de taille décroissante. Au total, les colonnes contiennent 1000 cases. Considérons la figure formée par ces colonnes et découpons-la maintenant en lignes horizontales. Comme il y a au plus 10 colonnes la longueur de chaque ligne ne dépassera pas 10. Notons \(y_1, \dots, y_m\) les longueurs des lignes. Nous avons
\[
y_1 + \cdots + y_m = 1000,
\]
car les lignes sont formées par les mêmes cases que les colonnes. Par conséquent \(\{y_1, \dots, y_m \}\) est une collection de type 2.
Inversement, étant donné une collection de type 2 rangée dans l’ordre décroissant, on représente chaque nombre de la collection sur la feuille quadrillée par une ligne. On empile les lignes et on découpe la figure obtenue en colonnes. Les longueurs des colonnes formeront une collection de type 1.
Il y a donc autant de collections de type 1 que de type 2.
Dans la solution du problème 3, on a associé à chaque collection de type 1 une collection de type 2. On dit que c’est une application de l’ensemble des collections de type 1 dans l’ensemble des collections de type 2. Cette application vérifie une propriété importante : chaque collection de type 2 est associée à exactement une collection de type 1, autrement dit, l’application regroupe par paires les collections de type 1 et les collections de type 2. Une telle application s’appelle une bijection. L’existence d’une bijection entre deux ensembles finis implique qu’ils ont le même nombre d’éléments.
Problème 4. Cent points bleus et un point rouge
Sur un cercle, on a marqué cent points bleus et un point rouge. Considérons tous les polygones convexes dont les sommets coïncident avec certains points marqués. Le nombre de polygones ayant un sommet rouge est-il plus grand que le nombre de polygones à sommets bleus ?
Solution (à lire avant de poursuivre la lecture de l’article).
Pour décrire un polygone, il suffit de préciser ses sommets, c’est-à-dire, une collection formée d’au moins trois points marqués. À chaque collection de points bleus, on peut associer une collection contenant le point rouge tout simplement en rajoutant le point rouge à la collection. On obtient ainsi une application de l’ensemble des polygones à sommets bleus dans l’ensemble des polygones bicolores. Cependant, cette application n’est pas une bijection.
En effet, un polygone bicolore est obtenu par la procédure décrite ci-dessus d’une manière unique, mais seulement à condition qu’il ait au moins 4 sommets. Les triangles bicolores ne peuvent pas du tout être obtenus à l’aide de cette procédure.
Donc, le nombre de polygones bicolores est strictement supérieur au nombre de polygones bleus.
Dans la solution du problème 4, on a eu affaire à une application ayant la propriété suivante : chaque élément de l’ensemble d’arrivée est associé à au plus un élément de l’ensemble de départ. Une telle application est dite injective. S’il existe une application injective \(f : X \to Y\) entre deux ensembles finis \(X\) et \(Y\), alors le nombre d’éléments de \(X\) est inférieur ou égal au nombre d’éléments de \(Y\). Si, de plus, l’application injective \(f\) n’est pas une bijection, alors le nombre d’éléments de \(X\) est strictement inférieur au nombre d’éléments de \(Y\). Voici encore quelques problèmes où nous rencontrerons des applications injectives.
Problème 5. Encore des dominos sur l’échiquier
Considérons à nouveau les recouvrements d’un échiquier de 8 × 8 cases par des dominos. Comparez le nombre de recouvrements ayant un domino qui couvre les cases a1 et a2 et le nombre de recouvrements ayant un domino qui couvre les cases b1 et b2.
Solution.
Tout recouvrement ayant un domino \(b1 – b2\) contient obligatoirement
un domino \(a1 – a2\). D’autre part, le recouvrement présenté sur le dessin ci-dessous contient un domino \(a1 – a2\), mais pas \(b1 – b2\). Donc, le nombre de recouvrements ayant un domino \(a1 – a2\) est strictement supérieur au nombre de recouvrements ayant un domino \(b1 – b2\).
Problème 6. Triangles de l’année
Nous dirons qu’un triplet de nombres entiers strictement positifs est triangulaire si les nombres du triplet sont les longueurs des côtés d’un triangle non aplati. Montrez qu’il y a moins de triplets triangulaires dont la somme des nombres vaut 2010 que de triplets triangulaires dont la somme des nombres vaut 2013.
Solution (à lire avant de poursuivre la lecture de l’article).
Considérons un triplet triangulaire formé de nombres entiers strictement positifs \(a\), \(b\) et \(c\) tels que
\[
a + b + c = 2010.
\]
Les nombres \(a\), \(b\) et \(c\) vérifient les inégalités triangulaires suivantes :
\[
\displaylines{
a + b > c, \cr
a + c > b, \cr
b + c > a.
}
\]
Considérons le triplet formé des nombres
\[
a + 1, b + 1 \; \text{et} \; c + 1.
\]
Ces trois nombres sont des entiers strictement positifs et vérifient les inégalités triangulaires
\[
\displaylines{
(a + 1) + (b + 1) > c + 1, \cr
(a + 1) + (c + 1) > b + 1, \cr
(b + 1) + (c + 1) > a + 1.
}
\]
Donc, les nombres
\(a + 1\), \(b + 1\) et \(c + 1\)
forment un triplet triangulaire. De plus,
\[
(a + 1) + (b + 1) + (c + 1) = (a + b + c) + 3 = 2013.
\]
On obtient ainsi une application de l’ensemble des triplets triangulaires de somme 2010 dans l’ensemble des triplets triangulaires de somme 2013. Cette application est clairement injective. Mais cette application n’est pas une bijection. En effet, le triplet triangulaire formé des nombres
\[
1, 1006 \; \text{et} \; 1006
\]
ne peut pas être obtenu par la procédure décrite ci-dessus. Par conséquent, il y a moins de triplets triangulaires de somme 2010 que de triplets triangulaires de somme 2013.
Problème 7. Nombres à trois chiffres
Considérons les nombres entiers strictement positifs dont l’écriture décimale a exactement trois chiffres. Parmi ces nombres, il y a des nombres dont le chiffre du milieu est strictement plus grand que les deux autres chiffres (notons \(N\) leur nombre), et des nombres dont le chiffre du milieu est strictement plus petit que les deux autres chiffres (notons \(M\) leur nombre). Comparez \(M\) et \(N\).
Solution.
Considérons un nombre \(A\) à trois chiffres
dont le chiffre du milieu est strictement supérieur aux deux
autres chiffres. Le premier chiffre
de \(A\) est strictement inférieur à \(\ 9\),
donc le nombre \(\ 999 – A\) est à trois chiffres.
De plus, le chiffre du milieu de \(\ 999 – A\) est strictement inférieur aux deux autres chiffres de \(\ 999 – A\).
On obtient une application de l’ensemble
des nombres à trois chiffres dont le chiffre du milieu
est strictement supérieur aux deux autres chiffres
dans l’ensemble des nombres à trois chiffres dont le chiffre du milieu
est strictement inférieur aux deux autres chiffres.
Cette application est clairement injective.
Mais cette application n’est pas une bijection, car aucun nombre
à trois chiffres commençant par \(\ 9\), par exemple, \(901\), ne peut être écrit comme \(\ 999 – A\), où \(A\) est un nombre à trois chiffres.
Donc, \(N < M\).
Problème 8. Une équipe pour des jeux mathématiques
Dans une classe de 31 élèves, l’enseignant de mathématiques doit choisir une équipe qui participera aux jeux mathématiques de l’école. Le nombre de membres de l’équipe n’est pas fixé, mais la classe doit être représentée aux jeux mathématiques par au moins un élève. Notons \(A\) le nombre d’équipes possibles ayant un nombre pair de membres et \(B\) le nombre d’équipes possibles ayant un nombre impair de membres. Montrez que \(B = A + 1\)
Solution (à lire).
À chaque équipe \(E\) formée d’élèves de la classe et ayant un nombre non nul pair de membres, on peut associer l’équipe, que nous appellerons {{complémentaire}}, constituée des élèves qui ne font pas partie de \(E\) ; cette équipe complémentaire a un nombre impair de membres. On obtient ainsi une application de l’ensemble des équipes ayant un nombre non nul pair de membres dans l’ensemble des équipes ayant chacune un nombre impair de membres. Cette application est injective, mais ce n’est pas une bijection. En effet, il existe exactement une équipe ayant un nombre impair de membres qui n’est pas complémentaire d’une équipe ayant un nombre non nul pair de membres : c’est l’équipe formée de tous les élèves de la classe. Donc,
\(B = A + 1\).
Dans la solution du problème 8, nous avons utilisé implicitement l’observation suivante : si \(f : X \to Y\) est une application injective entre deux ensembles finis \(X\) et \(Y\), alors le nombre d’éléments de \(Y\) est égal au nombre d’éléments de \(X\) augmenté du nombre d’éléments de \(Y\) qui n’appartiennent pas à l’image de \(f\).
Problèmes à résoudre par vous-mêmes
Problème 1. Deux cases enlevées
On a enlevé deux cases d’un échiquier de 8 × 8 cases : la case en bas à gauche et la case en haut à droite. Peut-on recouvrir le reste de l’échiquier par des dominos ? (Chaque domino doit couvrir deux cases et les dominos ne peuvent pas se chevaucher.)
Problème 2. Chevaliers et menteurs
Cinquante personnes sont assises autour d’une table ronde. Chaque personne est soit un chevalier qui dit toujours la vérité, soit un menteur qui ment toujours. Toute personne autour de la table a exactement un ami à cette table et, dans chaque paire d’amis, un des amis est un chevalier et l’autre est un menteur. A toutes les personnes assises autour de la table, on a posé la question suivante : « Votre ami est-il assis à côté de vous ? » Combien de personnes ont répondu « Oui » ?
Problème 3. Pions sur un damier
Vingt-cinq pions sont placés dans les cases d’un damier de 5 × 5 cases (un pion par case). Louis veut déplacer tous les pions de telle façon que chaque pion soit déplacé dans une case voisine (ayant un côté commun avec la case initiale) et chaque case contienne à nouveau exactement un pion. Peut-il y arriver ?
Problème 4. Le nombre de chiffres et le nombre de zéros
Montrez que le nombre total de chiffres dans l’écriture décimale des nombres entiers
\[
1, 2, \ldots, 10^5
\]
est égal au nombre total de zéros dans l’écriture décimale des nombres entiers
\[
1, 2, \ldots, 10^6.
\]
Problème 5. Mille nombres
Notons \(P\) la somme des chiffres de tous les nombres pairs entre 1 et 1000. Notons \(I\) la somme des chiffres de tous les nombres impairs entre 1 et 1000. Lequel des deux nombres \(P\) et \(I\) est le plus grand et de combien ?
Post-scriptum
Les lecteurs sont invités à nous proposer leurs solutions des « Problèmes à résoudre par vous-mêmes ». Les solutions peuvent être rédigées comme commentaires sur l’article ou envoyées à l’adresse suivante : ensortantdelecole@images.math.cnrs.fr
Les meilleures solutions seront publiées dans la rubrique.
L’équipe de la rubrique remercie Nikita Itenberg pour les illustrations qu’il a faites pour cet article.
NDLR : Retrouvez les autres articles sur le sujet ici : I et III, et les autres articles de la rubrique : En sortant de l’école.
Article édité par l’équipe de la rubrique « En sortant de l’école ».
Il est possible d’utiliser des commandes LaTeX pour rédiger des commentaires — mais nous ne recommandons pas d’en abuser ! Les formules mathématiques doivent être composées avec les balises .
Par exemple, on pourra écrire que sont les deux solutions complexes de l’équation .
Si vous souhaitez ajouter une figure ou déposer un fichier ou pour toute autre question, merci de vous adresser au secrétariat.