Exercices corrigés : rédiger une preuve mathématique (201-N11)

a) On reconnaît la preuve directe à ceci : l'hypothèse est RICHE, elle se traduit tout de suite en une égalité, et tout le reste est du calcul. Soient $n$ et $m$ deux entiers impairs. Par définition, il existe des entiers $k$ et $j$ tels que $n=2k+1$ et $m=2j+1$. Alors $n+m=(2k+1)+(2j+1)=2k+2j+2=2(k+j+1)$. Comme $k+j+1$ est un entier, $n+m$ s'écrit 2 fois un entier : il est pair. Supposé : $n$ et $m$ impairs. Établi : $n+m$ pair. Vérification sur un cas, $n=7$ et $m=11$ donnent $k=3$, $j=5$, $k+j+1=9$ et $n+m=18=2\times 9$. Le piège de rédaction, qui coûte la moitié des points sur une question de ce type : conclure « donc $n+m$ est pair » sans avoir exhibé le facteur 2. Une preuve directe n'est finie que lorsque la DÉFINITION de la conclusion est vérifiée mot pour mot, ici lorsque le nombre apparaît sous la forme 2 fois un entier. Écrire « la somme de deux impairs est évidemment paire » ne vaut aucun point : l'évidence n'est pas une structure de preuve, et le correcteur note la structure.

b) Même structure, hypothèse riche encore une fois. De $a \mid b$ on tire un entier $k$ tel que $b=ak$, et de $a \mid c$ un entier $l$ tel que $c=al$. Attention à la lettre : $k$ et $l$ n'ont aucune raison d'être égaux, et les confondre reviendrait à supposer $b=c$. Alors $bu+cv=aku+alv=a(ku+lv)$. Comme $ku+lv$ est un entier, on a bien $a \mid (bu+cv)$. Vérification : $a=7$, $b=21$, $c=35$, $u=2$ et $v=-1$ donnent $bu+cv=42-35=7=7\times 1$. Ce résultat porte un nom, le lemme de combinaison linéaire, et c'est lui qui fait fonctionner l'algorithme d'Euclide : tout diviseur commun de $b$ et de $c$ divise aussi le reste $b-qc$, qui est une combinaison linéaire de $b$ et de $c$. On s'en resservira à l'exercice 7. Retenez le geste : une hypothèse de divisibilité ne sert à rien tant qu'elle reste écrite avec la barre verticale, elle se traduit toujours en une égalité avec un entier nommé.

c) Il démontre trois cas particuliers, et rien de plus. L'énoncé est UNIVERSEL, il porte sur une infinité de couples, et aucune liste finie ne l'épuise. Trois exemples justes ne sont pas une preuve : ce sont des vérifications, et la vérification ne sert qu'à deux choses, se convaincre avant d'écrire et se rattraper quand on s'est trompé de signe. Le point à retenir est l'asymétrie complète entre démontrer et réfuter. Pour RÉFUTER un énoncé universel, un seul contre-exemple suffit et clôt le débat, c'est l'objet de l'exercice 5. Pour le DÉMONTRER, aucun nombre d'exemples ne suffit jamais. C'est exactement la différence entre tester un programme et le prouver : mille tests verts n'établissent pas qu'un programme est correct, ils établissent qu'il l'est sur mille entrées, et l'entrée qui le casse est justement celle à laquelle personne n'a pensé.

d) Parce que la même lettre force les deux nombres à être égaux. Écrire $n=2k+1$ et $m=2k+1$, c'est supposer $n=m$, donc ne traiter que les couples d'impairs ÉGAUX, du type $(7\,;7)$, alors que l'énoncé parle de deux impairs quelconques. Le calcul qui suit est juste, il donne $n+m=4k+2=2(2k+1)$, mais sa portée est fausse : il ne couvre pas le couple $(3\,;5)$. Un correcteur retire ici la quasi-totalité des points, non pour le calcul mais pour la portée. La règle de rédaction : une lettre fraîche pour chaque objet dont on ne sait rien, et deux objets distincts n'ont jamais droit à la même lettre tant qu'on n'a pas démontré qu'ils sont égaux. C'est la même faute que de nommer $i$ les deux compteurs de deux boucles imbriquées, et elle produit le même genre de dégât : le programme tourne, il calcule autre chose que ce qu'on croit.

e) Entre 1 et $10^{6}$ il y a $500\,000$ entiers impairs, donc $500\,000^{2}=2{,}5\times 10^{11}$ couples, soit 250 milliards de vérifications. À un milliard de tests par seconde, cela demande environ 250 secondes, un peu plus de quatre minutes. Et au bout de ces quatre minutes l'énoncé n'est toujours PAS démontré : on saura qu'il est vrai pour les impairs inférieurs à un million, et on ne saura rien pour $10^{6}+1$. La preuve de la question a) tient en trois lignes et couvre tous les entiers d'un coup, y compris ceux qui ne tiendront jamais dans une mémoire. C'est l'argument qui justifie, dans un cours de mathématiques pour l'informatique, d'apprendre à rédiger plutôt qu'à tester : la machine parcourt des cas, la preuve quantifie sur tous. Le corollaire pratique : quand un énoncé porte sur un ensemble infini, chercher une structure de preuve n'est pas un luxe de mathématicien, c'est la seule voie.

a) (1) $P \Rightarrow Q$ est l'énoncé de départ. (2) $Q \Rightarrow P$ est sa RÉCIPROQUE. (3) $\lnot Q \Rightarrow \lnot P$ est sa CONTRAPOSÉE. (4) $\lnot P \Rightarrow \lnot Q$ est la contraposée de la réciproque, donc l'équivalent de (2). En français : (2) dit « si $n$ est divisible par 3, alors $n$ est divisible par 6 », ce qui est FAUX, $n=9$ le réfute en une ligne. (3) dit « si $n$ n'est pas divisible par 3, alors $n$ n'est pas divisible par 6 », ce qui est vrai, et c'est d'ailleurs la forme sous laquelle on s'en sert : un nombre dont la somme des chiffres ne fait pas un multiple de 3 ne peut pas être un multiple de 6, sans aucun calcul de division. Le nom exact compte : sur une copie, écrire « contraposée » pour désigner $Q \Rightarrow P$ fait perdre les points de la question entière, même si le reste du raisonnement est correct, parce que la suite s'appuie alors sur un énoncé qui n'a pas la valeur de vérité annoncée.

b) Voir la table de la correction. Sur les quatre lignes, dans l'ordre $(P,Q)=(1,1),(1,0),(0,1),(0,0)$ : la colonne (1) vaut $1,0,1,1$ ; la colonne (3) vaut $1,0,1,1$ ; la colonne (2) vaut $1,1,0,1$. Les colonnes (1) et (3) sont identiques ligne pour ligne : un énoncé et sa contraposée sont la MÊME proposition, et c'est là ce qui autorise à démontrer l'un pour obtenir l'autre. La colonne (2) diffère des deux autres sur les lignes 2 et 3. Le calcul de la ligne 2 mérite d'être refait à la main : $P=1$, $Q=0$ donnent $\lnot Q=1$ et $\lnot P=0$, donc (3) vaut $1 \Rightarrow 0$, c'est-à-dire 0, comme (1). La table est le juge, et c'est la seule preuve d'équivalence qui vaille : aucune intuition tirée du français ne remplace la comparaison de deux colonnes.

c) Deux propositions donnent $2^{2}=4$ lignes. La réciproque diffère de l'énoncé sur DEUX de ces quatre lignes, soit la moitié exactement, ce qui est le meilleur argument contre la confusion : se tromper de forme, ce n'est pas commettre une petite imprécision, c'est avoir une chance sur deux de raisonner sur une proposition fausse. Plus généralement, une table à $n$ propositions compte $2^{n}$ lignes, donc 8 pour trois propositions et 32 pour cinq. Le point à retenir pour la suite du cours : quand une équivalence annoncée paraît douteuse, on ne discute pas, on écrit les quatre lignes, cela prend trente secondes et cela tranche.

d) La faute s'appelle affirmer la réciproque. L'étudiant a démontré $P \Rightarrow Q$ et il conclut $Q \Rightarrow P$, ce qui n'est jamais permis. Le plus petit contre-exemple entier positif est $x=2$ : il vérifie $x \geq 0$ et il n'est pas un carré parfait, puisque $1^{2}=1$ et $2^{2}=4$ l'encadrent strictement. Ce qu'il aurait eu le droit d'écrire est la contraposée : si $x<0$, alors $x$ n'est pas un carré parfait. Cette faute est la plus fréquente de tout le chapitre et elle ne se voit pas dans les calculs, elle se voit dans la phrase de conclusion, ce qui la rend redoutable en examen. Elle a un équivalent exact en informatique : de « si l'entrée est valide alors le test renvoie vrai », on ne peut rien conclure d'un test qui renvoie vrai, alors qu'un test qui renvoie faux garantit que l'entrée était invalide.

e) Il faudrait que (1) ET (2) soient toutes deux vraies, car une équivalence est la conjonction d'une implication et de sa réciproque. Ce n'est pas le cas ici, $n=9$ réfutant (2). Une équivalence vraie autour de la divisibilité par 6 existe pourtant : $n$ est divisible par 6 si et seulement si $n$ est divisible par 2 ET par 3. Le sens direct est immédiat, et le sens réciproque demande que 2 et 3 soient premiers entre eux, ce qui est le théorème de Gauss. La vérification numérique : 9 est divisible par 3 mais pas par 2, donc pas par 6 ; 4 est divisible par 2 mais pas par 3, donc pas par 6 ; 12 l'est par les deux, donc par 6. La leçon de rédaction : « si et seulement si » est une promesse de DEUX démonstrations, et une copie qui l'annonce sans en fournir deux perd les points du sens manquant.

a) La négation de « $n$ est impair » est « $n$ est pair », et c'est une hypothèse riche, elle s'écrit $n=2k$. La contraposée à démontrer est donc : si $n$ est pair, alors $3n+2$ est pair. Preuve : $n=2k$ donne $3n+2=6k+2=2(3k+1)$, qui est 2 fois un entier, donc pair. La contraposée étant équivalente à l'énoncé, l'énoncé est démontré. Vérification : $n=4$ donne $3n+2=14$, pair, conforme ; $n=5$ donne 17, impair, et 5 est bien impair. Comparons avec la voie directe : partir de « $3n+2$ est impair » donne $3n+2=2k+1$, donc $3n=2k-1$, et il faut alors argumenter que $3n$ impair force $n$ impair, ce qui est un deuxième énoncé du même type, non démontré. La voie directe tourne en rond, la contraposée tient en une ligne. Ce contraste est exactement le critère de choix.

b) La conclusion est un OU, et la négation d'un OU est un ET : « $x \leq 31$ ET $y \leq 31$ ». C'est là que tout se joue, car cette négation est riche, elle donne deux majorations utilisables, alors que la conclusion d'origine, un OU, ne se manipule pas. Contraposée à démontrer : si $x \leq 31$ et $y \leq 31$, alors $xy \leq 1\,000$. Preuve : $x$ et $y$ étant strictement positifs, $xy \leq 31 \times 31 = 961 \leq 1\,000$. Donc l'énoncé est vrai. La borne est fine : $31^{2}=961$ passe, et $32^{2}=1\,024$ dépasse bien 1 000, ce qui montre que le seuil 31 n'est pas choisi au hasard. Le piège, sanctionné à chaque examen : écrire la négation « $x \leq 31$ ou $y \leq 31$ ». Avec ce ou, le couple $(10\,;200)$ vérifie l'hypothèse et donne $xy=2\,000$, la preuve s'effondre et l'étudiant conclut à tort que l'énoncé est faux.

c) Négation de la conclusion : $n$ est impair, donc $n=2k+1$, hypothèse riche à nouveau. Contraposée : si $n$ est impair, alors $n^{3}+5$ est pair. Preuve : $n$ impair donne $n^{3}=n \times n \times n$ impair, car un produit d'impairs est impair, puis $n^{3}+5$ est la somme de deux impairs, donc pair d'après l'exercice 1. Vérification : $n=3$ donne $27+5=32$, pair. Si l'on veut tout expliciter, $n=2k+1$ donne $n^{3}=8k^{3}+12k^{2}+6k+1=2(4k^{3}+6k^{2}+3k)+1$, puis $n^{3}+5=2(4k^{3}+6k^{2}+3k+3)$. La voie directe, elle, exigerait de partir de « $n^{3}+5$ impair », donc de « $n^{3}$ pair », et de démontrer que le cube pair force $n$ pair, ce qui est encore un énoncé de la même famille : on serait reparti pour une contraposée, un cran plus loin.

d) Dans les trois cas, l'hypothèse de départ est PAUVRE : elle porte sur une expression composée ($3n+2$, $xy$, $n^{3}+5$) et non sur l'objet $n$ lui-même, si bien que la traduire en égalité ne donne rien d'exploitable. La conclusion, au contraire, porte directement sur $n$, ou se nie en un ET de deux majorations. Le critère de choix se formule donc ainsi : on compare la RICHESSE de $P$ et celle de $\lnot Q$, et on démontre en partant de la plus riche des deux. Trois signaux annoncent presque toujours une contraposée : la conclusion est une négation, la conclusion est un OU, ou la conclusion porte sur l'objet de base alors que l'hypothèse porte sur une expression construite à partir de lui.

e) Elles diffèrent par ce qu'on suppose et par ce qu'on cherche. Dans la contraposée, on suppose $\lnot Q$ SEULE, et on cherche à établir $\lnot P$ : rien de faux n'est jamais supposé, on démontre un énoncé équivalent à l'énoncé d'origine, et la preuve est aussi solide qu'une preuve directe. Dans l'absurde, on suppose $P$ ET $\lnot Q$, c'est-à-dire la négation complète de l'implication, et on cherche n'importe quelle contradiction, pas forcément $\lnot P$. L'absurde est donc plus permissif, et c'est à la fois sa force, il s'applique à des énoncés qui ne sont pas des implications, et sa faiblesse : on y raisonne sur un monde faux, où toute erreur de calcul produit une contradiction qui a l'air d'une conclusion. La règle d'usage : si la contraposée suffit, on la préfère, elle est plus courte et plus sûre ; l'absurde se réserve aux énoncés de non-existence, d'unicité et d'irrationalité, qui font l'objet de l'exercice 4.

a) On suppose $P$ ET $\lnot Q$, c'est-à-dire exactement la négation de l'implication, puisque $\lnot(P \Rightarrow Q)$ vaut $P \land \lnot Q$. On garde donc l'hypothèse de l'énoncé, ce qui est le point que les étudiants oublient : par l'absurde, on ne jette pas $P$, on l'ajoute à $\lnot Q$ et on dispose ainsi de DEUX hypothèses au lieu d'une, ce qui explique que l'absurde réussisse là où la contraposée, qui ne dispose que de $\lnot Q$, échoue parfois. Ensuite on cherche une contradiction quelconque : un nombre à la fois pair et impair, une fraction irréductible dont les deux termes sont pairs, un entier strictement compris entre deux entiers consécutifs. La rédaction obligatoire comporte trois marques : l'annonce « supposons par l'absurde que », la contradiction explicitement nommée quand elle arrive, et la conclusion qui reprend l'énoncé de départ. Une copie qui trouve la contradiction et s'arrête là perd les points de conclusion.

b) Supposons par l'absurde que $\sqrt{2}$ soit rationnel. Il s'écrit alors $\sqrt{2}=\frac{a}{b}$ avec $a$ et $b$ entiers, $b$ non nul, et la fraction choisie IRRÉDUCTIBLE, ce qui est toujours possible en simplifiant. En élevant au carré, $2=\frac{a^{2}}{b^{2}}$, donc $a^{2}=2b^{2}$ : $a^{2}$ est pair, donc $a$ est pair d'après la contraposée de l'exercice 3, et l'on écrit $a=2c$. Alors $4c^{2}=2b^{2}$, donc $b^{2}=2c^{2}$, donc $b$ est pair pour la même raison. L'hypothèse contredite est précisément l'IRRÉDUCTIBILITÉ : $a$ et $b$ sont tous deux pairs, donc divisibles par 2, alors qu'on les avait supposés sans facteur commun. Donc $\sqrt{2}$ est irrationnel. Le piège classique consiste à oublier de poser la fraction irréductible : sans cette précaution, obtenir « $a$ et $b$ pairs » n'est pas une contradiction du tout, c'est une information banale, et la preuve ne prouve rien. Vérification du bon ordre de grandeur : $\sqrt{2}\approx 1{,}41421$, et $\frac{99}{70}\approx 1{,}414286$ en est une excellente approximation, mais seulement une approximation.

c) Supposons par l'absurde $\log_{2} 3=\frac{a}{b}$ avec $a$ et $b$ entiers strictement positifs, ce qui est licite car $\log_{2} 3>1>0$. Par définition du logarithme en base 2, $2^{a/b}=3$, donc en élevant à la puissance $b$ : $2^{a}=3^{b}$. Le membre de gauche est pair, puisque $a \geq 1$ ; le membre de droite est impair, puisque 3 est impair et qu'un produit d'impairs est impair. Un entier ne peut être à la fois pair et impair : contradiction. Donc $\log_{2} 3$ est irrationnel. Sa valeur est $\log_{2} 3 \approx 1{,}58$, et c'est le nombre moyen de bits nécessaires pour coder un symbole pris dans un alphabet de trois lettres équiprobables. L'irrationalité dit alors quelque chose de concret : aucun codage à longueur fixe de $b$ symboles sur $a$ bits ne peut être exactement optimal, quel que soit le regroupement choisi, on s'en approche sans jamais y arriver. Le piège de rédaction : oublier la condition $a \geq 1$, sans laquelle $2^{a}$ pourrait valoir 1, qui est impair, et la contradiction disparaît.

d) R2 est la seule valide. R1 commet une faute de fond : rien ne garantit que $N$ soit premier, et l'exemple donné le prouve, $2\times 3\times 5\times 7\times 11\times 13+1=30\,031=59\times 509$ n'est pas premier. Ce que la preuve obtient est plus modeste et suffisant : $N$ admet un diviseur premier, et ce diviseur échappe à la liste. Dans l'exemple, 59 et 509 sont bien deux premiers absents de la liste 2, 3, 5, 7, 11, 13. R3 n'est pas une preuve du tout, c'est une affirmation : l'infinité des entiers n'entraîne pas celle d'un sous-ensemble, il y a une infinité d'entiers et pourtant un seul entier pair premier. La leçon de relecture : dans une preuve par l'absurde, la contradiction doit être EXHIBÉE, pas annoncée, et chaque étape qui affirme une existence doit dire de quel théorème elle la tient, ici le fait que tout entier supérieur à 1 admet un diviseur premier.

e) Non, et c'est même sa principale supériorité sur la contraposée, qui exige une implication. Aucun des énoncés b), c) et d) n'est une implication : « $\sqrt{2}$ est irrationnel » est une négation, « il existe une infinité de nombres premiers » est une affirmation d'existence. L'absurde s'applique à tout énoncé $A$, puisqu'il ne demande que de savoir écrire $\lnot A$. C'est pourquoi on le reconnaît à des mots-clés dans l'énoncé : il n'existe pas, aucun, au plus un, est unique, est irrationnel, est impossible. Tous désignent une proposition dont la négation est une EXISTENCE, donc une hypothèse riche : supposer qu'il existe un objet permet de le nommer et de calculer avec lui, alors que l'énoncé d'origine, qui nie, ne donne rien à manipuler. C'est le même critère qu'à l'exercice 3, appliqué à un énoncé qui n'est pas une implication.

a) Tout entier est pair ou impair : ce sont deux cas, et ils épuisent les entiers. Cas 1, $n=2k$ : alors $n^{2}=4k^{2}$, donc $n^{2} \equiv 0 \pmod 4$. Cas 2, $n=2k+1$ : alors $n^{2}=4k^{2}+4k+1=4(k^{2}+k)+1$, donc $n^{2} \equiv 1 \pmod 4$. Dans les deux cas le reste vaut 0 ou 1, il ne vaut JAMAIS 3. Conséquence immédiate, par contraposée : un entier de la forme $4k+3$, dont le reste modulo 4 est 3, ne peut pas être un carré parfait. Vérification : $7=4\times 1+3$, et $2^{2}=4$, $3^{2}=9$ l'encadrent ; $11=4\times 2+3$, encadré par 9 et 16 ; $15=4\times 3+3$, encadré par 9 et 16. Ce résultat est l'outil standard pour montrer qu'une équation n'a pas de solution entière : on regarde les restes possibles de chaque membre, et si les deux ensembles ne se rencontrent pas, l'équation est impossible. La disjonction de cas est ici le moteur, et le nombre de cas est fixé par le modulo choisi.

b) La liste doit être EXHAUSTIVE : la réunion des cas doit redonner le domaine $D$ tout entier, sans quoi l'énoncé reste non démontré sur ce qui manque. C'est la faute la plus fréquente, et elle passe inaperçue parce que chaque cas, pris isolément, est correct. En revanche, les cas n'ont aucun besoin d'être deux à deux disjoints : un chevauchement ne coûte rien, il fait seulement démontrer deux fois la même chose sur l'intersection. On peut donc traiter « $x \leq 0$ » puis « $x \geq 0$ » sans se soucier du zéro compté deux fois, alors que traiter « $x<0$ » puis « $x>0$ » laisse un trou et ruine la preuve. Sur une copie, la phrase qui rapporte les points est celle qui vérifie l'exhaustivité à haute voix, du type « tout entier est pair ou impair, les deux cas ci-dessus couvrent donc tous les entiers ».

c) Posons $x=\sqrt{2}^{\sqrt{2}}$ et discutons deux cas, qui épuisent les possibilités. Cas 1, $x$ est rationnel : alors le couple $a=b=\sqrt{2}$ convient, puisque $\sqrt{2}$ est irrationnel d'après l'exercice 4. Cas 2, $x$ est irrationnel : alors prenons $a=x$ et $b=\sqrt{2}$, tous deux irrationnels ; on calcule $a^{b}=\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}=\sqrt{2}^{\,\sqrt{2}\times\sqrt{2}}=\sqrt{2}^{2}=2$, qui est rationnel. Dans les deux cas un couple convient, donc un tel couple existe. Ce que la preuve ne dit PAS : LEQUEL des deux couples convient, car elle ne tranche pas si $x$ est rationnel. C'est une preuve d'existence NON CONSTRUCTIVE, et c'est exactement le profil des tiroirs de l'exercice 6, qui garantissent qu'un tiroir contient deux objets sans jamais dire lequel. Retenez cette parenté : la disjonction de cas non tranchée et les tiroirs sont les deux façons de démontrer une existence sans l'exhiber.

d) Un seul contre-exemple suffit, et il est fourni : $F_{5}=4\,294\,967\,297=641\times 6\,700\,417$ n'est pas premier, donc l'affirmation « tout nombre de Fermat est premier » est fausse. Fermat avait vérifié CINQ cas, $F_{0}=3$, $F_{1}=5$, $F_{2}=17$, $F_{3}=257$ et $F_{4}=65\,537$, tous premiers, et il a conjecturé le reste. Euler a trouvé le facteur 641 en 1732, quatre-vingts ans plus tard. L'histoire est le meilleur argument contre l'induction sauvage : cinq cas justes d'affilée, sur des nombres qui grandissent très vite, ne garantissent rien. Rédaction attendue pour une réfutation : on donne la valeur, on vérifie qu'elle satisfait l'hypothèse, on vérifie qu'elle viole la conclusion, et on conclut que l'énoncé universel est faux. Trois lignes, et aucune autre technique n'est nécessaire : c'est le seul cas où une valeur numérique constitue à elle seule une démonstration complète.

e) Modulo 3, il y a TROIS cas, les restes 0, 1 et 2, et modulo $n$ il y en a $n$, les restes 0 à $n-1$ : c'est exactement le théorème de la division euclidienne qui garantit l'exhaustivité, tout entier ayant un reste et un seul. La coupure « pair ou impair » est le cas $n=2$, donc elle est toujours licite, et c'est d'ailleurs pour cela qu'on l'emploie sans la justifier. Le choix du modulo est une décision de stratégie, pas de goût : on prend le plus petit qui sépare ce qu'on veut séparer. Pour la question a), modulo 4 suffit et donne deux valeurs de reste seulement, alors que modulo 8 en donnerait trois pour un résultat à peine plus fin. La règle pratique : plus le modulo est grand, plus l'information est précise, et plus la rédaction est longue ; on s'arrête au premier qui conclut.

a) Forme simple : si l'on range $n+1$ objets dans $n$ tiroirs, alors au moins un tiroir contient au moins deux objets. Démonstration par l'absurde, et c'est le premier intérêt de la question : supposons qu'aucun tiroir ne contienne deux objets, c'est-à-dire que chaque tiroir en contienne au plus un. Alors le nombre total d'objets est au plus $1+1+\cdots+1=n$, la somme portant sur les $n$ tiroirs. Or ce total vaut $n+1$, et $n+1>n$ : contradiction. Donc un tiroir au moins contient deux objets. Retenez la structure, elle est le squelette de toutes les questions suivantes : on nie la conclusion, la négation impose une MAJORATION de chaque tiroir, on somme ces majorations et on tombe sur un total trop petit. Le principe ne dit rien d'autre, et surtout il ne dit pas QUEL tiroir : c'est une existence non constructive, exactement comme la disjonction non tranchée de l'exercice 5.

b) Forme généralisée : si l'on range $m$ objets dans $n$ tiroirs, alors un tiroir au moins contient au moins $\lceil m/n \rceil$ objets, où $\lceil \cdot \rceil$ désigne la partie entière supérieure. Même démonstration : si tous les tiroirs contenaient au plus $\lceil m/n \rceil - 1$ objets, le total serait au plus $n\left(\lceil m/n \rceil - 1\right)$, qui est strictement inférieur à $m$ puisque $\lceil m/n \rceil < \frac{m}{n}+1$. Contradiction. Application : $\lceil 2\,000/30 \rceil = \lceil 66{,}67 \rceil = 67$, donc un dossier au moins contient 67 fichiers ou plus. Le piège, qui coûte un point à chaque fois : écrire 66, c'est-à-dire prendre la partie entière INFÉRIEURE, ou pire la moyenne $66{,}67$, qui n'est le nombre de fichiers d'aucun dossier. La borne est fine, au sens où une répartition existe avec un dossier à 67 et les autres à 66 ou 67 : on ne peut rien affirmer de plus fort.

c) Les objets sont les trames et les tiroirs sont les codes possibles. Un code de 16 bits prend $2^{16}=65\,536$ valeurs, alors que les trames de 1 000 bits sont au nombre de $2^{1000}$, un nombre astronomiquement plus grand. Comme $2^{1000}>2^{16}$, le principe des tiroirs s'applique : deux trames distinctes au moins portent le même code. Pour la garantie, il suffit de $65\,537$ trames distinctes, soit $2^{16}+1$ : c'est le plus petit nombre qui force la collision, et avec $65\,536$ trames rien n'est forcé, puisqu'une bijection reste concevable. La conséquence pratique est le point à retenir : un code de contrôle ne prouve JAMAIS qu'une trame est intacte, il rend seulement improbable qu'une erreur passe inaperçue. Aucun choix de fonction de contrôle ne change cela, c'est un résultat de comptage, pas de qualité d'algorithme.

d) Les objets sont les sous-ensembles non vides des 10 entiers choisis : il y en a $2^{10}-1=1\,023$. Les tiroirs sont les sommes possibles. La plus petite somme vaut au moins 1, et la plus grande est obtenue avec les dix plus grands entiers disponibles, $91+92+\cdots+100=955$. Il y a donc au plus 955 sommes possibles pour $1\,023$ sous-ensembles : deux sous-ensembles distincts ont la même somme. Si ces deux sous-ensembles se chevauchent, on retire leur intersection des deux, ce qui enlève la même quantité de part et d'autre, et l'on obtient deux sous-ensembles DISJOINTS de même somme, tous deux non vides puisque les sommes étaient égales et les ensembles distincts. La force du résultat tient à ce qu'il vaut pour N'IMPORTE QUEL choix de dix entiers : impossible de tricher en les choisissant bien, alors qu'aucun exemple ne le rendrait évident.

e) Il faut 367 étudiants : les tiroirs sont les 366 dates possibles, 29 février compris, et $366+1=367$ objets forcent la coïncidence. Les deux résultats ne se contredisent pas du tout, ils ne répondent pas à la même question. Les tiroirs donnent une CERTITUDE dans le pire des cas : à 367, aucun arrangement n'évite la coïncidence. Le calcul de probabilité, lui, dit qu'à 23 personnes la coïncidence a déjà plus d'une chance sur deux de se produire, ce qui est une affirmation sur la FRÉQUENCE et laisse parfaitement possible un groupe de 300 personnes aux dates toutes distinctes. Garder les deux registres séparés est l'un des réflexes les plus utiles du cours : forcé et probable sont deux mots différents, et confondre les deux fait écrire des phrases fausses sur la sécurité informatique.

a) Les énoncés (i) et (iii) appellent une récurrence, et eux seuls. Le signal est double : l'énoncé est INDEXÉ par un entier $n$, et le passage du rang $n$ au rang $n+1$ se fait par un petit calcul, ici ajouter $n+1$ à la somme, là factoriser $7^{n+1}-1=7(7^{n}-1)+6$. L'énoncé (ii) est une irrationalité, donc un absurde, et rien n'y est indexé par un entier. L'énoncé (iv) est une affirmation d'existence sans construction : c'est un cas de tiroirs, 13 objets pour 12 restes possibles. L'énoncé (v) est une implication dont la conclusion se nie facilement : c'est une contraposée, si $n$ est impair alors $n^{2}$ est impair, donc non divisible par 4. Ce tri est le geste central du chapitre, et il se fait en lisant la FORME de l'énoncé, jamais son sujet : trois de ces cinq énoncés parlent d'entiers, et ils demandent trois structures différentes.

b) Structure 1, la récurrence : au rang 1, $1=1^{2}$ ; en supposant $1+3+\cdots+(2n-1)=n^{2}$, on ajoute le terme suivant $2n+1$ et l'on obtient $n^{2}+2n+1=(n+1)^{2}$, ce qui est l'énoncé au rang $n+1$. Structure 2, la preuve directe par regroupement : la somme des $n$ premiers impairs vaut $\sum_{k=1}^{n}(2k-1)=2\times\frac{n(n+1)}{2}-n=n^{2}+n-n=n^{2}$. La seconde se rédige en une ligne, à condition de connaître la somme des premiers entiers. Vérification pour $n=6$ : $1+3+5+7+9+11=36=6^{2}$. La leçon est celle du fil : la récurrence n'est pas obligatoire dès qu'un énoncé porte sur tous les entiers, elle est un choix parmi d'autres, et elle est souvent le plus long des deux chemins. On la garde pour les énoncés dont le rang $n+1$ ne se calcule QUE par le rang $n$, typiquement les suites définies par récurrence, traitées dans le chapitre qui leur est consacré.

c) Le reste $r=a \bmod b$ vérifie $0 \leq r < b$ : il est un entier naturel et il est STRICTEMENT inférieur au $b$ précédent. La suite des restes successifs est donc une suite d'entiers naturels strictement décroissante. Or une telle suite ne peut pas être infinie : l'ensemble de ses valeurs serait une partie non vide de $\mathbb{N}$ sans plus petit élément, ce qui contredit le bon ordre. L'algorithme s'arrête donc après un nombre fini d'étapes. Déroulement : $1\,071=2\times 462+147$, puis $462=3\times 147+21$, puis $147=7\times 21+0$. Trois divisions, et le dernier reste non nul, 21, est le PGCD. Vérification : $1\,071=21\times 51$ et $462=21\times 22$, et $51$ et $22$ sont premiers entre eux. La quantité qui décroît porte un nom, le variant, et l'exhiber est toute la preuve de terminaison : c'est ce qu'on demande sur une copie, pas une phrase du type « on voit bien que cela finit ».

d) Non, et c'est précisément là que se joue la différence entre $\mathbb{N}$ et $\mathbb{Q}$. La suite $\frac{1}{2^{n}}$ est strictement décroissante, strictement positive, et pourtant infinie : elle ne s'arrête jamais. L'argument de terminaison ne repose donc pas sur la décroissance, il repose sur le fait que le variant vit dans $\mathbb{N}$, où il n'y a pas de place pour une descente infinie. Conséquence pratique en programmation : pour prouver qu'une boucle termine, on exhibe une quantité ENTIÈRE, positive, qui décroît strictement à chaque tour. Une quantité réelle qui décroît ne prouve rien, et c'est la source d'une famille classique de boucles qui tournent indéfiniment, celles qui attendent qu'un flottant atteigne exactement zéro.

e) Elle se cache dans la phrase « on peut toujours choisir la fraction irréductible ». Cette phrase est une conséquence du bon ordre : parmi toutes les écritures $\frac{a}{b}$ du même nombre avec $b>0$, il en existe une dont le dénominateur est le PLUS PETIT, et c'est celle-là qu'on prend. On peut d'ailleurs rédiger la preuve sans jamais parler d'irréductibilité, c'est la descente infinie : si $\sqrt{2}=\frac{a}{b}$, on fabrique $\frac{c}{d}$ avec $d<b$ représentant le même nombre, puis on recommence, et l'on obtient une suite infinie strictement décroissante d'entiers naturels, ce que le bon ordre interdit. Récurrence, bon ordre et descente infinie sont trois formulations du même principe, et savoir passer de l'une à l'autre est ce qui permet de reconnaître une récurrence déguisée dans un énoncé qui n'en a pas l'air.

1) FAUX, et c'est la confusion la plus coûteuse du chapitre. La contraposée de $P \Rightarrow Q$ est $\lnot Q \Rightarrow \lnot P$ ; sa réciproque est $Q \Rightarrow P$. La première a TOUJOURS la même valeur de vérité que l'énoncé, la seconde n'a aucun lien avec lui : sur les quatre lignes de la table de vérité de l'exercice 2, la réciproque diffère de l'énoncé sur deux lignes, soit une sur deux. Exemple qui tranche : « si $n$ est divisible par 6 alors $n$ est divisible par 3 » est vraie, sa contraposée « si $n$ n'est pas divisible par 3 alors $n$ n'est pas divisible par 6 » est vraie aussi, et sa réciproque « si $n$ est divisible par 3 alors $n$ est divisible par 6 » est fausse, $n=9$ le montre. Énoncé correct : la contraposée d'un énoncé lui est équivalente, sa réciproque est une proposition indépendante qui demande sa propre démonstration.

2) FAUX, et aucun choix d'exemple n'y change rien. Un énoncé universel porte sur une infinité de cas, et une liste finie n'en épuise jamais l'ensemble. L'histoire des nombres de Fermat de l'exercice 5 le montre crûment : cinq cas vérifiés, $F_{0}$ à $F_{4}$, tous premiers, et le sixième, $F_{5}=4\,294\,967\,297=641\times 6\,700\,417$, est composé. L'asymétrie est totale entre les deux sens : pour RÉFUTER un énoncé universel, un seul contre-exemple suffit et clôt la question ; pour le DÉMONTRER, il faut une structure valable pour tous les cas d'un coup. Énoncé correct : un exemple illustre, il ne démontre pas, sauf pour un énoncé d'EXISTENCE, où exhiber un objet est effectivement une preuve complète.

3) FAUX, même s'ils commencent tous deux par supposer la conclusion fausse. La contraposée suppose $\lnot Q$ SEULE et vise exactement $\lnot P$ : rien de faux n'est supposé, et elle ne s'applique qu'aux implications. L'absurde suppose $P$ ET $\lnot Q$, donc la négation complète de l'implication, et vise n'importe quelle contradiction ; il s'applique à tout énoncé, y compris à ceux qui ne sont pas des implications, comme l'irrationalité de $\sqrt{2}$ ou l'infinité des nombres premiers. Énoncé correct : la contraposée est un cas particulier très discipliné, l'absurde est plus général et plus dangereux, puisqu'on y raisonne dans un monde faux où la moindre erreur de calcul produit une contradiction qui ressemble à une conclusion.

4) FAUX : la récurrence ne démontre PAS le cas initial, elle l'EXIGE. Ses deux étapes sont l'initialisation, où l'on vérifie la propriété au premier rang, et l'hérédité, où l'on démontre que le rang $n$ entraîne le rang $n+1$. L'hérédité seule ne démontre rien : la propriété « $n=n+1$ » est héréditaire, puisque de $n=n+1$ on tire $n+1=n+2$, et elle est fausse à tous les rangs, faute d'initialisation. Réciproquement, une initialisation seule ne démontre qu'un cas. Énoncé correct : la récurrence démontre l'énoncé à tous les rangs à partir du cas initial vérifié, et ce cas initial doit être établi séparément. Le chapitre consacré à la récurrence dans ce cours détaille les deux pièges, avec la récurrence forte et les suites récurrentes.

5) FAUX, et c'est justement ce que le principe NE dit pas. Les tiroirs garantissent l'EXISTENCE d'un tiroir chargé, sans jamais désigner lequel ni exhiber les deux objets : c'est une preuve d'existence non constructive, du même type que la disjonction non tranchée de l'exercice 5. Dans la question du code de contrôle, on sait que deux trames de 1 000 bits partagent un code de 16 bits, et cette certitude ne fournit aucun moyen d'en trouver une paire. C'est la raison pour laquelle la sécurité informatique repose sur la DIFFICULTÉ d'exhiber une collision et non sur son absence, qui est impossible. Énoncé correct : le principe des tiroirs affirme qu'un tiroir contient au moins deux objets, et il ne donne ni le tiroir ni les objets.

a) Chaque bit prend deux valeurs et les choix sont indépendants, donc il y a $2^{10}=1\,024$ suites de 10 bits. C'est le principe multiplicatif, et c'est le seul calcul de dénombrement de tout le problème.

b) Il y a $2^{0}=1$ suite de longueur 0, la suite vide, puis $2^{1}=2$ suites de longueur 1, et ainsi de suite jusqu'à $2^{9}=512$ suites de longueur 9. Le total est $1+2+4+\cdots+512=2^{10}-1=1\,023$, par la somme des termes d'une suite géométrique de raison 2. Ce nombre mérite d'être regardé : toutes les suites plus courtes que 10 bits, TOUTES longueurs confondues, sont moins nombreuses que les seules suites de 10 bits. C'est cette inégalité d'une unité qui va tout faire, et elle n'est pas un accident de l'exemple : $2^{0}+\cdots+2^{n-1}=2^{n}-1$ pour tout $n$.

c) « Sans perte » signifie que la décompression retrouve le fichier de départ, donc que deux fichiers DIFFÉRENTS ne peuvent pas donner la même version compressée : sinon le décompresseur, devant cette version compressée, ne saurait pas lequel des deux rendre. L'application qui envoie un fichier sur sa version compressée est donc INJECTIVE. C'est toute la traduction du problème, et c'est l'étape que les étudiants sautent : le mot « injective » n'apparaît pas dans l'énoncé de l'entreprise, il doit être produit par la lecture. Sans lui, le comptage des questions a) et b) ne sert à rien.

d) Supposons par l'absurde que le compresseur annoncé existe. Il envoie chacune des $1\,024$ suites de 10 bits sur une suite strictement plus courte, donc de longueur comprise entre 0 et 9, et il y en a $1\,023$. On range $1\,024$ objets dans $1\,023$ tiroirs : par le principe des tiroirs, deux suites distinctes de 10 bits reçoivent la même version compressée. Cela contredit l'injectivité établie en c), donc le compresseur annoncé n'existe pas. Les structures employées sont donc DEUX, emboîtées : un raisonnement par l'absurde dont la contradiction est produite par le principe des tiroirs, le tout reposant sur un dénombrement. C'est le schéma le plus fréquent des preuves d'impossibilité en informatique, et il vaut la peine de le retenir tel quel : on suppose l'objet, on compte ce qu'il devrait distinguer, on constate qu'il y a plus d'objets que de places.

e) Si un tel compresseur existait, l'appliquer $n$ fois réduirait tout fichier de 10 bits à une longueur d'au plus $10-n$ bits, donc au bout de dix applications à 0 bit, la suite vide. Tous les fichiers seraient devenus le même, et aucune décompression ne pourrait les distinguer : c'est la même contradiction, sous une forme plus spectaculaire. Les compresseurs réels fonctionnent parce qu'ils ne prétendent PAS réduire tous les fichiers : ils réduisent ceux qui portent de la structure, texte, image, journal de serveur, et ils AGRANDISSENT les autres de quelques bits, ce que l'on constate en compressant un fichier déjà compressé ou une suite de bits aléatoires. Le théorème ne dit donc pas que la compression est inutile, il dit qu'elle est un échange : ce qui est gagné sur les fichiers fréquents est perdu sur les fichiers rares, et le gain moyen dépend entièrement de la distribution réelle des fichiers, jamais du seul algorithme.

a) Un chiffre hexadécimal prend 16 valeurs, donc trois chiffres donnent $16^{3}=4\,096$ identifiants distincts. La répétition devient certaine dès $4\,097$ sessions, par la forme simple du principe des tiroirs. Avec $5\,000$ sessions, la forme généralisée donne mieux : un identifiant au moins est porté par $\lceil 5\,000/4\,096 \rceil = 2$ sessions. Ce 2 est bien la partie entière supérieure de $1{,}22$, et non 1 : voilà pourquoi l'arrondi ne se fait jamais au plus proche dans ce genre de question. On notera que la conclusion est faible en apparence, deux sessions seulement, alors que le calcul de probabilité, lui, prédirait un très grand nombre de collisions ; mais elle a une qualité que la probabilité n'a pas, elle est CERTAINE.

b) R4 est la seule valide. R1 est CIRCULAIRE : elle commence par supposer ce qu'elle veut démontrer, « comme deux sessions ont le même identifiant », et la conclusion n'est donc appuyée sur rien. C'est la faute la plus difficile à repérer en se relisant, parce que le texte se lit très bien. R2 raisonne PAR L'EXEMPLE : une simulation exhibe un cas, et un cas ne démontre pas un énoncé qui porte sur toute journée possible ; au demeurant, si la simulation n'avait rien trouvé, cela n'aurait rien réfuté non plus. R3 démontre la RÉCIPROQUE : l'implication qu'elle établit va de la collision vers le comptage, alors qu'il faudrait aller du comptage vers la collision, et la phrase « c'est bien le cas ici » applique ensuite l'implication à l'envers, ce qui est la faute d'affirmer la conclusion de l'exercice 2. Trois fautes de STRUCTURE, aucune faute de calcul : c'est le résumé du chapitre.

c) Rédaction attendue. Premier élément, ce dont on part : les identifiants sont écrits sur 3 chiffres hexadécimaux, il y en a donc $16^{3}=4\,096$, et le serveur a servi $5\,000$ sessions. Deuxième élément, la technique nommée : on applique le principe des tiroirs, les objets étant les sessions et les tiroirs les identifiants possibles. Troisième élément, l'enchaînement : comme $5\,000>4\,096$, il y a strictement plus d'objets que de tiroirs, donc un tiroir au moins contient deux objets. Quatrième élément, la conclusion qui reprend l'énoncé : deux sessions au moins ont reçu le même identifiant. Quatre phrases, et chacune vaut des points. Ce qui ne compte PAS comme une preuve rédigée : une suite de calculs justes sans la phrase qui nomme la technique, et une conclusion qui s'arrête à « donc collision » sans revenir aux sessions de l'énoncé.

d) Non, cela ne supprime pas le risque, cela supprime seulement la CERTITUDE. Avec 4 chiffres hexadécimaux il y a $16^{4}=65\,536$ identifiants pour $5\,000$ sessions, donc plus de tiroirs que d'objets et le principe ne s'applique plus : il ne conclut rien. Mais ne rien conclure n'est pas conclure qu'il n'y a pas de collision. Les identifiants étant tirés au hasard, une collision reste possible, et le calcul du paradoxe des anniversaires, traité dans la série de dénombrement et probabilités du cours, montre même qu'elle est probable bien avant d'atteindre le nombre d'identifiants. C'est l'erreur de lecture la plus courante sur les tiroirs : le principe donne une condition SUFFISANTE de collision, jamais une condition nécessaire, et sa négation ne dit rien.

e) Il faudrait cesser de tirer au hasard et attribuer les identifiants par un COMPTEUR qui s'incrémente, ou par tout procédé qui n'attribue jamais deux fois la même valeur. La structure de preuve changerait alors du tout au tout : on ne compterait plus, on démontrerait que l'application session vers identifiant est injective, ce qui se fait par une preuve directe, ou par contraposée sous la forme « si deux sessions ont le même identifiant, alors elles ont le même numéro de compteur, donc elles sont la même session ». On y gagnerait la garantie, on y perdrait l'imprévisibilité, qui est justement ce qu'on cherche pour un identifiant de session : un compteur se devine, et deviner l'identifiant d'un autre visiteur est une faille. La vraie réponse d'ingénierie est donc d'allonger l'identifiant jusqu'à rendre la collision négligeable, en assumant qu'elle reste possible, ce qui est exactement ce que le chapitre apprend à dire correctement.