Home

MPSI/PCSI

Maths

Analyse

Logique

Le cours explique le raisonnement par l'absurde pour prouver une propriété mathématique. La propriété à démontrer impose la présence d'au moins deux réels x_i et x_j (parmi un ensemble de x_0, x_1, ... x_n) tels que la distance entre eux est inférieure ou égale à 1/n. Pour commencer, on écrit la propriété sous forme de quantificateurs pour pouvoir facilement écrire sa négation. Ensuite, pour démontrer la propriété, on suppose sa négation et on cherche à obtenir une contradiction. On utilise la somme télescopique pour montrer que x_n - x_0 est supérieur ou égal à 1, ce qui est une contradiction puisque x_n et x_0 sont dans [0,1]. Enfin, on démontre la propriété autrement en utilisant le principe des tiroirs : on divise [0,1] en n segments de même longueur et on range les x_i dans ces segments. Comme il y a n+1 x_i et seulement n segments, il doit y avoir au moins deux x_i dans un même segment, ce qui implique que leur distance est inférieure ou égale à 1/n.

Salut c'est Paul, et aujourd'hui dans une nouvelle vidéo, on va aborder le raisonnement par l'absurde. Donc on nous demande de prouver pour n supérieur ou égal à 1, une propriété. Et cette propriété a besoin de n plus 1 réels, donc x0, x1, xn dans 0,1, qui sont ordonnés. Donc x0 est plus petit que x1, et plus petit que xn. Et on veut démontrer que parmi ces réels, il y en a au moins deux ici, dont la distance est inférieure ou égale à 1 sur n. Donc là on va nous guider à travers ces trois questions ici, de comment faire le raisonnement par l'absurde. Donc on nous tient un peu par la main. Et d'abord on va écrire la propriété ici sous forme de quantificateur, pour pouvoir écrire sa négation plus facilement. Et ça sert à quoi cette négation? Parce que pour le raisonnement par l'absurde, on prend la négation et on la suppose. Et après on arrive à une contradiction, ce qui nous donne que la négation est fausse, donc que la propriété est vraie. Et finalement, ici dans la troisième question, on nous demande de prouver. Donc là aussi je vois que dans la propriété, on a x i moins x i moins 1. Et là on nous demande de montrer, on pourra montrer que, bon on pourra, on est pas dupe, c'est ce qu'il faudra le faire. On pourra montrer que x n moins x 0 est supérieur ou égal à 1. En fait moi ça me fait penser au somme télescopique, parce que ici on a les x i moins x i moins 1. Et en fait si on les somme, les termes vont se simplifier de deux à deux. Et on va se débrouiller pour obtenir le premier terme moins le dernier terme de cette somme. Donc, donnez-en une preuve. Et après finalement, on nous demande de donner une autre preuve, donc alternative, pas par l'absurde, en utilisant le principe des tiroirs. Donc le principe des tiroirs, c'est quand on a n tiroirs et n plus 1 objets, donc n plus 1 chaussettes, c'est un peu comme ça qu'on l'apprend en général, ou comme moi je l'ai appris. Si on a n tiroirs et n plus 1 chaussettes, il y aura forcément un tiroir où il y aura au moins deux objets dedans, deux chaussettes en fait. Ça paraît assez évident comme ça, et c'est un principe qu'on peut utiliser comme ça sans démonstration. Donc il faudra trouver quels sont nos tiroirs et quelles sont nos chaussettes pour voir ce qu'on peut faire d'intéressant et réfléchir un peu à ce qu'on peut faire. Donc, la première question, écrire à l'aide de quantificateurs et des valeurs de x i moins x i moins 1 une formule logique équivalente à la propriété. Donc la propriété c'est, il y a deux de ces réels dont la distance est inférieure ou égale à 1 sur n. S'il y a deux de ces réels dont la distance est inférieure ou égale à 1 sur n, par exemple x1 et x3, il y a forcément deux réels qui sont comme ça, il y en a forcément deux côte à côte, donc conjoints, dont la distance va être inférieure ou égale à 1 sur n, parce que ça paraît assez évident comme ça. Donc du coup, il va y avoir des x i et des x i moins 1, un x i et un x i moins 1 tel que ça va être nos réels, tel que c'est des x, tel que leur distance est inférieure ou égale à 1 sur n. Et donc ça veut dire qu'il existe un i tel que x i moins x i moins 1 est inférieur ou égal à 1 sur n et on n'a pas besoin de mettre des valeurs absolues parce que les x i ici sont ordonnées, donc ici c'est positif. Donc c'est bien la distance entre x i et x i moins 1. Une fois qu'on l'a écrite, on écrit sa négation, donc il existe quel que soit i dans 1 sur n et x i moins x i moins 1 est strictement supérieur à 1 sur n, donc c'est bien la négation de cette assertion. Et maintenant on va rédiger la démonstration par l'absurde. Donc qu'est-ce qu'on fait? On suppose la négation, supposons ce qu'on vient d'écrire en haut là, et on va essayer d'arriver à une contradiction. Donc on pourra montrer que x n moins x 0 est strictement supérieur ou égal à 1. On va faire ça. Donc en fait, on va pour faire ça, comme j'ai dit, on va sommer cette relation, on va sommer cette inégalité sur 1 n. Donc si on la somme pour i allant de 1 à n, x i moins x i moins 1 est strictement supérieur ou égal à la somme de i allant de 1 à n de 1 sur n. Donc là ça nous donne n fois n donc égal à 1. Et là on sépare les deux sommes. Donc ça c'est les sommes télescopiques. Là je vous le détaille pour cette fois-ci, mais dès que vous repérez les sommes télescopiques, vous pourrez arriver directement au résultat si vous avez l'habitude. Et donc on fait un changement d'indice ici. On décale pour se retrouver avec du i et pour en fait finalement se retrouver avec la même somme ici, mais avec des plages d'indices différentes. Et là on voit que les plages d'indices communes, ici on va chercher les plages d'indices communes pour voir qu'est-ce qui se supprime. Là la plage d'indices communes c'est 1 n moins 1. Et donc il ne va rester que le terme ici x i de rang n et ici que le terme x i de rang 0, ce qui nous donne x n moins x 0 strictement supérieur ou égal à 1. Et ça en quoi c'est une contradiction avec l'énoncé ou ce qu'on sait. Mais en fait comme x n et x 0 appartiennent à 0, 1, ce n'est pas possible que leur distance soit strictement supérieure à 1. Parce que la mesure ici de cet ensemble est égale à 1, donc on voit bien que c'est une contradiction. Donc c'est impossible. Ainsi on a prouvé la propriété. Donc donnez-en une preuve de cette propriété en utilisant le principe de Zéthirois. Donc vous prouvez que les x i, ici, donc il y a au moins deux x i, x i moins x i moins 1 qui est inférieur à 1 sur n. Donc il y a la distance entre ces x i. Donc il y a deux x i dont la distance est inférieure ou égale à 1 sur n. Donc en fait on va trouver nos tiroirs d'abord. Et donc les tiroirs, moi je dis que c'est des ensembles I k, tels que k sur n sont égales à le segment de k sur n à k plus 1 sur n. On va faire un dessin pour voir ce que c'est ces I k. Ces I k en fait c'est un découpage, donc une partition de 0, 1. Avec I 1, I 2, et chaque I k a une longueur ici de 1 sur n. 1 sur n, 1 sur n, 1 sur n ici. Et bien qu'est-ce que ça va nous faire en fait? Comme ici on a n ensembles, donc n tiroirs, et on a n plus 1 x i, donc x i ça va être nos chaussettes. Donc on va avoir au moins un ensemble I k tel qu'il y a deux x i dedans. Et comme la longueur de l'ensemble I k est égale à 1 sur n, la distance entre ces deux x i va être inférieure ou égale à 1 sur n. Maintenant on va le prouver. La famille des I k forme une partition de 0, 1, de cardinal n. Donc il y a n ensemble, donc il y a n tiroirs. Et la famille des x a est incluse dans 0, 1 et est de cardinal n plus 1. Donc on veut ranger n plus 1 chaussettes dans n tiroirs. D'après le principe des tiroirs, il existe k appartenant à 0, n moins 1. Et il existe I j appartient à 0, n carré tel que I est différendi, donc I et J sont distants. Tel que I x i et x j appartiennent tous les deux à I k. Donc là, j'ai dit de manière quantifiée, avec des quantificateurs, qu'il y a au moins un tiroir, un ensemble I k avec deux x i, x j différents dedans. Et ça veut dire quoi? Ça veut dire que la distance entre x i et x j est inférieure ou égale à 1 sur n. Parce que la longueur de I k, du segment I k est inférieure ou égale à 1 sur n. Donc ça implique ça. Ainsi, on a prouvé la propriété avec le principe des tiroirs. C'est un peu plus élégant, mais c'est une astuce un peu spécifique à cet exercice, alors que le raisonnement par l'absurde qu'on a vu, c'est une méthode plus générale. Mais il faut bien penser à ça, le principe des tiroirs, c'est toujours utile. C'est la fin de cet exercice, et on se dit à une prochaine fois!

Absurde et principe des tiroirs

RELATED

Recommended videos

Utiliser les quantificateurs

Ecrire la négation

Equivalence et implication