Path: asynchrone!freenix!deine.net!fu-berlin.de!news.newsland.it!news.glou.org!fr-chartes!maintfaq From: raph@giromini.org (Les utilisateurs de fr.sci.maths) Newsgroups: fr.usenet.reponses,fr.sci.maths,fr.education.entraide.maths Subject: [FAQ] fr.sci.maths - partie 2/3 Supersedes: Followup-To: poster Date: Sun, 2 Feb 2003 04:42:26 GMT Approved: fr-reponses@frmug.org User-Agent: MaintFaq version 2.1b Expires: Wed, 19 Feb 2003 04:42:26 GMT Message-ID: Content-Type: text/plain; charset=iso-8859-15 Content-Transfer-Encoding: 8bit X-No-Productlink: yes Lines: 1912 Xref: asynchrone fr.usenet.reponses:8627 fr.sci.maths:15881 fr.education.entraide.maths:11423 www-Archive-Name: PDF-version: PS-version: Archive-Name: fr/maths/maths-faq-2 Last modified: 21 septembre 2001. Version 2.11 ##################################################### # # # FAQ fr.sci.maths (partie 2/3) # # # ##################################################### fr.sci.maths est un groupe de discussion destiné à recueillir les discussions en français concernant les mathématiques. Ce document rassemble les questions qui ont été fréquemment posées dans ce forum. Remarque sur la notation : le signe de multiplication utilisé ici est l'astérisque *, comme souvent en informatique. La version texte de ce document a été divisée en trois parties, afin de faciliter sa difusion sur les forums francophones. On trouvera, dans cette partie, les chapitres IV à VII inclus. Pour les chapitres I à III, se referer au document intitulé : "[FAQ] fr.sci.maths - partie 1/3". Pour les chapitre VI à VII, se referer au document intitulé : "[FAQ] fr.sci.maths - partie 3/3". Table des matières : I Contradictions. 1. Est-ce que 0,9999... = 1 ? 2. J'ai réussi à montrer que 2=1. 3. Zéro puissance zéro égal un (0^0 = 1). II Démonstrations. 1. Le petit théorème de Fermat. 2. ab et a+b premiers entre eux. 3. Irrationalité de la racine carrée de 2. 4. Irrationalité de la racine d'un nombre premier. 5. Irrationalité de e. 6. Transcendance de e. 7. Somme des puissances des premiers entiers. 8. Les nombres et les polynômes de Bernoulli. 9. Par combien de zéros le nombre 1998! se termine-t-il ? 10. Expression par radicaux des racines d'un polynôme de degré n. III Géométrie. 1. Problème de la chèvre. 2. Problème (dit) de Napoléon. -+- Début de la deuxième partie -+- IV Énigmes. 1. Pièces et balance, traduit par Vincent Lefèvre. 2. Les âges du capitaine. 3. Quel est le nombre qui continue cette suite : 2, 12, 1112,... 4. Probabilité que 2 personnes soient nées le même jour. 5. Somme et produit de deux entiers. 6. Les deux échelles. 7. La cuve de vin. V Questions fondamentales. 1. Les nombres premiers. 2. Pi. 3. Le grand théorème de Fermat. 4. La conjecture de Syracuse. 5. Les cardinaux des ensembles infinis - Partie I. 6. Les cardinaux des ensembles infinis - Partie II. 7. Qu'est-ce que le nombre e ? -+- Début de la troisième partie -+- VI Mathématiques et Ordinateur. 1. Comment écrire des formules mathématiques dans les News ? 2. Logiciels de mathématiques. 3. L'algorithme de CORDIC sur les calculatrices. VII Conclusion. 1. Références. 2. Remerciements. ======================================================================== Changements intervenus depuis la version précédente : - Correction d'une erreur dans le paragraphe V.1 Les nombres premiers. - Ajout d'un lien pour télécharger Maple V release 4, en version étudiante. Les changements sont précédés du caractère : | ======================================================================== IV Énigmes. ========= 1. Pièces et balance. ------------------ Traduction de logic/weighing/balance des archives de rec.puzzles Problème On vous donne 12 pièces qui paraissent identiques, dont l'une est contrefaite et a un poids légèrement différent des autres (vous ne savez pas si la pièce est plus lourde ou plus légère). On vous donne une balance de Roberval, qui vous permet de mettre le même nombre de pièces de chaque côté et d'observer quel côté (s'il y en a un) est plus lourd. Comment identifier la pièce contrefaite et déterminer si elle est plus lourde ou plus légère, en 3 pesées? Solution Martin Gardner a donné une jolie solution à ce problème. Supposez que vous avez le droit à P pesées. Écrivez les 3^P chaînes possibles de longueur P ayant pour caractères " 0 ", " 1 " et " 2 ". Éliminez les 3 chaînes comportant uniquement un caractère répété P fois. Pour chaque chaîne, trouvez le premier caractère différent du caractère le précédant. Considérez ce couple de caractères. Si ce couple n'est pas 01, 12 ou 20, éliminez cette chaîne. En d'autres termes, seules les chaînes de la forme 0*01.*, 1*12.* ou 2*20.* (expressions rationnelles) sont acceptées. Il doit vous rester (3^P-3)/2 chaînes. C'est le nombre de pièces que vous pouvez contrôler en P pesées. Associez donc chaque pièce à une chaîne de P caractères. Effectuez P pesées comme suit: Pour la pesée I, mettez d'un côté toutes les pièces ayant un 0 dans la chaîne en position I, et mettez de l'autre côté toutes les pièces ayant un 2 dans la chaîne en position I. Si le côté avec les 0 en position I est plus lourd, écrivez un 0. Si c'est l'autre côté qui est plus lourd, écrivez un 2. Sinon, écrivez un 1. Après P pesées, vous avez écrit une chaîne de P caractères. Si votre chaîne correspond à une des pièces, alors c'est cette pièce qui est contrefaite, et elle est plus lourde. Sinon, changez chaque 2 en 0 et chaque 0 en 2 dans votre chaîne. Votre chaîne correspondra alors à l'une des pièces, et cette pièce est plus légère que les autres. Notez que si vous devez seulement identifier la pièce contrefaite, mais pas déterminer si elle est plus lourde ou plus légère, vous pouvez contrôler (3^P-3)/2+1 pièces. Étiquetez la pièce supplémentaire par la chaîne contenant uniquement des 1, et utilisez la méthode ci-dessus. Notez aussi que vous pouvez contrôler (3^P-3)/2+1 pièces si vous devez déterminer si la pièce contrefaite est plus lourde ou plus légère, pourvu que vous ayez une pièce de référence, dont vous savez qu'elle a le poids correct. Vous faites ceci en étiquetant la pièce supplémentaire par la chaîne contenant uniquement des 2. Cette pièce est placée toujours du même côté, et ce plateau contient une pièce de plus que l'autre. Alors, placez la pièce de référence de l'autre côté, à chaque pesée. Il est très facile de prouver que ceci marche, une fois que vous avez remarqué que la méthode de construction des chaînes assure qu'à chaque position, 1/3 des chaînes ont un 0, 1/3 ont un 1, et 1/3 ont un 2, et que si une chaîne est dans la liste, alors celle obtenue en remplaçant chaque 0 par un 2 et chaque 2 par un 0 n'y est pas. Si vous savez déjà que la pièce contrefaite est plus lourde (ou plus légère), vous pouvez contrôler 3^P pièces. Avec P pesées, il ne peut y avoir que 3^P combinaisons d'équilibre, plateau de gauche plus lourd et plateau de droite plus lourd. L'algorithme est dans ce cas: Partagez les pièces en 3 groupes de même taille... A, B et C. Pesez A avec B. Si un plateau tombe, il contient la pièce lourde, sinon cette pièce est dans le groupe C. Si la taille de votre groupe est 1 vous avez trouvé la pièce, sinon faites une recurrence sur le groupe contenant la pièce lourde. 2. Les âges du capitaine. ---------------------- Le capitaine dit à son fils: " La cabine n°1 abrite M. DUPONT et ses deux filles. Le produit de leurs trois âges est 2450 et la somme de leurs trois âges est égale à 4 fois le tien. Peux-tu trouver les âges des trois passagers ? " Après un instant, le fils répond: " Non, il me manque une donnée. " Le capitaine ajoute alors: " Je suis plus âgé que M. DUPONT. " Le fils du capitaine en déduit aussitôt les trois réponses. Quel est l'âge du capitaine ? de son fils ? de M. DUPONT ? Quels sont les âges des deux filles ? Étant donné que le produit des âges vaut 2450, c'est donc que les âges des voyageurs sont des diviseurs de 2450. Or 2450 = 1*2*5*5*7*7 (décomposition en nombres premiers) On a alors comme âges possibles : 1, 2, 5, 7, 10, 14, 25, 35, 49, 50, 70, 98, 175, 245, 350, 490, 1225, ou 2450. Il semble absurde de supposer que l'âge d'un des passagers puisse excéder 174 ans (quoi que...). Ainsi, les âges possibles sont réduits aux douze premiers diviseurs. On a donc qu'un nombre fini de triplets possible : {98,25,1} , {98,5,5} , {70,35,1} , {70,7,5} , {50,49,1} , {50,7,7}, {49,25,2} ,{49,10,5}... (je ne les écrit pas tous) Il suffit de faire la somme de chacun des triplets. Or le fils du capitaine dit ne pas avoir assez d'indices pour trouver avec les sommes, c'est donc qu'il existe deux sommes identiques. En effet, les triplets {50,7,7} et {49,10,5} ont la même somme (64 ans). On en déduit l'âge du fils qui est de 64/4 = 16 ans. De plus comme le capitaine est plus âgé que M. Dupont, on déduit que M. Dupont n'a que (sic!) 49 ans De là ses filles ont 10 et 5 ans. On peut également dire que le capitaine a 50 ans. Donc M. Dupont a 49 ans les deux filles ont 5 et 10 ans Le capitaine a 50 ans et Le fils a 16 ans 3. Quel est le nombre qui continue cette suite : 2, 12, 1112... ------------------------------------------------------------ La construction de la suite se fait comme suit : il faut lire à haute voix les chiffres qui la composent. On part de " 2 ", on lit un " 2 ", on écrit 12. Puis, on lit un " 1 ", un " 2 " on écrit 1112. On lit trois " 1 ", un " 2 ", on écrit 3112. On peut montrer par l'absurde que le nombre de signes distincts qui composent cette suite se limite aux chiffres 1, 2 et 3. En effet, supposons qu'à une ligne on trouve le chiffre 4, suivi par exemple du chiffre 1. Cela signifie qu'à la ligne précédente, on avait la suite ...1111... C'est à dire à la ligne d'avant ...11..., que l'on aurait dû traduire par 21 et non 1111 comme cela a été fait. D'où contradiction. Il ne peut donc pas y avoir de chiffre supérieur strictement à 3. Dans la suite, on prendra la convention : u(0)=2 u(1)=12 u(2)=1112 etc. Nous nommerons u(n) la valeur trouvée à l'étape n Cette suite ne peut pas se stabiliser, et même elle tend vers l'infini. nous savons calculer u(n+1) en fonction de u(n) mais aussi, en toute logique, u(n-1) en fonction de u(n) (cela paraît évident) qui n'a qu'une seule valeur possible en fonction de u(n). Ainsi, supposons qu'il existe m>n tels que u(m) = u(n) alors, d'après l'observation précédente, u(m-1) = u(n-1) et finalement par une récurrence évidente, u(m-n) = u(0) = 2. Or m-n>0 donc d'après la méthode de construction de la liste, u(m-n) a un nombre pair de chiffres d'où une contradiction. Donc quels que soient m et n, u(m)<>u(n) ; soit v(n) la suite définie de la façon suivante : si il existe k tel que u(k)=n alors v(n)=k. Sinon, v(n)=0 Quel que soit A de N, N=max(v(0)...v(N)) => (n>N => u(n)>A). Donc u(n) tend vers l'infini. On peut même montrer que le nombre de 1 diverge : Je nomme groupe une suite de chiffres faisant partie d'une autre suite: non décalé (gn) si il commence par un chiffre de rang impair groupe décalé (gd) si il commence par un chiffre de rang pair (1232 est un gn de 221232 et un gd de 2221232). Si X et Y sont deux groupes, je note X -> Y si une partie de X engendre Y en remontant dans les termes de la suite (engendrer sera toujours employé dans ce sens). ex : 1112 (gn) -> 12 2322 (gn) -> 3322 2322 (gd) -> 222 (en effet, les chiffres peuvent être groupés par deux lorsque l'on remonte dans la suite). On appellera un doublet, une gn de deux chiffres. Deux doublets consécutifs ne peuvent pas se terminer par le même chiffre (on appellera cela une incompatibilité de répétition ir) le groupe 333 ne peut pas exister car il contient forcément un doublet 33 et donc engendrera forcément 333 ce qui par récurrence arrive à une contradiction évidente. le doublet 33 ne peut donc pas exister. Un groupe contenant un doublet 33 provoquera une incompatibilité 3 (i3). Cherchons les gn de quatre chiffres ne contenant pas de 1 et ne provoquant pas d'incompatibilité (ie: pouvant exister dans la suite): je ne regarde pas les ir et les i3 triviales : 2223 -> 2233 supposé compatible 2322 -> 3322 supposé compatible 2332 -> 33222 i3 si gn et ir si gd incompatible 3223 -> 22233 supposé compatible tous les autres sont incompatibles. Cherchons les gn de huit chiffres ne contenant pas de 1 et ne provoquant pas d'incompatibilité (il sont constitués des gn de quatre chiffres compatibles): 22232223 -> 22332233 i3 si gn donc gd -> 3322233 i3 dans tous les cas 22232322 ir 22233223 -> 223322233 i3 dans tous les cas 23222223 ir 23222322 -> 33223322 i3 si gn donc gd -> 22233222 i3 si gd et ir si gn 23223223 ir 32232223 -> 222332233 i3 si gd donc gn -> 223322233 i3 dans tous les cas 32232322 ir 32233223 -> 2223322233 i3 dans tous les cas Donc tout gn de 8 chiffres contient au moins un 1. Cette suite tendant vers l'infini, le nombre de gn de 8 chiffres (même sans recouvrement) tend vers l'infini. Donc le nombre de 1 aussi. On constate que la fin du code est stabilisée dès la 6ème itération pour ses signes finaux. On note D la transformation telle que u(n+1)=D(u(n)). On note |X| le nombre de chiffres du groupe X. Lemme 1 : pour n>=6, u(n) se termine par 222112 si n est pair, et par 322112 si n est impair. par récurrence. C'est vrai pour n = 6. Soit n > 6, supposons la propriété vérifiée pour n et montrons la pour n+1. Si n est pair, u(n) se termine par 222112. Le chiffre précédent, s'il existe, n'est pas un 2 (puisqu'on n'a pas 4 chiffres identiques consécutifs). Donc u(n) se termine par un bloc de trois 2, puis un bloc de deux 1, puis un 2, et donc u(n+1) se termine par 322112 ; n+1 étant impair, c'est précisément ce qu'on attendait. Si n est impair, u(n) se termine par 322112. Peu importe si le chiffre précédent est un 3 ou non, seuls les trois derniers blocs nous intéressent, et u(n+1) se termine donc par 222112 ; n+1 étant pair, c'est ce qu'on attendait. Lemme 2 : soit x(n) la suite définie pour n>=6 par x(6)=222112, x(7)=322112, x(8)=3222112, x(9)=3322112, x(10)=23222112, et pour n>=10, x(n+1) est égal à D(x(n)) privé de son premier chiffre. 1. Pour tout n>=6, x(n) est un suffixe de u(n). 2. Pour tout n>=6, x(n) est un suffixe de x(n+2). 3. Pour n>=11, |x(n)| est impair et |x(n+2)| >= |x(n)|+2. 4. Pour tout n, |x(n)| >= n-2. Preuve : 1. Par récurrence sur n, d'après la définition de u(n). Noter qu'il est important d'enlever le premier chiffre de D(x(n)) pour construire x(n+1), car le chiffre précédant x(n) dans u(n) peut être identique au premier chiffre de x(n), ce qui modifie la longueur du premier bloc ; en revanche, le second chiffre de D(x(n)), qui indique la nature du premier bloc de x(n), peut être conservé car il apparaît bien à cet endroit dans u(n+1). Au passage, on peut noter que ce chiffre est toujours un 2. 2. Par récurrence sur n. On le vérifie à la main pour n < 10. Pour n>=10, si x(n) est un suffixe de x(n+2), alors x(n+1) est un suffixe strict de D(x(n+2)), donc c'est un suffixe de x(n+3). 3. Pour n>=11, la longueur de x(n) est impaire par construction. On montre |x(n+2)| >= |x(n)|+2 par récurrence. C'est vrai pour n=11 (et même n=9 et n=10). Supposons que |x(n+2)| >= |x(n)|+2 pour un certain n>=11. Comme x(n) est un suffixe de x(n+2), on peut écrire x(n+2) = wx(n), avec |w| >= 2. L'avant dernier chiffre de w ne peut être égal au premier chiffre de x(n), car il s'agit de deux chiffres consécutifs en position impaire qui sont toujours distincts dans une image par D. Par conséquent D(x(n+2)) contient au moins un bloc de plus que D(x(n)) et donc |D(x(n+2))| >= |D(x(n))|+2, d'où |x(n+3)| >= |x(n+1)|+2. 4. Se déduit facilement des valeurs initiales et de 3. Théorème : pour tout l>=0, il existe un entier n0 tel que pour tout n > n0, le suffixe de longueur l de u(n) coïncide avec le suffixe de longueur l de u(n+2). C'est vrai d'après le lemme 1 pour l <= 6, en prenant n0 = 6. Pour l supérieur à 6, on prend n0 = l+2. Alors pour n > n0, le suffixe de longueur l de u(n) est un suffixe de x(n), puisque |x(n)| >= n-2 >= l d'après le 4. du lemme 2. Il coïncide donc avec le suffixe de longueur l de u(n+2), puisque x(n) est un suffixe de x(n+2) qui est un suffixe de u(n+2). ( d'après les 2. et 1. du lemme 2. ) On peut formaliser ce résultat en définissant une topologie convenable sur l'ensemble des mots finis et infinis sur l'alphabet {1,2,3}. On peut alors montrer que la suite u(n) a deux valeurs d'adhérence, qui sont deux mots infinis à gauche : ...131221121321131112111322311211132132212312211322212221121123222112 et ...211331123113221321123113121322111213112221133211322112211213322112 Exercice : faire la même chose en regardant cette fois le début des mots (ce qui est plus habituel que de regarder la fin, d'ailleurs !). Cette fois, il y a 3 valeurs d'adhérence. Enfin, on peut montrer que la proportion de 1 a une limite finie, qui est un nombre algébrique de degré 71. L'idée de Conway est d'identifier un certain ensemble fini de blocs (qu'il nomme selon les éléments chimiques), de sorte que si x est l'un de ces blocs, D(x) s'exprime comme concaténation de plusieurs blocs élémentaires, et de plus qu'il n'y ait jamais d'interaction entre blocs consécutifs, de sorte que D(xy) = D(x)D(y). D agit alors comme une substitution (i.e. un morphisme de monoïde) sur les mots formés de symboles de blocs élémentaires, et le nombre d'occurrences de chacun des blocs élémentaires peut être exprimé à l'aide de puissances de la matrice de la substitution. D'où finalement une densité qui s'exprime en fonction des valeurs propres de cette matrice et est donc un nombre algébrique. Lire à ce sujet: -- J.H. Conway "The weird and Wonderful Chemistry of Audioactive Decay" in "Open Problems in Communications and Computation" T.M. Cover and B. Gopinath eds., Springer 1987 -- Shalosh B. Ekhad and Doron Zeilberger "Proof of Conway's Lost Cosmological Theorem" -- Les commentaires d'un mathématicien, de Jean-Paul Delahaye in "Pour la Science", Janvier 1996, p.100 et suivantes. Voir, entre autres (Warning, in english) : http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/SEQUENCES/series000 http://www.univie.ac.at/EMIS/journals/ERA-AMS/1997-01-011/1997-01-011.html http://www.math.temple.edu/~zeilberg/mamarim/mamarimhtml/horton.html 4. Probabilité que 2 personnes soient nées le même jour. ----------------------------------------------------- On réunit dans une pièce n personnes. On veut determiner, d'une part, quelle est la probabilité que deux de ces personnes soient nées le même jour et d'autre part, à partir de combien de personnes il y a plus d'une chance sur deux que l'événement cherché soit réalisé. Enfin, on s'intéressera aux différentes méthodes de calcul et à ce qu'il se passe quand les dates de naissance ne sont pas équiprobables. a) Toutes les dates de naissance sont équiprobables. On supposera dans un premier temps que les dates d'anniversaire ont la même probabilité d'apparition. La bonne solution, comme souvent en probabilités, consiste à calculer la probabilité de l'événement complémentaire. C'est à dire qu'on s'intéresse à la probabilité qu'il n'y ait aucune coïncidence des dates d'anniversaire dans un groupe de n personnes. En effet, la probabilité d'un événement additionnée à celle de son complémentaire est égale à 1. Donc la probabilité de l'événement est égale à un moins la probabilité de son complémentaire. Le nombre total de cas possibles est 365 à la puissance n noté 365^n. Le nombre de cas favorables est le nombre de choix ordonnés de n dates parmi 365, soit: 365! / (365-n)! Donc, la probabilité qu'il n'y ait aucune coïncidence de dates d'anniversaire est : 365! / ((365-n)! * 365^n ) = produit[(365 - i)/365 , pour i=0 à n-1] = produit[1 - i/365 , pour i=0 à n-1] La probabilité P(n) qu'il y ait au moins une coïncidence est donc : P(n) = 1 - produit[1 - i/365 , pour i=0 à n-1] Il existe d'autres solutions, par exemple, la suivante. On nomme A, B etc. les personnes de l'assistance. Alors, il y a une coïncidence si A a le même anniversaire que B, ou que C,... Ou encore si B a le même anniversaire que C, etc. Le problème de cette méthode, c'est qu'il faut ensuite calculer la probabilité d'une union d'événements qui ne sont pas disjoints. Il faut faire la somme des probabilités des évènements, en enlever la somme des intersections 2 à 2, ajouter la somme des intersections 3 à 3, etc. (c'est la formule de Poincaré). C'est long et pénible. b) A partir de quelle valeur de n cette probabilité dépasse-t-elle 1/2 ? La seule solution est de calculer la probabilité pour différentes valeurs de n, et de rechercher la première valeur de P(n) dépassant 1/2. Cette valeur est 23. En effet, on trouve par le calcul: P(22)=0.4756953077 P(23)=0.5072972343 c) Les différentes méthodes de calcul pratique Si on veut calculer brutalement le nombre : 365! /((365-n)! * 365^n) avec une machine à calculer, on obtient un dépassement de capacité. Il faut donc réfléchir un peu pour faire le calcul, en tenant compte des possibilités informatiques. -- Si on dispose d'un logiciel de calcul mathématique, tel que Maple ou Mathématica, le problème de dépassement de capacité disparaît, et on utilise n'importe laquelle des expressions ci-dessus. -- Si on dispose d'une calculatrice programmable, il est possible de programmer, avec une boucle, le calcul de l'expression : produit[1 - i/365 , pour i=0 à n-1] Comme cette programmation dépend de la calculatrice et du langage utilisés, il est difficile d'en dire plus. -- Si l'on dispose d'un tableur, l'expression : produit[1 - i/365 , pour i=0 à n-1] est facile à calculer en faisant un tableau de taille n, avec 3 colonnes : une colonne pour i, une colonne pour 1 - i/365, une colonne pour le produit. -- Si l'on n'a qu'une calculatrice scientifique, il est nécessaire d'utiliser une approximation. Il faut remarquer que produit[1 - i/365 , pour i=0 à n-1] = exp(somme[log(1 - i/365) , pour(i=0 à n-1)]) Or, si n est beaucoup plus petit que 365, on a : log(1 - i/365) ~ -i/365 Et comme la somme des n premiers entiers est égal à n*(n+1)/2. On a donc : produit[1 - i/365 , pour i=0 à n-1] ~ exp( -n*(n-1)/730) Cette approximation est relativement précise. Elle donne les valeurs suivantes pour P(22) et P(23), ce qui donne une réponse juste pour la question (2) malgré la très forte proximité de P(23) avec 1/2 : P(22) ~ 0.4689381108 P(23) ~ 0.5000017522 d) Probabilités inégales pour les dates de naissance Nous avons jusque là supposé que toutes les dates de naissance étaient de même probabilité. Que se passe-t-il si on se passe de cette hypothèse ? Les probabilités de coïncidence d'anniversaire sont augmentées. Cela paraît assez naturel puisque, si ces probabilités sont très concentrées, par exemple sur une seule date dans l'année, la probabilité de coïncidence se rapproche de 1. La difficulté de cette question tient au fait que l'on ne peut pas faire varier n'importe comment les probabilités des différentes dates de naissance. En effet, il faut que la somme de toutes ces probabilités fasse 1. Notons p_i la probabilité de naissance le jour i et A l'ensemble des jours de l'année. Alors la probabilité de non-coïncidence est : ______ _____ \ | | ) | | p_i / | | ------ i dans S S inclus dans A tel que card(S)=n On s'intéresse aux jours 1 et 2. Les ensembles de cardinal n inclus dans A peuvent être classés en 3 catégories: les ensembles ne contenant ni 1 ni 2, les ensembles contenant 1 ou 2, mais pas les deux, les ensembles contenant 1 et 2. On note A' l'ensemble A, moins les éléments 1 et 2. La somme ci-dessus peut être réécrite : _____ _____ _____ _____ _____ _____ \ | | \ | | \ | | ) | | p_i +(p + p )* ) | | p_i + p * p * ) | | p_i / | | 1 2 / | | 1 2 / | | ----- i dans S ----- i dans S ----- i dans S S inclus S inclus S inclus dans A' tel que dans A' tel que dans A' et que card(S)=n card(S)=n-1 card(S)=n-2 Supposons que p1 et p2 soient différents, et montrons que l'on peut augmenter la probabilité de non-coïncidence. On remplace p1 et p2 par (p1 + p2)/2. Le premier des 3 termes ci-dessus n'est pas modifié, puisque ni p1 ni p2 n'y apparaissent. Le second non plus, car il ne dépend que de p1+p2. En revanche, le troisième terme est augmenté, car on remplace p1*p2 par ((p1 + p2)/2)^2 qui est plus grand. Donc, si les p_i sont différents, la probabilité de non-coïncidence n'est pas maximale. Par la suite, on démontre qu'une fonction continue sur un ensemble fermé borné atteint son maximum. Or, l'ensemble des vecteurs formés de 365 probabilités, dont la somme fait 1, est un ensemble fermé borné. Donc le maximum de la probabilité de coïncidence est atteint. Il ne peut être atteint que si tous les pi sont égaux, qui est donc le maximum. Donc, la probabilité de non coïncidence est maximale si les probabilités de jours de naissance sont égales. Par conséquent, si les probabilités sont égales, la probabilité de coïncidence d'anniversaire est minimale. 5. Somme et produit de deux entiers. --------------------------------- a) Enoncé. Un prof de maths donne un problème à résoudre à ses deux meilleurs élèves, Pierre et Sophie. Il donne à Pierre le produit de deux nombres entiers compris (au sens large) entre 2 et 100, et à Sophie la somme des deux mêmes nombres, puis il leur demande s'ils peuvent déterminer quels étaient les nombres de départ. Pierre: Non, je ne peux pas trouver ces deux nombres. Sophie: Je le savais. Pierre: Dans ce cas, je connais les deux nombres. Sophie: Alors moi aussi. Sachant que les deux élèves sont d'excellents logiciens et que leurs quatre déclarations étaient rigoureusement exactes, saurez-vous être aussi futés qu'eux, et trouver les deux nombres choisis par le professeur ? b) Commentaires. L'énoncé tel qu'il est présenté ici est le plus proche de ce qui est en général posé dans news:fr.sci.maths. Malheureusement, il lui manque des précisions importantes sur ce que le prof de maths dit effectivement aux élèves. D'abord, il n'est pas précisé que Pierre sait que Sophie a la somme, et que Sophie sait que Pierre a le produit. Bon, d'accord, c'est « évident ». Mais il y a un autre point qui semble « évident » alors qu'il est souvent source d'erreurs de raisonnement. Cet autre point, c'est que l'on ne sait pas si Pierre et Sophie connaissent la valeur minimum (2) et la valeur maximum (100) des nombres de départ. Pour ce qui est de la valeur minimum, il faut qu'ils la connaissent ; sinon, le problème est impossible (par exemple, s'ils pensent que les nombres commencent à 1 au lieu de 2, alors la seule solution serait 1 et 4, qui ne rentre pas dans le cadre de l'énoncé). En ce qui concerne la valeur maximum, les deux cas sont possibles (soit ils connaissent la limite, soit ils ne la connaissent pas), ce qui donne deux problèmes différents, intéressants tous les deux. c) Solutions. Puisqu'il y a deux interprétations possibles de l'énoncé, il y a aussi deux solutions distinctes. La première (c.1) suppose que Pierre et Sophie savent que les nombres sont compris entre 2 et 100, alors que la seconde (c.2) suppose qu'ils savent seulement que les nombres sont supérieurs ou égaux à 2. Néanmoins, la méthode utilisée est la même dans les deux cas, à savoir prendre chacune des 4 affirmations dans l'ordre, et en déduire des informations précieuses sur les sommes S et produits P possibles. c.1) Solution dans le premier cas (valeur maximum connue, égale à 100). Pierre: Non, je ne peux pas trouver ces deux nombres. Ceci signifie que le produit P peut se décomposer d'au moins deux manières différentes en produit de deux nombres compris entre 2 et 100. Par exemple, on pourrait avoir P = 75, car ce produit se décompose en 3*25 ou 5*15, mais on ne peut pas avoir P = 77 car alors la décomposition serait unique : 7*11. Voici une liste de valeurs que nous pouvons d'ores et déjà éliminer: - toute valeur inférieure à 4 ou supérieure à 10000 - le produit de deux nombres premiers (par exemple 77 = 7*11) - le cube d'un nombre premier (par exemple 125 = 5*25) - le double du carré d'un premier plus grand que 10 (par exemple, 242 = 2*11*11 = 11*22 : la décomposition en 2*121 est impossible) - un multiple strict d'un nombre premier plus grand que 50 (par exemple 318 = 6*53) - le produit du carré d'un premier plus grand que 10 par un nombre premier (par exemple 242 = 2*11*11 = 11*22 ; la décomposition en 2*121 est impossible) - et bien d'autres... --- Sophie: Je le savais. Ceci signifie que la somme S ne peut pas s'écrire comme somme de deux nombres dont le produit aurait été éliminé dans l'étape précédente. Par exemple, la somme 11 convient car tous les produits possibles sont "non uniques" : 11 = 2+9 ; 2*9 = 18 = 3*6 11 = 3+8 ; 3*8 = 24 = 2*12 = 4*6 11 = 4+7 ; 4*7 = 28 = 2*14 11 = 5+6 ; 5*6 = 30 = 2*15 = 3*10 En revanche, la somme 13 ne convient pas car : 13 = 2+11 ; 2*11 = 22 (pas d'autre décomposition) Par conséquent, on peut commencer par éliminer toutes les sommes de deux nombres premiers. Vous pouvez vérifier que cela élimine déjà toutes les sommes paires (ceci a été conjecturé par Goldbach dans le cas général, et vérifié par ordinateur sur beaucoup plus de nombres que ce dont on a besoin pour résoudre ce problème). Pour ce qui est des sommes impaires, on élimine celles qui sont égales à un nombre premier plus 2: 5 (3+2), 7(5+2), 9(7+2), 13 (11+2), etc. Après ce premier débroussaillage, il nous reste les sommes qui sont égales à un nombre composé impair plus 2 : 11 (3*3 + 2), 17 (3*5 + 2), 23 (3*7 + 2), 27 (5*5 + 2), 29, 35, 37, 41, 47, 51, 53, 57, 59, etc. Nous pouvons aussi supprimer toutes les sommes S à partir de 57, puisque : si 57 <= S <= 153, on peut écrire S = 53 + n, avec 4 <= n <= 100, si 155 <= S <= 197, on peut écrire S = 97 + n, avec 58 <= n <= 100, si S = 199, on peut écrire S = 100 + 99. Dans chacun de ces trois cas, le produit P correspondant (soit 53*n, soit 97*n, soit 100*99) a une décomposition unique. On peut enfin supprimer la somme S = 51 = 17 + 34, car le produit P = 17*34 n'a pas d'autre décomposition. Voici donc la liste exhaustive des sommes possibles à cette étape du raisonnement, avec pour chaque somme la liste des produits possibles. 11 : 18 24 28 30 17 : 30 42 52 60 66 70 72 23 : 42 60 76 90 102 112 120 126 130 132 27 : 50 72 92 110 126 140 152 162 170 176 180 182 29 : 54 78 100 120 138 154 168 180 190 198 204 208 210 35 : 66 96 124 150 174 196 216 234 250 264 276 286 294 300 304 306 37 : 70 102 132 160 186 210 232 252 270 286 300 312 322 330 336 340 342 41 : 78 114 148 180 210 238 264 288 310 330 348 364 378 390 400 408 414 418 420 47 : 90 132 172 210 246 280 312 342 370 396 420 442 462 480 496 510 522 532 540 546 550 552 53 : 102 150 196 240 282 322 360 396 430 462 492 520 546 570 592 612 630 646 660 672 682 690 696 700 702 --- Pierre: Dans ce cas, je connais les deux nombres. Pour que Pierre puisse faire cette affirmation, il faut que le produit P se trouve une fois et une seule dans la liste que nous venons d'écrire. Cela élimine donc les produits P = 30 (S = 11 ou 17), P = 42 (S = 17 ou 23), etc. Il reste: 11 : 18 24 28 17 : 52 23 : 76 112 130 27 : 50 92 110 140 152 162 170 176 182 29 : 54 100 138 154 168 190 198 204 208 35 : 96 124 174 216 234 250 276 294 304 306 37 : 160 186 232 252 270 336 340 41 : 114 148 238 288 310 348 364 378 390 400 408 414 418 47 : 172 246 280 370 442 480 496 510 522 532 540 550 552 53 : 240 282 360 430 492 520 570 592 612 630 646 660 672 682 690 696 700 702 --- Sophie: Alors moi aussi. Pour que Sophie puisse dire cela, il faut qu'il ne reste plus qu'un seul produit correspondant à la somme qu'elle connaît. Ceci n'est réalisé que si la somme est 17, auquel cas le produit est 52. Les nombres de départ sont donc 4 et 13. c.2) Solution dans le second cas (valeur maximum inconnue). Pierre: Non, je ne peux pas trouver ces deux nombres. Ceci signifie que le produit n'est pas le carré ou le cube d'un nombre premier, ni le produit de deux nombres premiers. Nous ne pouvons rien en déduire de plus pour le moment. --- Sophie: Je le savais. Comme dans le premier cas, nous pouvons éliminer toute somme paire et toute somme d'un nombre premier avec 2, et il nous reste les sommes égales à un nombre composé impair plus 2. Contrairement au premier cas, nous ne pouvons éliminer aucune autre somme. La liste (incomplète) des sommes et produits possibles est la suivante: 11 : 18 24 28 30 17 : 30 42 52 60 66 70 72 23 : 42 60 76 90 102 112 120 126 130 132 27 : 50 72 92 110 126 140 152 162 170 176 180 182 29 : 54 78 100 120 138 154 168 180 190 198 204 208 210 35 : 66 96 124 150 174 196 216 234 250 264 276 286 294 300 ... 37 : 70 102 132 160 186 210 232 252 270 286 300 312 322 330 ... 41 : 78 114 148 180 210 238 264 288 310 330 348 364 378 390 ... 47 : 90 132 172 210 246 280 312 342 370 396 420 442 462 480 ... ... --- Pierre: Dans ce cas, je connais les deux nombres. Comme tout-à-l'heure, nous éliminons les produits P qui se trouvent plus d'une fois dans la liste. Il reste (liste exhaustive pour toutes les sommes inférieures à 200) : 11 : 18 24 28 17 : 52 23 : 76 112 27 : 50 92 140 152 176 29 : 54 100 208 35 : 96 124 216 304 37 : 160 232 336 41 : 148 288 400 47 : 172 280 496 51 : 98 144 188 308 344 608 620 644 53 : 520 592 57 : 212 260 392 656 800 59 : 220 688 65 : 244 67 : 192 472 1116 71 : 268 448 880 77 : 292 832 976 79 : 228 568 1504 83 : 316 1072 1216 87 : 332 632 836 1136 1340 1472 1880 89 : 1168 93 : 356 1040 1856 1952 95 : 1264 1984 97 : 712 1296 101 : 388 1144 2368 2440 107 : 412 2752 113 : 436 1552 117 : 452 872 1616 3392 119 : 1648 2728 121 : 904 2848 123 : 242 476 1712 3440 3776 125 : 484 1744 3904 127 : 1776 131 : 384 508 3784 4288 135 : 266 524 896 1016 1904 2996 3296 3956 4544 137 : 4672 143 : 556 2032 4120 5056 145 : 1096 2176 3616 147 : 290 1112 1496 2096 2432 3680 4280 5312 155 : 604 2224 157 : 1192 3712 161 : 628 2320 6208 6424 163 : 4192 167 : 652 2416 5080 6592 171 : 338 668 1304 2480 2888 3020 3404 3888 4448 5240 5504 6848 6968 7100 7304 173 : 2512 6976 177 : 692 3140 7232 179 : 2608 185 : 724 187 : 1432 7552 189 : 374 1448 2768 2924 5024 5624 7208 7448 7808 191 : 8128 197 : 772 2896 --- Sophie: Alors moi aussi. Ici encore, il doit rester un seul produit sur la ligne de la somme correspondant à ce qu'a Sophie. Là encore, les nombres 4 et 13 sont solution (S=17, P=52), mais ce ne sont plus les seuls. Les autres solutions sont: 4 et 61 (S=65, P=244), 16 et 73 (S=89, P=1168), 64 et 73 (S=137, P=4672). Bien évidemment, on ne tiendra pas compte des cas où l'un des nombres est plus grand que 100, par exemple pour S=127 et P=1776: les nombres seraient 16 et 111. 6. Les deux échelles. ------------------ a) Enoncé. Deux échelles se croisent dans une cour rectangulaire. Les échelles mesurent respectivement 10 et 14m. Vues de côté, elles se croisent à 5m du sol. On suppose les échelles droites et sans épaisseur. Quelle est la largeur de la cour ? b) Solution. On appelle : - BF l'échelle qui va du haut à gauche au bas à droite (B en haut à gauche) ; - EA l'échelle qui va du bas à gauche au haut à droite (E en bas) - I le point d'intersection des deux échelles, - H la projection orthogonale de I sur le sol. | |A | /| | / | | / | | / | | / | B| / | |\_ I / | | \_ / | | \_ | | /| \_ | | / | \_ | | / | \_ | E+/---|-------\+F H On pose : AF = x ; EF = y ; BE = z ; AE = a ; BF = b ; IH = c ; On applique le théorème de Pythagore dans le triangle FAE rectangle en F. AF^2 + EF^2 = AE^2. C'est à dire : x^2 + y^2 = a^2. On applique le théorème de Pythagore dans le triangle FEB rectangle en E. EF^2 + BE^2 = BF^2. C'est à dire : y^2 + z^2 = b^2. On applique le théorème de Thalès avec les parallèles (BE), (IH) et (AF). c/x + c/z = EH/EF + HF/EF = (EH + HF)/EF = 1, d'où c/z = (x-c)/x Il vient donc : x^2 - z^2 = a^2 - b^2 et z = c*x/(x-c) Et puis : x^2 - (c*x/(x-c))^2 = a^2 - b^2 ce qui conduit à x^4 - 2 * c * x^3 - (a^2 - b^2) * x^2 +2 * c * (a^2-b^2) * x - c^2 * (a^2-b^2)=0 Cette équation de degré 4 se résout par radicaux ou de manière approchée avec tout outil de calcul. On a ensuite : y = sqrt(a^2 - x^2). On a ici : a = 14, b = 10, c = 5, d'où l'équation : x^4 - 10 * x^3 - 96 * x^2 + 960 * x - 2400 = 0 Et donc : x = 12.78405 avec un outil de calcul Puis y = sqrt(a^2-x^2) = 5.706842. 7. La cuve de vin. --------------- Problème : Du vin est placé dans une cuve cylindre horizontale de longueur L est de rayon R. On mesure la hauteur h de vin dans la cuve, et on veut en déduire le volume v de vin. Une solution : On peut s'en sortir avec un peu de calcul intégral. Si l'on considère un axe vertical dont l'origine est placée à la hauteur du centre du cylindre, alors la section du cylindre à la hauteur z a pour aire a(z) = 2*sqrt(R^2-z^2)*L. Par conséquent, on a : v = int(-R..h-R, a(z)dz) L'intégrale se calcule par le changement de variable z = R*sin t. On a alors successivement, en notant x = h/R - 1 (x=-1 lorsque la cuve est vide, x=0 à mi-hauteur et x=1 quand elle est pleine) : v = int(-pi/2..Arcsin x, 2L*R^2*cos^2 t dt) v = L*R^2*int(-pi/2..Arcsin x, (1+cos 2t)dt) v = L*R^2*[Arcsin x + sin(2*Arcsin x) - (-pi/2 + sin(-pi)] Finalement, si l'on appelle v0 = pi*R^2*L le volume total de la cuve, on obtient le taux de remplissage : v/v0 = [Arcsin x + x*sqrt(1-x^2) + pi/2]/pi, ou plus simplement v/v0 = [x*sqrt(1-x^2) + Arccos(-x)]/pi Voici quelques valeurs : x -1.00 -0.75 -0.50 -0.25 0.00 0.25 0.50 0.75 1.00 v/v0 0% 7% 20% 34% 50% 66% 80% 93% 100% À noter que la formule ne s'inverse pas simplement (i.e. il n'y a pas d'expression élémentaire de h en fonction de v), donc si c'est le niveau de vin que l'on cherche, le plus simple est de résoudre l'équation numériquement. On trouve par exemple : v/v0 10% 20% 30% 40% 50% 60% 70% 80% 90% x -0.69 -0.49 -0.32 -0.16 -0.00 0.16 0.32 0.49 0.69 ======================================================================== V Questions fondamentales. ======================== 1. Les nombres premiers. --------------------- Définition : - Un nombre premier est un entier possédant exactement 2 diviseurs. (ces deux diviseurs sont donc 1 et lui-même). A noter que la définition de nombre premier exclut 1. Admettre 1 comme nombre premier rendrait faux l'important "Théorème fondamental de l'arithmétique" qui dit qu'il existe une unique manière d'écrire un nombre entier supérieur à 1 comme produit de nombres premiers (sans prendre en compte l'ordre de la multiplication). a) En existe-t-il une infinité ? Oui. En voici une démonstration par l'absurde. Noter qu'après le Théorème de Pythagore, c'est sûrement le résultat mathématique pour lequel on connaît le plus de démonstrations différentes. Supposons qu'il n'en existe qu'un nombre fini n, qui seraient p_1, p_2,..., p_n. Le produit p_1*...*p_n est divisible par chacun de ces premiers p_1,..., p_n. Cela signifie que p_1*...*p_n+1 n'est divisible par aucun d'entre eux. Donc le plus petit diviseur (excepté 1) de ce nombre, qui est forcément un nombre premier, n'est ni p_1, ni p_2,..., ni p_n. Notre liste ne peut donc pas être complète, il doit donc exister une infinité de nombres premiers. b) Quel est le plus grand que l'on connaisse ? | Actuellement (attention, les records tombent vite!), le plus grand | nombre premier connu est 2^6972593 - 1 qui a été découvert en 1999 | par Hajratwala, Woltman et Kuyrowski. Il a 2098960 décimales. Ce | nombre est le trente-huitième nombre de Mersenne. | (Source| : http://www.utm.edu/research/primes/largest.html) c) Polynôme donnant l'ensemble des nombre premiers. Il existe un polynôme à coefficients entiers à 26 variables tel que l'ensemble des nombres premiers coïncide avec l'ensemble des valeurs **positives** prises par P(a,b,c,...x,y,z) lorsque les 26 variables a,b,c,...,x,y,z parcourent N. Ce polynôme s'écrit: P(a,b,...,y,z) = (k+2) * {1 - [wz+h+j-q]^2 - [(gk+2g+k+1)(h+j)+h-z]^2 - [2n+p+q+z-e]^2 - [16((k+1)^3)(k+2)((n+1)^2) + 1 - f^2]^2 - [(e^3)(e+2)((a+1)^2) +1 -o^2]^2 - [(a^2-1)(y^2)+1-x^2]^2 - [16(r^2)(y^4)(a^2-1) +1 -u^2]^2 - [((a+(u^2) (u^2-a))^2-1)(n+4dy)^2+1-(x+cu)^2]^2 - [n+l+v-y]^2 - [(a^2-1)l^2+1-m^2]^2 - [ai+k+1-l-i]^2 - [p+l(a-n-1)+b(2an+2a-n^2-2n-2)-m]^2 -[q+y(a-p-1) + s(2ap+2a-p^2- 2p-2)-x]^2-[z+pl(a-p)+t(2ap-p^2-1)-pm]^2} Rendre P(a,...,z) positif revient à annuler simultanément chacun des crochets dans le " long " facteur {1 - [...]^2 - ... - [...]^2}. Ce facteur se réduit alors à 1, tandis que les conditions ainsi imposées à k font que le facteur " court ", à savoir (k+2), est premier. On peut lire dans " l'Abrégé d'Histoire des Mathématiques " de Jean Dieudonné (pages 232 et suivantes) l'existence d'un polynôme à 21 variables ayant la même forme et les mêmes propriétés que le polynôme déjà cité. Pour ceux qui voudraient s'initier à ce genre de mathématiques, On peut lire: -- l'article "Diophantine Decision Problems", de la regrettée Julia Robinson, pages 76 à 116 du livre "Studies in Number Theory", volume 6 des MAA Studies in Mathematics, édité (au sens scientifique du terme) par W.J. LeVeque. -- "Little book of big primes" de Paulo Ribenboim. -- "book of prime numbers records" Annexe: Dans le même ordre d'idée il existe un polynôme dont les valeurs positives donnent les nombres de Fibonacci : f(x,y) = 2 x(y^4) + (x^2)(y^3) - 2(x^3)(y^2) - (y^5) - y(x^4) + 2 y d) Nombres de Mersenne et nombres premiers. Au sujet du projet GIMPS (Great Internet Mersenne Prime Search), ce projet consiste à chercher le plus grand nombre premier sous la forme d'un nombre de Mersenne (Les nombres de Mersenne sont les nombres premiers du type 2^p - 1 où p est lui-même premier). Le 38ième nombre de Mersenne a été trouvé le 1er juin 1999 par l'équipe de Nayan Hajratwala, George Woltman et Scott Kurowski. il s'agit de 2^6972593 - 1. Ce nombre compte 2,098,960 décimales. Trouverez vous le 39ième nombre de Mersenne ? Vous pouvez vous aussi participer à ce grand projet en faisant tourner sur votre machine (quelle que soit la plateforme) le programme qui a été développé pour ce projet. C'est un programme que vous pouvez faire tourner en tâche de fond et qui utilise les cycles CPU non utilisés (donc cela ne ralentira pas votre ordinateur). C'est un projet de recherche à plusieurs qui utilise les résultats fournis par les 4200 participants pour déterminer quels nombres restent à tester,... C'est un projet qui se fait en collaboration, celui qui a la chance de trouver un nombre de Mersenne inscrit définitivement son nom dans l'histoire des maths... (et gagne aussi 10 000 $ je crois, mais j'espère que vous ne ferez pas ça pour l'argent). Plus de renseignements sur: http://www.mersenne.org/prime.htm ou en français (miroir officiel) sur: http://wwwusers.imaginet.fr/~fcrevola/mersenne/prime.htm 2. Pi. --- a) Algorithmes de calculs de décimales. C'est Archimede (en 225 avant JC) qui calcula le premier algorithme sur les décimales de Pi. Petit texte de 60 pages avec bibliographie sur les formules et algorithmes pour calculer Pi, disponible au format Postscript et Pdf : http://www.multimania.com/~gersoo/docs/pi/pi.ps.gz http://www.multimania.com/~gersoo/docs/pi/pi.pdf b) l'algorithme de Bailey, Borwein et Plouffe ? C'est pour calculer pi en base 16 (il y a une version en base 10, mais beaucoup plus lente). L'intérêt, c'est qu'on peut calculer un chiffre sans devoir déterminer tous les précédents. Voir par exemple les pages web suivantes : http://www.lacim.uqam.ca/plouffe/Simon/PourLaScience.html http://www.cecm.sfu.ca/pi/ http://www.wri.com/~victor/articles/pi/pi.html http://www.mathsoft.com/asolve/plouffe/plouffe.html http://www.joyofpi.com J.P. Delahaye a écrit un très beau livre sur le sujet: "Le Fascinant nombre Pi" aux éditions Belin - Pour la science. 3. Le grand théorème de Fermat. ---------------------------- a) Enoncé. Le " grand " ou " dernier " théorème de Fermat dit ceci: alors qu'il existe des carrés qui sont somme de deux carrés (par exemple 5² = 3² + 4², 13² = 12² + 5²), il n'existe aucun cube (non nul) qui soit somme de deux cubes (non nuls). De même, il n'existe aucune puissance quatrième qui soit somme de deux puissances quatrièmes (non nulles), etc. En général, pour n > 2, il n'existe aucun triplet (x, y, z) d'entiers non nuls, tels que x^n + y^n = z^n. C'est à dire, traduit en langage mathématique : pour n > 2 l'équation x^n + y^n = z^n n'a pas de solution entière non triviale. b) Histoire liée au théorème. Contrairement au petit théorème, il s'agit d'un résultat extrêmement difficile, dont Fermat n'a pas publié de démonstration, et qu'il n'a probablement pas démontré. Fermat n'a même jamais affirmé publiquement l'avoir démontré. Il écrivit dans une marge du livre II des Oeuvres de Diophante: " j'ai découvert une démonstration merveilleuse, mais je n'ai pas la place de la mettre dans la marge ". Le livre et cette annotation ont été publiés après sa mort, par son fils. En dépit de la simplicité de son énoncé, ce théorème est tellement difficile à prouver que les plus grands mathématiciens s'y sont cassé les dents pendant 358 ans exactement, d'après le livre de Simon Singh. On notera cependant, que : -> Euler (1707-1783) le démontre pour n = 3 et ses multiples -> Legendre (1752-1833) pour n = 5 -> Kummer (1810-1893) pour tout n tel que 2 3x+1). On >conjecture< que l'on finit toujours par trouver la valeur 1 au fil des calculs, valeur à partir de laquelle on restera bloqué dans le cycle 1-4-2-1-... Cependant, le fait que l'on retrouve toujours 1 n'a pas été démontré et même si on est presque sûr que cela est vrai, quel que soit l'entier n choisi au départ, il n'est pas exclu qu'il existe un entier n ne vérifiant pas cette propriété, d'où le nom de : >conjecture< de Syracuse. Depuis plusieurs dizaines d'années, ce problème est activement étudié par les mathématiciens, mais n'a pas encore été résolu. Les recherches ont cependant bien avancé, comme nous allons le voir plus loin. b) Une métaphore éclairante. Comment souvent, les mathématiciens, en travaillant sur ce problème, ont senti que certaines idées étaient récurrentes etont introduit un vocabulaire adapté pour décrire les phénomènes étudiées. Imaginons que l'on vérifie la propriété pour n=15. On obtient : 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1. On appelle cette suite finie d'entiers le VOL, ou la TRAJECTOIRE de 15. Il faut imaginer une représentation de cette suite sur un graphique, l'axe des abscisses figurant l'indice de chaque entier dans la suite, l'axe des ordonnées indiquant l'entier correspondant. On appelle ETAPE, un nombre de cette suite finie. Ici, par exemple, 80 est une étape du vol de 15. Si la conjecture est vraie, on remarque que la suite atteint une étape maximale, appelé ALTITUDE MAXIMALE du vol. Ici, l'altitude maximale était 160. On définit également la DUREE de chaque vol comme le nombre d'étapes à franchir avant d'arriver pour la première fois au chiffre 1, et la durée de VOL EN ALTITUDE comme la durée entre le moment où le vol commence, et celui où il repasse sous sa valeur initiale. c) Des avancées intéressantes. A partir de là, il est plus facile de comprendre les dernières avancées dans la résolution du problème. Il a été ainsi démontré que chacune des propositions suivantes était équivalente à l'énoncé de la conjecture de Syracuse elle-même : (1) Tout vol a une durée finie C'est en gros l'énoncé de la conjecture en elle-même. (2) Tout vol est de durée en altitude finie En effet, si ceci est vrai, alors on conclut sur notre problème par récurrence. Pour n=2 on finit par retomber sous 2, c'est à dire à 1. Supposons que n et tous les entiers plus petits quelui vérifient la conjecture. Démontrons que c'est alors le cas de n+1 : Le vol n+1 a une durée en altitude finie, donc, au cours des calculs, on arrive à n, ou à un entier inférieur, que l'on note i. Mais i vérifie la conjecture, donc il aboutit au cycle 4-2-1. Ainsi n+1 aboutit-il aussi à ce cycle. Réciproquement, si la conjecture est vraie, la propriété (2) est bien entendue vraie. (3) Tout vol a un nombre fini d'étapes paires (resp. impaires) On considère le vol n. Après un certain nombre d'étapes, on atteint un dernier nombre pair. On le divise par deux, et on obtient un impair. Mais, si on applique x -> 3x+1 à cet impair, on obtiendra un pair, ce qui contredit le fait qu'on ait dépassé les dernier pair, sauf si le nombre impair que l'on vient de trouver est 1. Alors on s'arrête dans les calculs, et n vérifie la conjecture, qui de ce fait est vraie. (4) Tout vol a un nombre fini d'étapes paires (resp. impaires) en altitude Démonstration analogue. Les mathématiciens désespèrent quant au fait de démontrer directement la conjecture elle-même, et pensent qu'il est moins difficile de montrer que l'une de ces propriétés, équivalentes au problème, est vraie. On sait par ailleurs montrer que la propriété est vraie pour un très grand nombre d'entiers. On considère par exemple n = 4*k + 1. En effectuant les calculs, on trouve qu'il devient 12*k+4, 6*k+2, 3*k+1, ce dernier entier étant plus petit que n. Pour n = 4*k, on descend sous n dès la première étape du calcul. De même que pour 4k + 2. Il suffirait donc de pouvoir montrer que 4k+3 a lui aussi une durée de vol en altitude finie pour conclure que la conjecture est vraie ! On peut affiner ce type de démonstration. En travaillant avec les entiers du type 65536*k + i (avec i compris entre 0 et 65535), tous les cas aboutissent sauf 1729 cas, donc il ne reste que 2,6% des nombres à étudier. Des développements plus récents ont montré que pour n assez grand, il existait une constante alpha telle que au moins n^alpha des entiers inférieurs à n possèdent la propriété de Syracuse. En 1995, J. Lagarias et D. Applegate démontrèrent ce résultat pour la constante alpha=0,81. Mais leurs calculs furent menés avec des ordinateurs et sont invérifiables à la main. d) Les records établis Les records enregistrés au fur et à mesure des recherches ont été soigneusement consignés. C'est à T. Oliveira e Silva que l'on doit les records les plus récents et les plus significatifs. Les records suivants proviennent de sa page web : Le plus grand nombre testé est : 77 * 2^50 = 86694292826882048. La conjecture a été vérifiée par deux fois avec des ordinateurs jusqu'à n = 2^51 = 2251799813685248. Le record de l'altitude maximale est tenu par le vol 82450591202377887, qui atteint l'entier : 875612750096198197075499421245450. D'autres records, datant de 1998 et sans doute améliorés depuis : Celui de vol de durée record en vol est celui du vol 100759293214567, de durée 1820 (c'est assez faible, on aurait pu croire que des entiers résisteraient plus). Enfin celui de durée en altitude record est le vol 70665924117439, dont la durée en altitude est de 1177 étapes. e) Données heuristiques et indécidabilité du problème Si l'on étudie la façon dont les entiers évoluent en terme de parité au cours d'un calcul de Syracuse, on peut avoir une idée de son temps de vol.. Ainsi, si l'on obtient souvent des nombres pairs, ils vont être divisés par deux, et on arrivera plus rapidement à 1 (en admettant qu'on arrive toujours à 1). En tenant compte du fait qu'un nombre impair donne un nombre pair et que ce dernier va être divisé par deux ensuite, et qu'il y a dans l'ensemble des entiers naturels autant de pairs que d'impairs, on estime, au moyen d'un calcul probabiliste, qu'un entier donné est en moyenne multiplié par 3/4 lorsqu'on effectue une étape du calcul. Ceci tend à confirmer la conjecture. Expérimentalement, ce résultat de 3/4 est très bien confirmé, et le modèle statistique semble performant. Cependant, certains mathématiciens sont arrivés à se poser la question de l'indécidabilité du problème. Ils ont proposé quelques extensions du problème : autoriser les entiers négatifs, ou remplacer 3x+1 quand x est impair par qx+1 avec q un entier impair donné. Pour certaines valeurs de q>3, la conjecture n'est pas vraie. Mais c'est J. Conway qui a semé le doute. Plutôt que de ce demander si un entier donné, au cours du calcul, était pair ou impair, c'est à dire avait 0 ou 1 pour reste par la division euclidienne par 2, il s'intéresse au reste par la division euclidienne par un entier p et propose alors p formules à employer pour effectuer les calculs selon ce que ce reste soit 0, 1, 2, .., ou p-1. Il a montré que si alors on étendait la conjecture de Syracuse, on arrivait à un problème indécidable. Finalement, on a vu que beaucoup de résultats tendent à nous faire penser qu'il est >presque< impossible que la conjecture soit fausse. Cependant, il est arrivé dans l'histoire que les mathématiciens aient une telle intuition très forte en faveur d'une conjecture et qu'elle soit en fait fausse. Les résultats de J. Conway montrant que des problèmes très similaires sont indécidables incitent donc à la prudence ! f) Bibliographie "La conjecture de Syracuse", par Jean-Paul Delahaye in: _Pour La Science_ N°247 de mai 1998. Et sur le web : "On the 3x+1 problem" par Eric Roosendaal à l'adresse : http://oldpersonal.computrain.nl/eric/wondrous/ "3x+1 search results" par T. Oliveira e Silva http://www.inesca.pt/~tos/3x+1.html 5. Les cardinaux des ensembles infinis - Partie I. ----------------------------------------------- a) Avertissement Le sujet est vaste et peut intéresser des gens de niveaux divers (à partir du lycée et bien au-delà). C'est pourquoi cet article est découpé en 2 parties. La première s'adresse au niveau pré-bac, la seconde est accessible à partir du DEUG, environ. Dans la première partie, l'accent est mis sur la "vulgarisation", parfois au détriment de la rigueur : pour éviter des complications techniques, certaines démonstrations sont "un peu fausses", tout en donnant l'idée principale de la méthode. Chaque fois que c'est le cas, c'est signalé, et on peut se reporter à la seconde partie pour trouver une démonstration (à priori) rigoureuse. La seconde partie complète la première, avec des outils plus abstraits et plus puissants. Elle s'efforce à la rigueur, mais elle peut comporter des erreurs ou imprécisions. Merci enfin à David Madore (David.Madore@ens.fr), spécialiste du sujet, d'avoir corrigé et complété une première mouture de cet article. Merci également à tous les lecteurs de fr.sci.maths qui m'ont indiqué des corrections diverses. Rappel : N : ensemble des entiers naturels = {0,1,2,3,...} Z : ensemble des entiers relatifs (signés) = {...,-1,0,1,...} Q : ensemble des nombres rationnels (fractions) R : ensemble des nombres réels C : ensemble des nombres complexes L'étoile signifie que l'ensemble est privé de 0 (N*={1,2,3,...}). Voici d'abord les résultats essentiels, qui seront suivis par quelques explications : _ N, Z, Q ont autant d'éléments _ R, C ont autant d'éléments _ Les 3 premiers ont moins d'éléments que les 2 derniers. La notion de cardinal étend la notion de nombre aux infinités, de façon à ce que l'on puisse comparer les ensembles infinis. Voici comment. b) Cardinal d'un ensemble fini Pour un ensemble fini, le cardinal est une notion intuitive, c'est simplement le nombre d'éléments de l'ensemble. Il appartient à N. Ex : Card {1,2,3} = 3 = Card {6,15,28} (*) Opérations sur les cardinaux (finis) : -------------------------------------- (1) Si A et B sont deux ensembles finis *disjoints* alors Card (A Û B) = Card A + Card B où Û désigne l'union disjointe. Ex : A = {1,2,3} Card A = 3 B = {8,9} Card B = 2 A Û B = {1,2,3,8,9} Card(A Û B) = 5 = 3+2. (2) Si A et B sont deux ensembles finis, alors Card (A × B) = (Card A) . (Card B) où A × B désigne le produit cartésien des ensembles A et B. Ex : A = {1,2,3} Card A = 3 B = {a,b} Card B = 2 A × B = { (1,a), (1,b), (2,a), (2,b), (3,a), (3,b) } Card (A × B) = 6 = 3x2. (3) Si A est un ensemble fini on note P(A) l'ensemble des parties de A, c'est a dire l'ensemble des sous-ensembles de A. alors Card P(A) = 2^(Card A) En effet : pour constituer une partie B de A, il y a un choix à faire pour chaque élément de A : soit on le met dans B, soit on ne l'y met pas (2 possibilités). S'il y a n éléments dans A, cela donne 2^n possibilités pour B, soit 2^n parties différentes. Ex : A = {1,2,3} Card A = 3 P(A) = { Ø, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3} } Card P(A) = 8 = 2^3 Ce sont ces propriétés (1), (2), (3) qu'on va vouloir généraliser aux ensembles infinis. ----- Pour un ensemble infini, l'intuition ne s'applique plus : il faut recourir à des définitions formelles. C'est Cantor qui, le premier, a fourni un système cohérent permettant de traiter les ensembles infinis. c) Définition rigoureuse d'un ensemble infini : Une bijection f entre 2 ensembles E et F est une application qui fait correspondre à chaque élément de E un unique élément de F et inversement. S'il existe une bijection entre E et F, on dit que E et F sont équipotents et on note : E ~ F. Un ensemble est dit fini s'il est en bijection avec un ensemble A_n = {1, 2, 3, ..., n} avec n un entier naturel (et A_0 = Ø). Alors Card(E) = n, et on retrouve la notion intuitive. Un ensemble E qui ne peut pas être mis en bijection avec un tel ensemble A_n est dit infini. Ex : N est un ensemble infini. d) Cardinal d'un ensemble infini : On étend la notion de cardinal aux ensembles infinis de la façon suivante (schématiquement ; pour plus de rigueur voir partie II) : 1. Si 2 ensembles sont équipotents (en bijection), on dit qu'ils ont le même cardinal. 2. On dit que Card E <= Card F si E a même cardinal qu'une partie de F. En particulier, si un ensemble infini E est inclus dans un ensemble (infini) F alors Card E <= Card F (inégalité large). Ex. (règle 1) : Card Z = Card N car il existe (au moins) une bijection de N dans Z, qu'on peut expliciter : g : n --> n/2 si n est pair n --> -(n+1)/2 si n est impair ce qui donne 0 --> 0 1 --> -1 2 --> 1 3 --> -2 ... Ex. (règle 2) : Card N <= Card Z <= Card Q <= Card R <= Card C. e) Quelques résultats sur les ensembles dénombrables On a vu Card N = Card Z. Établissons quelques autres résultats : (*) Card N = Card (N^2) On peut en effet compter les éléments de N^2 = { (a,b) | a,b dans N }. Une bijection possible de N^2 dans N est le "comptage en diagonale" : (0,0) --> 0 (1,0) --> 1 (0,1) --> 2 (2,0) --> 3 (1,1) --> 4 (0,2) --> 5 ... (on compte les points de N^2 selon les diagonales bas-droite -> haut gauche, en s'éloignant de l'origine). On peut même expliciter la bijection : (p,q) --> (p+q).(p+q+1)/2 + q De même, on a Card (Z^2) = Card Z. (*) Card (Z) = Card Q Essentiellement, une fraction p/q est un couple d'entiers relatifs (p,q). Cette égalité n'est donc pas particulièrement surprenante quand on a admis Card (Z^2) = Card Z. Formellement, la démonstration est un peu technique : elle est donc donnée dans la deuxième partie. On a donc : Card N = Card Z = Card Q. Ce cardinal est noté aleph_0. (aleph est la première lettre de l'alphabet hébreu). Tous les ensembles infinis qui ont le même cardinal que N sont dits dénombrables. Au sens large, "dénombrable" signifie aussi "fini ou dénombrable". Enfin, un ensemble qui n'est ni fini ni dénombrable est dit... indénombrable. f) Quelques résultats sur les ensembles indénombrables Plaçons nous maintenant dans les réels. (*) Card [0,1] = Card [0,2] = Card [a,b] = ... Il est facile de trouver une bijection de [0,1] dans [0,2] : k : x --> 2x par exemple. De même, on peut toujours trouver une bijection entre 2 intervalles de R, ouverts ou fermés. Tous les intervalles de R ont donc le même cardinal. (*) Card (a,b) = Card R (a,b) désigne l'intervalle, sans se préoccuper de l'inclusion ou non des bornes. La fonction tangente, par exemple, fournit une bijection de ]-pi/2,pi/2[ dans R. En appliquant ce qui précède, tout intervalle de R a le même cardinal que R. (*) Card ([0,1[^2) = Card [0,1[ En effet on peut expliciter une bijection de [0,1[^2 dans [0,1[ : Soit (a,b) dans [0,1[^2. Écrivons leur développement décimal : a = 0, a1 a2 a3 a4 ... b = 0, b1 b2 b3 b4 ... formons alors c = 0, a1 b1 a2 b2 a3 b3 a4 b4 ... N'est-il pas alors clair que la fonction l : (a,b) --> c est une bijection de [0,1[^2 dans [0,1[ ? [en fait, pas tout a fait : il y a une lacune, expliquée dans la seconde partie, mais ça ne change pas le résultat] Grâce à ce qui précède on déduit que : Card R = Card [0,1[ = Card ([0,1]^2) = Card R^2. On peut démontrer la même chose avec n'importe quel exposant à la place de 2. (*) Card C = Card R En effet, les fonctions partie réelle et partie imaginaire d'un complexe fournissent une bijection évidente de C dans R^2. Avec ce qui précède on a donc Card C = Card R^2 = Card R. g) Rapport dénombrable/indénombrable On va maintenant voir que R n'est pas dénombrable. Pour simplifier, on va montrer que [0,1[ n'est pas dénombrable ; ce qui implique, bien sûr, que R ne l'est pas. Supposons le contraire : on peut alors énumérer [0,1[, c'est-à-dire qu'il existe une suite (u_n), n dans N, qui contient tous les réels de [0,1[. Écrivons le développement décimal (par exemple) des premiers termes de (u_n) en notant u_n,i le i-ème chiffre après la virgule de u_n : u_1 = 0, u_1,1 u_1,2 u_1,3 u_1,4 ... u_2 = 0, u_2,1 u_2,2 u_2,3 u_2,4 ... ... u_n = 0, u_n,1 u_n,2 u_n,3 u_n,4 ... ... On forme maintenant le nombre v s'écrivant : v = 0, u_1,1 u_2,2 u_3,3 u_4,4 ... u_i,i ... (on prend les chiffres de la diagonale principale ci-dessus) On forme enfin le nombre w en remplaçant chaque chiffre de v par son prédécesseur (et 0 par 8) : w = 0, w_1 w_2 w_3 w_4 ... avec : w_i = 8 si u_i,i = 0 w_i = u_i,i - 1 sinon Alors le nombre w, qui est bien défini, n'est pas dans la liste des valeurs parcourues par (u_n). En effet : w_1 (le premier chiffre de w après la virgule) est différent de u_1,1 (le premier chiffre de u_1 après la virgule) donc w <> u_1. w_2 <> u_2,2 donc w <> u_2 ... w_n <> u_n,n donc w <> u_n pour tout n. On a donc construit un réel de [0,1[ qui n'est pas dans (u_n) : contradiction avec l'hypothèse. Une telle suite u_n parcourant tous les réels de [0,1[ n'existe donc pas, donc [0,1[ est indénombrable. La technique qui nous a permis de le montrer est classique, et connue sous le nom de "Procédé diagonal de Cantor". h) Conclusion : Tout ceci nous permet d'écrire : Card N = Card Z = Card Q < Card R = Card C. Pour d'autres développements, et des justifications plus rigoureuses, voir la partie II. 6. Les cardinaux des ensembles infinis - Partie II. ------------------------------------------------ a) Autre définition rigoureuse d'un ensemble infini : Une définition équivalente (moyennant l'axiome du choix) à celle de la première partie est : Un ensemble E est dit infini si on peut trouver une bijection entre lui-même et une de ses parties (strictes) F, ie : F inclus dans E, F <> E, F ~ E. Ex : N est en bijection avec N*, par la fonction f : n --> n+1 ainsi, N est infini b) Cardinal d'un ensemble infini : La façon parfaitement rigoureuse de définir le cardinal pour un ensemble infini s'appuie sur le théorème de Cantor-Bernstein : Thm : Soient A et B deux ensembles (finis ou infinis). Si A s'injecte dans B et B s'injecte dans A, alors A et B sont équipotents. (la démonstration est facile dans le cas fini, un peu moins dans le cas général). Ce théorème justifie les écritures : Card(A) = Card(B) si A et B sont équipotents Card(A) <= Card(B) si A s'injecte dans B En effet, on peut alors appliquer la règle d'antisymétrie : si n <= m et m <= n alors n = m. Écrire cette règle avec les cardinaux infinis est une simple ré-écriture du théorème de Cantor-Bernstein. D'autre part, on a l'équivalence (moyennant l'axiome du choix) : - A s'injecte dans B - B se surjecte sur A et en notant Card(B) >= Card(A) si B se surjecte sur A, on reste cohérent en manipulant les cardinaux. Pour la culture (merci à David Madore) : Si A et B sont deux ensembles quelconques, alors soit A s'injecte dans B (ie Card(A) <= Card(B)), soit B s'injecte dans A (ie Card(B) <= Card(A)). En d'autres termes : les cardinaux forment une classe "totalement ordonnée". c) Quelques précisions sur les ensembles dénombrables (*) Card (Z^2) = Card Q On a une injection évidente f : Q --> Z^2 : f(p/q) = (p,q) avec p,q premiers entre eux et q>0 [on peut rajouter f(0)=(0,1) pour être parfaitement rigoureux] Évidemment, ce n'est pas une bijection : (4,6) par exemple n'a pas d'antécédent, puisque f(4/6) = (2,3). On a donc Card Q <= Card(Z^2). D'autre part, on a vu dans la première partie : Card (Z^2) = Card Z. Or Z s'injecte trivialement dans Q : Card Z <= Card Q. De ces deux inégalités on déduit Card (Z^2) = Card Q, alors qu'il serait fastidieux d'exhiber une bijection explicite entre Q et Z^2. d) Quelques précisions sur les ensembles indénombrables (*) Card ([0,1[^2) = Card [0,1[ En fait, l'application l donnée dans la partie I n'est pas vraiment une bijection, mais seulement une injection. Cela est dû à l'existence de deux écritures décimales distinctes pour les décimaux : l'une avec un nombre fini de chiffre (ex : 1,23), l'autre avec un nombre infini de chiffres (ex : 1,2299999...) [Voir la FAQ 0,999...=1]. En conséquence, le nombre 0,50595959... par exemple n'a pas d'antécédent puisque: l(0,555... , 0,099...) = l(0,555.. , 0,1) = 0,51505050... Cependant, ça suffit : l nous fournit une injection de [0,1[^2 dans [0,1[, et l'injection réciproque est triviale. En appliquant le théorème de Cantor-Bernstein on peut donc conclure en toute rigueur que Card([0,1[) = Card([0,1[^2). La généralisation à Card R = Card (R^2), se fait toujours comme indiqué dans la première partie. e) Rapport dénombrable/indénombrable Voici une démonstration plus indirecte du fait que R est indénombrable, mais qui a l'avantage de préciser le rapport entre les 2, à savoir R ~ P(N), l'ensemble des parties de N. (*) Soit E un ensemble. P(E) n'est jamais équipotent à E. En voici une (jolie) démonstration par l'absurde. Supposons qu'il existe une bijection h : E --> P(E) Pour tout x dans E, h(x) est un sous-ensemble de E. Notons F = { x dans E | x n'est pas dans h(x) }. Par construction, F est une partie de E, donc F est dans P(E). Comme h est une bijection, F a un antécédent dans E, ie : il existe y dans E tel que h(y) = F = {x dans E | x n'est pas dans h(x)} Alors : - si y est dans F, par définition de F, y n'est pas dans h(y)=F. Absurde. - si y n'est pas dans F, par définition de F, y est dans h(y)=F. Absurde aussi. C'est donc l'hypothèse d'existence de la bijection h qui est fausse. Cqfd. (*) Card P(N) = Card R On constitue donc l'application p : P(N) --> R de la façon suivante. Soit E dans P(N). E est donc un sous-ensemble (fini ou infini) de N. On forme un nombre d écrit en base 2 de la façon suivante : d = 0, d0 d1 d2 d3 d4 d5... où dn = 1 si n est dans E, 0 sinon On a alors d dans [0,1], de façon claire (d=0 si E=@, d=1 si E=N). [On peut définir p de façon plus concise : p(E) = \somme_{n dans E} 2^-(n+1)] La fonction p : E --> p(E)=d est alors une surjection de P(N) dans R. [Tout réel r de [0,1] est atteint, et pour connaître son antécédent, il suffit d'écrire le développement binaire de r. En revanche, p n'est pas une bijection, en raison de l'existence de 2 développements binaires, comme pour les développements décimaux.] D'autre part, si on fabrique l'application q comme p, mais en considérant que cette fois d est écrit en base 3 (ou 10, ou n>2), alors l'application q est une injection de P(N) dans R. [Tous les réels ne sont pas atteints, mais chaque réel atteint a un antécédent unique.] P(N) se surjecte et s'injecte à la fois dans R, donc P(N) ~ R : Card P(N) = Card R Par généralisation du cas fini, on écrit : Card R = Card P(N) = 2^(Card N) = 2^(aleph_0) (*) Card N < Card R En effet, puisque N est inclus (donc s'injecte) dans R,Card N <= Card R. De plus, on vient de montrer que Card R = Card P(N), et que P(N) n'est pas équipotent à N. Donc Card N < Card R. f) Hypothèse du Continu... On définit aleph_1 comme étant le plus petit cardinal strictement supérieur à aleph_0 (pour une définition plus rigoureuse de aleph_1, voir l'article de David Madore : http://www.eleves.ens.fr:8080/home/madore/w/ordinals/ordinals.html) Le fait de savoir si Card R = aleph_1 est indécidable d'après la construction de R seule, c'est à dire qu'on peut arbitrairement décider que oui ou non. Habituellement, on fait l'hypothèse que c'est bien le cas (hypothèse du Continu) : aleph_1 = Card R. En termes plus simples, l'hypothèse du Continu dit que : toute partie de R est soit au plus dénombrable, soit équipotente à R. En termes intuitifs (!) : il n'existe pas d'ensemble "strictement plus gros" que N mais "strictement plus petit" que R. g) Opérations sur les cardinaux Toutes les opérations valables avec les cardinaux finis, sont extensibles aux cardinaux infinis, mais l'intérêt est moindre : Si A ou B est infini : Card (A Û B) = Card A + Card B = Max (Card A , Card B) Card (A × B) = Card A . Card B = Max (Card A , Card B) Card (P(A)) = 2^Card(A) L'hypothèse du Continu "dit" ainsi que aleph_1 = 2^aleph_0. h) Références -- Initiation à la théorie des ensembles, J. Breuer Dunod, 1961 -- Théorie axiomatique des ensembles, Jean-Louis Krivine, Presses Universitaires de France, 1972 (niveau maîtrise) voir aussi : -- Théorie des ensembles, Jean-Louis Krivine, Vuibert, 1998 7. Qu'est-ce que le nombre e ? --------------------------- a. le point de vue Néperien. On pose ln(e) = 1. Il suffit d'expliquer comment on définit naturellement la fonction logarithme, et tu comprendras pourquoi e est e. La fonction ln se définit (à une constante près) par la propriété : ln(xy)=ln(x)+ln(y). En dérivant cette relation, on vérifie que : y ln'(xy))= ln'(x). Donc : ln'(y) = ln'(1)/y. On définit donc la fonction ln comme étant LA SEULE FONCTION dérivable telle que : 1 ln(xy)=ln(x)+ln(y) 2. ln'(1) = 1. Puis on définit e par : ln(e)=1. L'intérêt de cette définition de la fonction ln : on a de jolis développements en série entière, la fonction exp, inverse de la fonction ln vérifie : y'=y et y(0)=1 (c'est un théorème). Tiens, d'ailleurs, on peut aussi décider de définir d'abord la fonction exp. Les théorèmes deviennent des définitions et les définitions deviennent des théorèmes : b. Le point de vue de Cauchy: exp est la solution de l'équation différentielle y'=y, vérifiant : exp(0) = 1. Suivant ce point de vue, on définit e=exp(1) et on définit ln comme étant la fonction inverse de la fonction exp (de sorte que ln(e)=1). On a alors le théorème : 1. ln(xy)=ln(x)+ln(y) 2. ln'(1) = 1. c. Le point de vue Théologique e^(i\pi) + 1 = 0. Il suffit de définir la fonction puissance. Si a est un réel positif, on définit a^n pour tout entier naturel n, puis a^(1/p) pour tout entier naturel p (c'est le nombre b tel que b^p=a. Ce nombre existe car l'application b->b^p est un bijection) donc a^q pour tout nombre rationnel positif q, puis a^x pour tout réel positif x (par passage à la limite). On s'aperçoit que la fonction que l'on définit ainsi admet un prolongement analytique : z dans C -> a^z dans C, on démontre qu'il existe une infinité de réels positifs tel que e^(i\pi) + 1 = 0 et on définit e comme le plus petit réel positif tel que : e^(i\pi) + 1 = 0 Ensuite, on peut définir la fonction exponentielle par exp(x)=e^x, et les définitions du second point de vue deviennent des théorèmes (alors qu'en utilisant la définition du second point de vue (convenablement étendue aux nombres complexes), l'équation e^(i\pi) + 1 = 0 est un théorème). ======================================================================== Les autres parties de cette FAQ se trouve dans les documents intitulés : [FAQ] fr.sci.maths - partie 1/3 [FAQ] fr.sci.maths - partie 3/3 Ce document est disponible sur le forum fr.sci.maths ou à l'adresse : http://www.usenet-fr.net/fur/maths/maths-faq.html http://www.usenet-fr.net/fur/maths/maths-faq-3.html .