Théorie > Fondements > Rédaction d'une preuve

Général
Résumé Chapitre entier
Points théoriques
Conseils généraux Exemple algébrique Exemple géométrique Exemple combinatoire Exercice supplémentaire
Exercices
Exercice 1 Exercice 2

Exemple combinatoire

Voici un troisième problème ainsi qu'une solution mal rédigée à celui-ci. À nouveau, notre but est de montrer tout ce qui peut être amélioré dans cette solution.

Problème
On dit que deux nombres à trois chiffres sont similaires s'ils ont au moins deux chiffres en commun, à la même position. Par exemple, les nombres $284$ et $204$ sont similaires, mais les nombres $379$ et $973$ ne le sont pas. Quelle est, au maximum, la taille d'un sous-ensemble de $S = \{100, 101, \ldots, 999\}$ ne contenant aucune paire de nombres similaires ?

Solution 1 (mauvaise)
Prenons les $90$ nombres $100, 111, 122, \ldots, 199, 201, 212, \ldots, 290, \ldots, 908, 919, \ldots, 997$. Ces nombres ne sont pas similaires car si ils ont le même chiffre des centaines alors ils n'ont pas le même chiffre des dizaines et pas le même chiffre des unités et s'ils n'ont pas le même chiffre des centaines alors ils n'ont pas à la fois le même chiffre des dizaines et le même chiffre des unités car on a décalé le chiffre des unités par rapport au chiffre des dizaines à chaque nouvelle centaine. Si on prend $91$ nombres au lieu de $90$ alors le dernier nombre devra forcément avoir le même chiffre des centaines que $10$ autres nombres et ce nombre sera forcément similaire à l'un des $10$ nombres car tous les chiffres des dizaines sont déjà pris.

Beaucoup de critiques peuvent être émises quant à cette solution :

  • La liste des $90$ nombres n'est pas du tout évidente à comprendre. C'est un exemple typique où l'élève sait parfaitement ce qu'il veut dire vu qu'il a réfléchi à la construction de ces nombres pendant longtemps, mais un lecteur qui n'est pas dans sa tête ne va pas facilement comprendre comment compléter les petits points de la liste, ni ce qui a amené l'étudiant à considérer ce sous-ensemble assez particulier. Il n'est en fait même pas clair qu'il y a exactement $90$ nombres dans ce sous-ensemble. L'élève devrait réfléchir à une meilleure manière de présenter ces nombres, pour donner une meilleure intuition de ce qu'il est en train de faire. Une façon de le faire consiste à donner une formule explicite : il s'agit ici des nombres $\overline{abc}$ avec $c = a+b-1$ (ou $a+b-11$ si $a+b \ge 11$).

  • La deuxième phrase de cette solution est beaucoup trop longue, sans aucun signe de ponctuation, ce qui la rend quasi incompréhensible ! Il faut absolument découper une telle phrase à rallonge en plusieurs morceaux, sans quoi personne ne va avoir le courage de poursuivre la lecture de cette solution. Par ailleurs, cette phrase est très peu rigoureuse pour prouver qu'il n'y a pas deux nombres similaires parmi les $90$ qui ont été donnés. L'élève explique à peu près comment il a essayé d'éviter d'avoir deux nombres similaires lors de la construction de ses $90$ nombres, mais il ne donne pas de justification suffisamment claire au fait que ça fonctionne. C'est en fait une conséquence de la première remarque : les nombres n'ont pas été décrits de manière très explicite donc il est difficile d'apporter une preuve rigoureuse au fait que ces nombres vérifient une certaine propriété.

  • Sur base de ces deux premières remarques, on peut essayer de formaliser la preuve. Nous avons vu plus haut que les $90$ nombres sont ceux de la forme $\overline{abc}$ avec $c = a+b-1$ (ou $a+b-11$ si $a+b \ge 11$). Une erreur classique consiste, lorsqu'on pense avoir trouvé une solution à un problème, à foncer tête baissée dans sa rédaction sans se demander si elle ne pourrait pas être légèrement modifiée pour la rendre plus courte ou plus facile à rédiger. Ici, notre formule $c = a+b-1$ ou $a+b-11$ n'est pas très jolie, et elle risque d'être pénible à utiliser pour nous justifier. Après un peu de réflexion, on peut voir qu'une façon d'éviter ce "ou" est de dire que $a+b-1-c$ doit être divisible par $10$. C'est déjà plus joli, mais continuons à prendre un peu de recul. Cette expression $a+b-1-c$ est un peu bizarre, avec ce $-1$ et ce $c$ précédé d'un signe $-$ alors que $a$ et $b$ sont précédés d'un $+$. Ne pourrait-on pas modifier cette expression, quitte à modifier légèrement la liste des $90$ nombres ? Que se passe-t-il si on prend les nombres $\overline{abc}$ tels que $a+b+c$ est divisible par $10$ ? Cela marche aussi ! Et voilà, on a trouvé un sous-ensemble de $90$ nombres beaucoup plus facile à décrire, et cela va grandement simplifier la rédaction d'une preuve rigoureuse au fait qu'il n'y a pas deux nombres similaires parmi ceux-ci. C'est fait dans la solution ci-dessous.

  • La dernière phrase, pour montrer que $91$ ne fonctionne pas, est également très mal écrite. Même si l'idée est là, l'étudiant semble justifier les choses en rajoutant un $91^\text{ème}$ nombre aux $90$ déjà choisis. C'est une erreur commune : on ne peut pas supposer que les $90$ premiers nombres sont d'une forme particulière pour prouver que ça ne fonctionnera pas avec $91$ nombres ! Pour rendre cette preuve rigoureuse, il faut trouver une manière plus générale de présenter les choses. Le principe des tiroirs, comme souvent, peut ici nous aider.

  • Il n'y a aucune conclusion dans cette solution : l'étudiant ne répond même pas explicitement à la question qu'on lui pose ! Dans un tel problème où on demande de trouver le plus grand nombre vérifiant une propriété, une bonne façon de rédiger sa solution consiste à commencer par donner la réponse numérique et expliquer la stratégie que l'on va adopter pour la prouver. Lorsque la preuve se découpe en plusieurs parties comme ici (montrer que $90$ fonctionne puis que $91$ ne fonctionne pas), il est aussi naturel de scinder la preuve en plusieurs paragraphes.

Voici une meilleure solution prenant en compte toutes ces remarques.

Solution 2 (bonne)
Nous allons montrer que la réponse est $90$, en montrant d'abord qu'il existe un sous-ensemble de $S$ à $90$ éléments ne contenant aucune paire de nombres similaires, puis en montrant qu'un sous-ensemble de $S$ avec au moins $91$ éléments contient forcément deux nombres similaires.

  • Considérons le sous-ensemble $X$ de $S$ défini par
    $$X = \left\{\overline{abc} \ : \ \begin{align}&1 \le a \le 9\\ &0 \le b, c \le 9\\ & 10 \mid a+b+c\end{align} \right\}$$ où $\overline{abc}$ est le nombre ayant $a, b, c$ pour chiffres dans le système décimal.

    On a $|X| = 90$, puisque pour chaque chiffre $a \ne 0$ et chaque chiffre $b$, il y a exactement un chiffre $c$ tel que $a+b+c$ est multiple de $10$.

    Montrons maintenant que deux nombres différents dans $X$ ne sont jamais similaires. Supposons par l'absurde qu'il existe deux nombres différents similaires $\overline{abc}$ et $\overline{def}$ dans $X$. Cela signifie qu'exactement deux des trois égalités $a = d$, $b = e$ et $c = f$ sont vérifiées. Cela implique en particulier que
    $$a+b+c \ne d+e+f$$ et
    $$|(a+b+c) - (d+e+f)| \le 9,$$ ce qui est impossible car $a+b+c$ et $d+e+f$ sont tous les deux multiples de $10$ par définition de $X$.

  • Considérons un sous-ensemble $Y$ de $S$ avec $|Y| \ge 91$ et montrons qu'il contient forcément deux nombres similaires. Définissons les $90$ sous-ensembles $S_{10}, S_{11}, \ldots, S_{99}$ de $S$ par
    $$S_i = \left\{10\cdot i + j \mid 0 \le j \le 9 \right\} \text{ pour tout $i \in \{10, 11, \ldots, 99\}$}.$$ On a $S = S_{10} \cup S_{11} \cup \ldots \cup S_{99}$. Par le principe des tiroirs, il existe deux éléments de $Y$ se trouvant dans le même ensemble $S_i$. Ces deux nombres ont donc le même chiffre des centaines et le même chiffre des dizaines : ils sont similaires.