Preuve par épuisement: Mathématiques, Logique

Q: Qu'est-ce que la preuve par épuisement en mathématiques?

La preuve par épuisement est une méthode de démonstration où l'on vérifie tous les cas possibles pour prouver une affirmation.

Q: Comment fonctionne la preuve par épuisement?

Elle fonctionne en divisant le problème en tous les cas possibles et en vérifiant chacun d'eux pour confirmer qu'ils satisfont la proposition.

Q: Quand utilise-t-on la preuve par épuisement?

On l'utilise surtout quand il y a un nombre limité de cas à vérifier, ce qui la rend possible à réaliser.

Q: Quels sont les avantages de la preuve par épuisement?

Son principal avantage est qu'elle apporte une certitude totale, car tous les cas sont examinés sans exception.

Sauter à un chapitre clé

Qu'est-ce que la méthode de la preuve par épuisement ?

La preuve par épuisement est une méthode de preuve directe. Elle peut prendre beaucoup de temps, car il peut y avoir beaucoup de cas à vérifier. Il est possible de diviser les cas, par exemple les nombres pairs et impairs.

La preuve par épuisement est différente des autres méthodes de preuve directe, car nous n'avons pas besoin de tirer des arguments logiques. Il suffit de montrer qu'"aucun des cas ne réfute la conjecture ; la conjecture est donc vraie". La preuve par épuisement n'est utilisée que lorsqu'il y a un nombre fini de cas.

Comment prouver l'épuisement ?

Nous pouvons généraliser la méthode de la preuve par épuisement en utilisant deux étapes.

Étape 1 : Établir les cas qui s'appliquent à l'énoncé.

Étape 2 : Prouve que l'affirmation est vraie pour chaque cas.

Chaque cas de l'affirmation doit être prouvé séparément, un par un. Nous devons épuiser tous les cas pour vérifier l'affirmation.

Si l'un des cas identifiés peut être réfuté, l'ensemble de la conjecture peut être considéré comme réfuté. Tu peux consulter la section Démonstration par contre-exemple pour approfondir ce concept.

Prenons un exemple pour comprendre comment appliquer les étapes ci-dessus.

Montre que \(n^2-1\) est un multiple de 3 si n n'est pas un multiple de 3.

Solution :

Étape 1 : Si n n'est pas un multiple de 3, il est soit un, soit deux de plus qu'un multiple de 3. Nous pouvons donc écrire \(n = 3k + 1\) ou \(n = 3k + 2\), k étant un entier quelconque.

Étape 2 : Prouve maintenant que l'énoncé est vrai pour chaque cas.

Cas 1 : Montre que si \(n = 3k + 1\), alors \(n^2-1\) est un multiple de 3.

\N-(\N- Début{align} n^2-1 &= (3k + 1)^2 -1 \N- &= (3k)^2 + 6k +1-1 \N- &=9k^2 +6k \N- &=3(3k^2 + 2k) \N- Fin{align}\N)

Comme \N(3 (3k^2 + 2k)\Nest 3 fois \N((3k² + 2k)\N), nous pouvons conclure que \N(3 (3k^2 + 2k)\Nest un multiple de 3.

Ainsi, \(n^2 -1\) est un multiple de 3 pour \(n = 3k + 1\).

Vérifions maintenant le deuxième cas.

Cas 2 : Pour vérifier si \(n = 3k + 2\), alors \(n^2 -1\) est un multiple de 3.

\(\N- Début{align} n^2-1 &= (3k+2)^2 -1 \N- (3k)^2 + 2(3k)(2) + 2^2-1 \N- 9k^2 +12k + 3 \N- 3(3k^2 + 4k + 1) \N- Fin{align}\N)

L'expression résultante \(3 (3k^2 + 4k + 1)\) est également un multiple de 3 pour toute valeur de k. Ainsi, \(n^2 -1\) est un multiple de 3 pour \(n = 3k + 2\).

Comme les deux cas satisfont à l'énoncé, nous avons prouvé que l'énoncé donné est correct.

Quand utiliser la preuve par épuisement

La preuve par épuisement n'est possible que lorsque nous pouvons réduire la conjecture à un nombre fini de cas. Par exemple, nous avons réduit la conjecture à deux cas possibles dans l'exemple ci-dessus. Supposons que nous essayions plutôt de résoudre la conjecture par preuve par épuisement pour toutes les valeurs possibles de n. Ce serait un processus sans fin puisque le domaine de n n'est pas borné, c'est-à-dire que n peut prendre un nombre infini de valeurs.

Si nous pouvons réduire la conjecture donnée à un petit nombre de cas possibles, dont chacun peut être prouvé (ou réfuté), alors il peut être bon d'utiliser la preuve par épuisement. Pour un très grand nombre de cas, la preuve par épuisement n'est généralement pas une approche très efficace.

Exemples de preuves par épuisement

Exemple 1 : Montre que \(p = n^2 + 2\) n'est pas un multiple de 4, où n est un entier, \(2 \leq n \leq 7\).

Solution :

Étape 1 : divise l'énoncé en un nombre fini de cas.

Il est donné que \(2 \leq n \leq 7\) et pour chaque valeur de n, nous devons vérifier si \(p = n^2 +2\) est un multiple de 4 ou non.

Nous aurons six cas, comme indiqué.

Cas 1 : n = 2

Cas 2 : n = 3

Cas 3 : n = 4

Cas 4 : n = 5

Cas 5 : n = 6

Cas 6 : n = 7

Étape 2 : Prouve que l'affirmation est vraie pour chaque cas.

Prouvons chaque cas un par un.

Cas 1 : n = 2

Substitue n = 2 dans \(p = n^2 +2\) et vérifie si la valeur obtenue est un multiple de 4 ou non.

\(p = (2)^2 + 2 = 6\)

Comme 6 n'est pas divisible par 4, nous pouvons conclure que p n'est pas un multiple de 4.

Deuxième cas : n = 3

Substitue n = 3 dans \(p = n^2 +2\) et vérifie si la valeur obtenue est un multiple de 4 ou non.

\(p = (3)^2 + 2 =11\)

Comme 11 n'est pas divisible par 4, nous pouvons conclure que p n'est pas un multiple de 4.

Cas 3 : n = 4

Substitue n = 4 dans \(p = n^2 +2\) et vérifie si la valeur obtenue est un multiple de 4 ou non.

\(p = (4)^2 + 2 = 18\)

Comme 18 n'est pas divisible par 4, nous pouvons conclure que p n'est pas un multiple de 4.

Cas 4 : n = 5

Substitue n = 5 dans \(p = n^2 +2\) et vérifie si la valeur obtenue est un multiple de 4 ou non.

\(p = (5)^2 + 2 = 27\)

Comme 27 n'est pas divisible par 4, nous pouvons conclure que p n'est pas un multiple de 4.

Cas 5 : n = 6

Substitue n = 6 dans \(p = n^2+2\) et vérifie si la valeur obtenue est un multiple de 4 ou non.

\(p = (6)^2 + 2 = 38\)

Comme 38 n'est pas divisible par 4, nous pouvons conclure que p n'est pas un multiple de 4.

Cas 6 : n = 7

Substitue n = 7 dans \(p = n^2 +2\) et vérifie si la valeur obtenue est un multiple de 4 ou non.

\(p = (7)^2 + 2 = 51\)

Comme 51 n'est pas divisible par 4, nous pouvons conclure que p n'est pas un multiple de 4.

Comme tous les cas satisfont à l'énoncé. L'affirmation \N(p = n + 2\N) n'est pas un multiple de 4 lorsque n est un entier et \N (2 \leq n \leq 7\N) est correcte.

Exemple 2 : Si p est un nombre premier tel que \N(3 <p <25\N), alors prouve par épuisement que \N((p - 1) (p + 1)\Nest un multiple de 12.

Solution :

Étape 1 : divise l'énoncé en un nombre fini de cas.

Il est donné que p est un nombre premier tel que \(3 <p <25\), et pour chaque p, nous devons vérifier si \((p - 1) (p + 1)\) est un multiple de 12 ou non.

Les nombres premiers compris entre 3 et 25 sont 5, 7, 11, 13, 17, 19, 23.

Nous aurons sept cas, comme indiqué.

Cas 1 : p = 5

Cas 2 : p = 7

Cas 3 : p = 11

Cas 4 : p = 13

Cas 5 : p = 17

Cas 6 : p = 19

Cas 7 : p = 23

Étape 2 : Prouve que l'affirmation est vraie pour chaque cas.

Prouvons chaque cas un par un.

Cas 1 : Vérifier si \((p - 1) (p + 1)\) est un multiple de 12 lorsque p = 5.

\N- (\N- (p - 1) (p + 1) &= (5-1) (5 + 1) \N- &= (4) (6) \N- &= 24 \N- &= 2(12) \Nend{align}\N)

\N- \N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 5.

Cas 2 : Pour vérifier si \((p - 1) (p + 1)\) est un multiple de 12 lorsque p = 7.

\N- (\N- (p - 1) (p + 1) &= (7-1) (7 + 1) \N- &= (6) (8) \N- &= 48 \N- &= 4 (12) \N- (p - 1) (p + 1) &= (7-1) (7 + 1) \N- &= (6) (8) \N- &= 48 \N- &= 4 (12) \N-)

\N- \N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 7.

Cas 3 : Pour vérifier si \((p - 1) (p + 1)\) est un multiple de 12 lorsque p = 11.

\N- (p-1) (p + 1) &= (11-1) (11 + 1) \N- (10)(12) \N- (120) \N- (10 (12) \Nend{align}\N)

\N- \N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 11.

Cas 4 : Pour vérifier si (p - 1) (p + 1) est un multiple de 12 lorsque p = 13.

\N- (\N- (p - 1) (p + 1) &= (13-1) (13 + 1) \N- &= (12) (14) \N- &= 168 \N- &= 14 (12) \N- (p - 1) (p + 1) &= (13-1) (13 + 1) \N- &= (12) \N- (\N-)

\N- \N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 13.

Cas 5 : Pour vérifier si (p - 1) (p + 1) est un multiple de 12 lorsque p = 17.

\(\N- (p - 1) (p + 1) &= (17-1) (17 + 1) \N- &= (16) (18) \N- &= 288 \N- &= 24 (12) \N- (p - 1) (p + 1) &= (17-1) (17 + 1) \N- &= (16) (18) \N- &= 288 \N- &= 24 (12) \N- (p + 1))

\N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 17.

Cas 6 : Vérifier si \N((p - 1) (p + 1)\Nest un multiple de 12 lorsque p = 19.

\N- ((p - 1) (p + 1) &= (19-1) (19 + 1) \N- &= (18) (20) \N&= 360 \N&= 30 (12) \N- (p - 1) (p + 1) &= (19-1) (19 + 1) \N- &= (18) (20) \N-&= 360 \N-&= 30 (12) \N- (p + 1) \)

\N- \N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 19.

Cas 7 : Vérifier si \((p - 1) (p + 1)\) est un multiple de 12 lorsque p = 23.

\N- ((p - 1) (p + 1) &= (19-1) (19 + 1) \N- &= (18) (20) \N&= 360 \N&= 30 (12) \Nend{align} \)

\N((p-1) (p + 1)\N) est un multiple de 12 lorsque p = 23.

Ainsi, tous les cas satisfont l'énoncé. Par conséquent, l'affirmation, si p est un nombre premier tel que \(3 <p <25\), alors \((p - 1) (p + 1)\) est un multiple de 12, est correcte.

Exemple 3 : Si n est un entier positif, alors \(n^7-n\) est divisible par 7.

Solution :

Étape 1 : divise l'énoncé en un nombre fini de cas.

Il est donné que n est un entier, et pour chaque n, nous devons vérifier si \(n^7-n\) est divisible par 7 ou non.

Nous aurons sept cas, comme indiqué.

Cas 1 : n multiple de 7. Donc, \(n = 7q\), où q est un entier.

Cas 2 : n un de plus que le multiple de 7. Donc, \(n = 7q + 1\), où q est un nombre entier.

Cas 3 : n deux de plus que le multiple de 7. Donc, \(n = 7q + 2\), où q est un nombre entier.

Cas 4 : n trois plus que le multiple de 7. Donc, \(n = 7q + 3\), où q est un nombre entier.

Cas 5 : n quatre plus que le multiple de 7. Donc, \(n = 7q + 4\), où q est un nombre entier.

Cas 6 : n cinq plus que le multiple de 7. Donc, \(n = 7q + 5\), où q est un nombre entier.

Cas 7 : n six plus que le multiple de 7. Donc, \(n = 7q + 6\), où q est un nombre entier.

Étape 2 : prouve que l'énoncé est vrai pour chaque cas.

Factorisons d'abord l'expression \(n^7 -n\) et prouvons chaque cas un par un.

\N(n^7-n = n(n^6-1) = n((n^3)^2-1) = n(n^3+1)(n^3-1)\N)

Puisque \N(x^2 -y^(x+y)(x-y)\N) :

\(n(n+1)(n^2-n+1)(n-1)(n^2+n+1)\)

Puisque \N(x^3 + y^3 = (x+y)(x^2-xy+y^2)\N et \N(x^3-y^3 = (x-y)(x^2+xy+y^2)\N).

Donc, \N(n^7-n = n(n-1)(n+1)(n^2-n+1)(n^2+n+1)\N)

Vérifions maintenant chaque cas un par un.

Cas 1 : Pour vérifier que \(n^7-n\) est divisible par 7 pour, \(n = 7q\), où q est un entier.

\(n^7-n\) a un facteur \(n = 7q\).