Processing

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,…,999} ne contenant aucune paire de nombres similaires ?

Solution 1 (mauvaise)
Prenons les 90 nombres 100,111,122,…,199,201,212,…,290,…,908,919,…,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 ¯abc avec c=a+b−1 (ou a+b−11 si a+b≥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 ¯abc avec c=a+b−1 (ou a+b−11 si a+b≥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 ¯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è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={¯abc : 1≤a≤90≤b,c≤910∣a+b+c} où ¯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≠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 ¯abc et ¯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≠d+e+f et
    |(a+b+c)−(d+e+f)|≤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|≥91 et montrons qu'il contient forcément deux nombres similaires. Définissons les 90 sous-ensembles S10,S11,…,S99 de S par
    Si={10⋅i+j∣0≤j≤9} pour tout i∈{10,11,…,99}. On a S=S10∪S11∪…∪S99. Par le principe des tiroirs, il existe deux éléments de Y se trouvant dans le même ensemble Si. Ces deux nombres ont donc le même chiffre des centaines et le même chiffre des dizaines : ils sont similaires.