Il n'existe pas de plus grand nombre pair

Démontre qu'il n'existe pas de plus grand nombre pair.

Écris la négation en première ligne: Supposons par l'absurde qu'il existe un plus grand nombre pair $N$ = Hypothèse : $N$ est pair et $N \ge$ tout nombre pair

Utilise la définition de pair: $N = 2k$ pour un entier $k$, donc $N + 2 = 2k + 2 = 2(k + 1)$ = $N + 2$ est pair

Compare les deux nombres: $N + 2 > N$ = Il existe un nombre pair plus grand que $N$

Repère la contradiction et conclus: $N$ est le plus grand nombre pair, pourtant $N + 2$ est un nombre pair plus grand = L'hypothèse est fausse

Answer: L'hypothèse mène à une contradiction, donc il n'existe pas de plus grand nombre pair. CQFD

Deux personnes sur 13 sont nées le même mois

Démontre que dans tout groupe de 13 personnes, au moins deux sont nées le même mois.

Écris la négation: Supposons par l'absurde que les 13 personnes sont toutes nées des mois différents = Hypothèse : 13 mois différents

Compte ce que l'hypothèse exige: 13 personnes sans mois répété exigent au moins 13 mois différents = Il faut au moins $13$ mois

Compare avec les faits: Une année n'a que $12$ mois, et $13 > 12$ = Impossible

Conclus: L'hypothèse est fausse = Deux personnes partagent un mois

Answer: Au moins deux des 13 personnes sont nées le même mois. C'est le principe des tiroirs : 13 personnes, 12 tiroirs (les mois). CQFD

Il n'existe pas de plus petit rationnel strictement positif

Démontre qu'il n'existe pas de plus petit nombre rationnel strictement positif.

Écris la négation: Supposons par l'absurde que $r$ est le plus petit nombre rationnel strictement positif = Hypothèse : $r > 0$, $r$ rationnel, rien de plus petit

Construis un nouveau nombre: Si $r = \frac{a}{b}$, alors $\frac{r}{2} = \frac{a}{2b}$ est un quotient d'entiers = $\frac{r}{2}$ est rationnel

Vérifie sa taille: $r > 0$, donc $0 < \frac{r}{2} < r$ = $\frac{r}{2}$ est positif et plus petit que $r$

Repère la contradiction et conclus: $r$ était le plus petit, pourtant $\frac{r}{2}$ est plus petit = L'hypothèse est fausse

Answer: Il n'existe pas de plus petit nombre rationnel strictement positif. Par exemple, si quelqu'un propose $\frac{1}{1000}$, alors $\frac{1}{2000}$ est plus petit. CQFD

Racine de 2 est irrationnelle

Démontre que $\sqrt{2}$ est irrationnel.

Écris la négation: Supposons par l'absurde que $\sqrt{2}$ est rationnel : $\sqrt{2} = \frac{a}{b}$ avec $a, b$ entiers, $b \neq 0$, et la fraction irréductible = $a$ et $b$ n'ont aucun diviseur commun

Élève les deux membres au carré: $2 = \frac{a^2}{b^2}$, donc $a^2 = 2b^2$ = $a^2$ est pair

Déduis que a est pair: Si $a$ était impair, $a^2$ serait impair (démontré dans la leçon sur la démonstration directe) = $a = 2k$ pour un entier $k$

Remplace: $(2k)^2 = 2b^2$, donc $4k^2 = 2b^2$, donc $b^2 = 2k^2$ = $b^2$ est pair, donc $b$ est pair

Repère la contradiction: $a$ et $b$ sont tous deux pairs, donc tous deux divisibles par $2$ = Cela contredit "irréductible"

Answer: L'hypothèse "$\sqrt{2}$ est rationnel" mène à une contradiction, donc $\sqrt{2}$ est irrationnel. CQFD

Il existe une infinité de nombres premiers (Euclide)

Démontre qu'il existe une infinité de nombres premiers.

Écris la négation: Supposons par l'absurde qu'il n'y a qu'un nombre fini de nombres premiers : $p_1, p_2, \ldots, p_n$ = La liste contient tous les nombres premiers

Construis un nouveau nombre: $N = p_1 \cdot p_2 \cdots p_n + 1$ = $N > 1$

Divise N par chaque nombre premier de la liste: $N$ vaut un de plus qu'un multiple de chaque $p_i$ = Le reste vaut toujours $1$, donc aucun $p_i$ ne divise $N$

Utilise un résultat connu: Tout entier supérieur à $1$ a au moins un facteur premier = $N$ a un facteur premier absent de la liste

Repère la contradiction: La liste était censée contenir tous les nombres premiers = L'hypothèse est fausse

Answer: Il existe une infinité de nombres premiers. Attention : $N$ lui-même n'est pas forcément premier. Avec les nombres premiers jusqu'à 13, $N = 30031 = 59 \times 509$, et 59 et 509 sont des nombres premiers absents de la liste. CQFD

Mistake: Nier "Il y a une infinité de nombres premiers" par "Il n'y a aucun nombre premier"

Why: Le contraire de "une infinité" n'est pas "aucun". La négation doit couvrir tous les cas où l'énoncé est faux, c'est-à-dire "un nombre fini seulement".

Correct: Suppose "Il n'y a qu'un nombre fini de nombres premiers". De même, la négation de "tout nombre premier est impair" est "au moins un nombre premier n'est pas impair", et non "tout nombre premier est pair".

Mistake: Nier $x > 5$ par $x < 5$

Why: Le cas $x = 5$ est oublié. Si la démonstration n'exclut que $x < 5$, le nombre $5$ reste possible.

Correct: La négation de $x > 5$ est $x \le 5$, et la négation de $x \ge 5$ est $x < 5$.

Mistake: Oublier "irréductible" dans la démonstration de l'irrationalité de $\sqrt{2}$

Why: Sans cette condition, trouver que $a$ et $b$ sont tous deux pairs n'est pas du tout une contradiction : $\frac{4}{2}$ a un numérateur et un dénominateur pairs.

Correct: Écris $\sqrt{2} = \frac{a}{b}$ sous forme irréductible. Toute fraction peut être simplifiée, donc cela ne coûte rien, et c'est exactement ce fait que la démonstration contredit ensuite.

Mistake: Prendre un résultat surprenant pour une contradiction

Why: Un résultat qui paraît étrange (un très grand nombre, une fraction inattendue) n'est pas impossible. Une contradiction doit entrer en conflit avec l'hypothèse ou avec un fait connu.

Correct: Nomme les deux énoncés qui se contredisent, par exemple "$r$ est le plus petit" et "$\frac{r}{2} < r$", puis écris la conclusion.

Trouver deux chaussettes assorties dans le noir

Le principe des tiroirs, démontré par l'absurde, donne le plus petit nombre d'objets qui garantit une répétition.

Un tiroir contient des chaussettes noires, blanches et grises. Si tu pouvais prendre 4 chaussettes toutes de couleurs différentes, il faudrait 4 couleurs, or il n'y en a que 3. Donc 4 chaussettes contiennent toujours une paire assortie.

Collisions de hachage en informatique

Les ordinateurs attribuent aux fichiers des codes courts appelés empreintes (hachages). Comme il y a plus de fichiers possibles que de codes, deux fichiers différents doivent parfois partager un code.

Un système attribue à chaque fichier un code de 00 à 99. Parmi 101 fichiers, supposer que tous les codes sont différents exigerait 101 codes, or il n'y en a que 100, donc deux fichiers partagent un code.

Pourquoi une calculatrice n'affiche jamais la valeur exacte de racine de 2

Comme $\sqrt{2}$ est irrationnel, son développement décimal ne se termine jamais et ne se répète jamais. Toute valeur décimale à l'écran n'est qu'une approximation, ce dont les ingénieurs tiennent compte quand ils calculent des diagonales.

Un carreau carré de 1 m de côté a une diagonale de $\sqrt{2} \approx 1{,}4142$ m. La valeur 1,4142 est proche, mais pas exacte.

Q: Pourquoi suffit-il d'aboutir à une contradiction ?

A: Un raisonnement correct à partir d'énoncés vrais ne produit que des énoncés vrais. Si on aboutit à quelque chose d'impossible, au moins un point de départ était faux, et le seul point de départ que nous avons ajouté nous-mêmes est l'hypothèse $\neg P$. Donc $\neg P$ est faux et $P$ est vrai.

Q: Quand dois-je utiliser le raisonnement par l'absurde ?

A: C'est un bon choix quand l'énoncé affirme que quelque chose n'existe pas (pas de plus grand nombre, pas de fraction égale à $\sqrt{2}$) ou qu'il existe une infinité de quelque chose. Dans ces cas, supposer le contraire te donne un objet concret avec lequel travailler.

Q: Le raisonnement par l'absurde est-il la même chose qu'une démonstration par contraposée ?

A: Non. Une démonstration par contraposée prouve directement "si non q, alors non p" et se termine par "non p". Un raisonnement par l'absurde suppose que l'énoncé est faux et peut se terminer par n'importe quelle impossibilité. Toute démonstration par contraposée peut être réécrite comme un raisonnement par l'absurde, mais un raisonnement par l'absurde n'est pas toujours une démonstration par contraposée.

Q: Que signifie CQFD, et qu'est-ce que "reductio ad absurdum" ?

A: CQFD ("ce qu'il fallait démontrer", en latin quod erat demonstrandum) marque la fin d'une démonstration. Reductio ad absurdum, "réduction à l'absurde", est le nom latin du raisonnement par l'absurde.