25 août 2007

Problèmes antiques

Allez, munissez-vous tous d'un compas, d'une règle et d'un crayon, nous montons dans le bus magique pour l'Antiquité ! Dites au revoir aux fractales, à la théorie des groupes et aux puzzles un brin trop compliqués, là ou nous allons, tout ça n'a pas encore été inventé... La Grèce antique, 5eme siècle avant J-C. On commence à parler de nombres premiers et même d'intégrale, mais ce qui nous intéresse aujourd'hui, ce sont les problèmes de géométrie de l'époque.

J'espère que tout le monde a bien pris sa règle et son compas. Ouvrez bien vos esgourdes, les questions commencent ! Pour plus de compréhension, j'ai écrit les question en français, et non en grec antique.

Problème numéro 1 : la trisection de l'angle
Sur votre feuille, tracez un angle quelconque. Maintenant, à l'aide de votre règle et de votre compas, vous devez diviser cet angle en trois parties égales.

trisection

Problème numéro 2 : la quadrature du cercle
Ce petit problème est un peu plus compliqué. Après avoir tracé un cercle quelconque sur votre feuille, vous devez construire un carré de la même aire que ce cercle.

quadrature

Problème numéro 3 : La duplication du cube
(Cadre historique : pour faire cesser la peste à Athènes, l'oracle de Delphes demande aux Athéniens de doubler l'autel cubique consacré à Apollon)
Après avoir dessiné un cube sur votre feuille (enfin, son patron), vous allez devoir construire le cube qui possède le volume double du premier.

duplication

La réponse à ces questions... Après la page de publicité.


=== PubL ===

Ne ratez pas l'article de Choux Romanesco, Vache qui rit et intégrale curviligne de la semaine prochaine, qui donnera les solutions des trois grands problèmes antiques : trisection de l'angle, quadrature du cercle et duplication du cube !

=== /PubL ===



Avant de passer aux réponses, un petit point d'histoire tout de même. Ces trois problèmes de l'antiquité sont appelés les "trois grands problèmes de l'Antiquité" (Nom pas très original, j'admets, même si parfois, on y ajoute un quatrième problème, celui de construire un polygone régulier à n côtés). En fait, les anciens n'ont jamais réussi à trouver leur solution avec leur règle et leur compas, et c'est seulement grâce au développement de l'algèbre que les solutions ont été trouvées.


Les solutions sont simple : il n'y a pas de solution. (Désolé de l'annoncer comme ça, j'espère que vous n'avez pas trop cherché longtemps quand même...)

Il est tout à fait impossible de dupliquer un cube, de trisecter un angle ou de quadraturer un cercle seulement avec une règle et un compas. Pourquoi ? Je vais tâcher d'y répondre tout de suite.


Avant de savoir ce que l'on ne sait pas faire, commençons plutôt par ce que l'on sait faire avec une règle et un compas.

* J'espère que tout le monde sait tracer la parallèle à une droite passant par un point donné, ainsi que la perpendiculaire à une droite passant par un point donné, avec une règle et un compas (pas besoin d'équerre) :

parralperp

* Plus intéressant : on peut facilement faire des additions et des soustractions de longueurs :

addisoustr

* Et encore plus chouettes, grâce au théorème de Thalès, on peut effectuer des multiplications et des divisions :

multdivis

* Et le plus chouette encore, l'extraction de racine carrée ! Dans l'image ci-dessous, y=√x :

raccarre

Et en fait, c'est a peu près tout ce que l'on peut faire avec des longueurs : des additions, des soustractions, des multiplications, des divisions et des extractions de racines carrées. Pourvu qu'on ait une longueur unité, on peut construire tout un tas de nombres avec ça. On appelle "ensemble des nombres constructibles" toutes les longueurs que l'on peut construire à partir d'un segment unité, d'une règle et d'un compas. Si deux nombre sont dans cet ensemble, alors leur somme, leur différence, leur produit et leur quotient appartiennent à cet ensemble : on dit que l'ensemble des nombres constructibles est un "corps". De plus, si un nombre appartient à cet ensemble, alors sa racine carrée y est également : on peut dire que l'ensemble des nombres constructible est un corps stable par racine carrée.

Dans les différentes opérations sur les nombres montrées plus haut, je n'ai montré de formidable que l'extraction de racine carrée : pas de racine cubique ou cinquième, par exemple. Et pour cause : c'est impossible. A partir d'un segment unité, on ne peut construire à la règle et au compas que des sommes, différences, produit, quotient et racines carrées de nombre : le corps des entiers constructibles et le plus petit corps stable par racine carrée (Autrement dit : l'ensemble des nombres que l'on peut écrire avec des  +, des -, des ×, des ÷ et des √)

On peut voir la même chose d'un autre point de vue : un nombre ne peut être construit à la règle et au compas à une seul condition (qui n'est pas suffisante) : Il doit être la racine d'un polynôme (A coefficients entiers) qui a pour degré une puissance de 2 . Inversement, un nombre qui n'est pas racine d'un polynôme ayant pour degré une puissance de 2 n'est pas constructible à la règle et au compas. (À peu de choses près, c'est le théorème de Wantzel) C'est grâce à cette dernière version du théorème de Wantzel que l'on va pouvoir démontrer l'impossibilité de résolution des 3 grands problèmes antiques.

La duplication du cube

Si on revient à notre problème numéro 3 de duplication du cube. Si on imagine que l'arrête du cube de base mesure 1, son aire vaudra 1. Il faut alors construire un cube ayant pour volume 2, et donc, d'arête égale à  raccub2 . Le problème, c'est que ce nombre est la solution de l'équation x3-2=0, qui est une équation de troisième degré (et 3 une puissance de 2). En conclusion, le nombre raccub2 n'est pas un nombre constructible à la règle et au compas, la duplication du cube sera alors impossible.

La quadrature du cercle

Si notre cercle a un rayon d'une unité, son aire vaudra π (pi). Le carré qu'il faudra alors construire aura alors pour côté √π. Comme on sait extraire des racines carrées, ce n'est pas un problème de construire √π si on sait construire π... Et là est le hic, puisque π est un nombre transcendant, c'est à dire qu'il n'est la racine d'aucun polynôme à coefficient rationnel, donc encore moins d'un polynnôme ayant pour degré une puissance de 2. Pi n'est pas constructible, la quadrature du cercle est donc impossible !

Trisection de l'angle
(Là, l'explication est déjà un peu plus ardue, et pas très précise, mais c'est l'idée)

Si notre angle de départ est α, on peut très facilement construire cos(α) (On trace le cercle unité, et on prend le projeté orthogonal de l'intersection cercle/droite sur l'autre droite). Pour trouver la trisection du cercle, il va falloir réussir à tracer cos(α/3).

En s'amusant un peu avec nos chères relations de trigonométrie, on trouve que cos(α)=4.cos3(α/3)-3.cos(α/3), soit une équation de la forme a=4x3-3x. L'équation à résoudre est alors du troisième degré, et sauf dans de rares cas, les solutions seront pleines de racines cubiques. En gros, cos(α/3) n'est pas un nombre constructible, et c'est bien dommage !

Bref, à la règle et au compas, ces trois problèmes de la Grèce antique sont absolument impossible. Mais il existe heureusement d'autres méthodes astucieuses !... (Suspens jusqu'à la semaine prochaine...)


Source :
Beaucoup trop de wikipédia (dont sont issues toutes les images de la deuxième partie)
Et un peu de l'encyclopédie de Gérard Villemin.

Posté par El Jj à 10:03 - Commentaires [7] - Permalien [#]
Tags : ,


20 août 2007

Jouons avec des allumettes

A cause d'un grand nombre de problème, l'article du jour qui aurait pu parler de série convergente, de crible d'Erathostène ou de géométrie grecque sera remplacée par une curiosité géométrique qui ne casse pas des briques.
Merci de votre attention.

Aujourd'hui, nous allons jouer avec des allumettes et un peu de colle !

Voici un triangle, réalisable en allumettes collées :

triangle

Ce triangle, équilatéral de son état, est parfait : il est impossible de le déformer sans changer la longueur de se côtés.

Maintenant, prenons ce carré, également réalisable en allumettes :

carre

Ce carré, carré de son état, a cependant un peu la bougeotte : impossible de le fabriquer en allumettes collées sans se retrouver avec un losange. Ce carré n'est pas rigide ! Il faut le rigidifier en ajoutant d'autre allumettes !

La solution est simple, il suffit d'ajouter une allumette plus longue en diagonal, le carré sera rigidifié, et tout ira mieux dans le meilleur des mondes !

carre2

Mais c'est évidemment de l'anti-jeu, il faudrait réussir à le rigidifier avec seulement des allumettes de même taille.
Le but du jeu est simple : comment rigidifier ce carré en collant d'autres allumettes de même taille ?

Allez, cherchez, bandes de moule, avant de regarder la solution !


Et comme un seul problème d'allumettes, ça ne suffit pas en voici un deuxième, beaucoup plus stupide que le premier :
Comment, en déplaçant une seule et unique allumette, obtenir un carré ?

allu

(Il y a deux solutions possibles, j'attends les deux !)


Sources :
Le site de Gérard Villemin, donné en lien un peu plus haut
Et même pas Wikipédia !

Posté par El Jj à 00:50 - Commentaires [9] - Permalien [#]
Tags : ,

11 août 2007

Farey, Ford et les autres

PickoverPetit

- Dis, Jj, c'est quoi ton avatar MSN ?
- ...
- Jj, c'est quoi ton avatar MSN ?
- ...
- Jj, c'est quoi l'hypothèse de Riemann ?
- Et bien, mon avatar MSN, c'est l'adaptation des cercles de Ford aux fractions complexes... Quelques explications sont nécessaires, semble t'il...

Sir John Farey

Farey, géologue-mathématicien-écrivain anglais de son état, n'a pas vraiment découvert les suites de Farey portant aujourd'hui son nom, il a simplement fait quelques conjectures à son propos, mais Cauchy qui passait par là lui a donné tout le mérite.

Bref, une suite de Farey (d'ordre n), qu'est ce que c'est ? En termes simples, ce sont toutes les fractions irréductibles entre 0 et 1 que l'on peut écrire avec des nombres entre 0 et n.

Par exemple, on a
F3 = {01, 13, 12, 23, 11}
F4 = {01, 14, 13, 12, 23, 34, 11}
etc.

Quelques propriétés intéressantes :

* Quand on prend deux termes consécutifs de la forme ab < cd, on a toujours bc-ad=1

* Quand on prend trois termes consécutifs de la forme ab < pq < cd, on trouve que pq est le médian de ab et de cd :

median

C'est d'ailleurs cette deuxième propriété que John Farey n'a jamais su démontrer.

Lester Ford (père)

Mais les suites de Farey sont très jolies, mais il leur manque un petit quelque chose : une représentation graphique. C'est là que Ford, mathématicien américain, arrive, et propose de représenter chaque fraction par un cercle, que l'on appellera "cercle de Ford".

Le cercle associé à une fraction p/q irréductible, c'est le cercle de centre (p/q, 1/2q²) et de rayon 1/(2q²).

On peut alors représenter les différentes suites de Farey avec ces cercle de Ford.
Ainsi, la suite F7 se représente ainsi (J'ai omis de représenter les cercles correspondant à 0/1 et 1/1, ils sont trop gros):

ford

Et le plus étonnant dans tout ça, c'est que chaque cercle est tangent à son voisin ! On peut toujours aller plus loin, et représenter la suite de Farey à l'infini, ce qui donne une très jolie fractale. Chaque cercle embrasse alors une infinité d'autres cercles. :

ford

   

Clifford A. Pickover
Et c'est là que Pickover, chroniquer scientifique et inventeur des nombres vampires, arrive, et propose de remplacer les cercles par des sphères.

ford3D


Mais comme ça n'apportait pas grand chose, il s'est dit qu'il serait intéressant d'adapter les fractions des suites de Farey en fractions complexes (Si vous ne connaissez rien aux complexes, cette partie là sera encore plus difficile à suivre)

Maintenant, au lieu de prendre toutes les fractions irréductibles de la forme p/q, on prend toutes celles de la forme (p'+ip")/(q'+iq") (p', p", q' et q" sont tous entiers). Un petit calcul permet de trouver que cette fraction est de la forme a+ib, avec a et b étant des fractions réelles.
Ensuite, il n'y a plus qu'à les représenter dans le plan complexe avec des sphères de la même façon que pour les cercles de Ford.
Pour une fraction complexe p/q, on lui associera la sphère de rayon 1/(2qq) (q étant le conjugué de q) et touchant le plan complexe à la position p/q. Une fois que l'on a fait tout ça avec un ordinateur disposant de bons logiciels, on trouve ceci :

fordb

Et c'est à ce moment là que l'on peut se dire que même si on peut trouver que tout ça ne sert à rien, c'est quand même très joli !


(Mais en vrai, les suites de Farey ont une importance dans le problème de l'hypothèse de Riemann, problème du prix du millénaire à un millions de dollars)


Sources :
Le baiser infini (d'où proviennent la plupart des images de cet article)
Wikipédia (On ne change pas une équipe qui gagne)

Posté par El Jj à 16:13 - Commentaires [4] - Permalien [#]
Tags : , ,

05 août 2007

Le Ernõ's cube !

Petite devinette d'une difficulté extrême, surtout quand on vient de lire le titre de cet article :
Quel est l'objet cubique qui possède 54 facettes, 26 petits cubes et qui, selon la théorie des groupes, possède un ensemble de configurations qui constitue un groupe fini ?
Indice supplémentaire : c'est un casse tête que l'on peut résoudre avec son nez :

Bien que datant de 1974, le casse-tête créé par Ernõ Rubik ravi toujours autant les mathématiciens d'aujourd'hui. Non seulement, c'est un très bon support pédagogique pour la théorie des groupes, mais surtout, la recherche mathématique est active sur le sujet. C'est en effet en juin dernier que l'on a eu la réponse fondamentale à la question "En combien de coup au maximum peut-on résoudre n'importe quel Rubik's cube ?".

26.

La réponse, donnée en juin, c'est 26. (Quand on parle d'un "coup", c'est une rotation de un quart de tour d'une tranche du cube (un demi tour, c'est alors 2 coups)). Et cette réponse n'est pas encore définitive, il se peut que ce nombre soir revu à la baisse prochainement (le résultat, obtenu en 63h avec de bons ordinateurs -  7 Tbits de données temporaires - a été obtenu à partir de pré-calculs sur les différentes familles de configurations différentes du cube).

Histoire de répondre à un sms que l'on m'a envoyé en début de semaines, sachez qu'un Rubik's cube peut prendre 43 252 003 274 489 856 000 positions différentes (8! x 37 x 12! x 210). Celà peut paraître peu par rapports aux chiffres donné dans mon dernier article, mais c'est quand même énorme !

Une autre question très fréquemment posée : "Comment résoudre ce $£¤%# de casse-tête ?". La réponse du flemmard est de ne pas toucher y toucher, et de le poser fièrement résolu au dessus de la cheminée. Mais il existe cependant des techniques de résolution, comme la technique couche par couche, ou la technique de Petrus... L'algorithme ultime (celui qui donne le chemin à suivre pour terminer le cube en un minimum de mouvements) reste cependant à trouver... Les chercheurs cherchent...

Mais il n'y a pas que le 3×3×3 Rubik's cube dans la vie ! Il y a toujours les variantes sur le nombre de cubes par face : la version 2×2×2 (Pocket cube), la 4×4×4 (Rubik's Revenge), la 5×5×5 (Professor's cube), voire 20×20×20. On peut ensuite jouer sur la forme, avec le Pyraminx ou le Skewb. Et enfin, mon alternative préférée, celle en 4 dimensions : le magic cube 4D !

Et pour en finir avec ce petit tour d'horizon du Rubik's Cube, sachez que le record de vitesse de résolution de Rubik's cube est de 9,88 secondes, détenu par le français (Cocorico !) Thibaut Jacquinot lors du Spanish Open 2007 le 5 mai 2007.

Et le record à une main est de 17,9 secondes...

Tout ça pour dire que la recherche en mathématiques avance. Cela paraît peut-être dérisoire, mais cette réponse amène avec elle des avancées dans la théorie des groupes de permutations et dans la faisabilité de grands calculs informatiques. Et ça, ben, c'est pas rien...


Sources :
Toujours les mêmes
Bulletin d'info
Théorie des groupes et Rubik's Cube (laissez moi potasser le sujet, et j'en reparlerai...)
Top 9 des trucs de psychopathe faits avec un Rubik's Cube

Posté par El Jj à 02:05 - Commentaires [3] - Permalien [#]
Tags : , , ,

28 juillet 2007

L'éternité, c'est long

Surtout vers la fin... [Woody Allen]

Mais c'est pourtant aujourd'hui que sort le jeu "Eternity II" dont je vais me faire un plaisir d'un faire la publicité pendant tout un article !
Eternity II, c'est ça (Une soixantaine d'euros dans tous les bons magasins de jouets) :

eternityII


Il s'agit en fait d'un simple puzzle de 256 pièces, et en le terminant, on peut gagner la modique somme de 2000000 de dollars.
Deux millions de dollars pour un simple puzzle de 256 pièces, il doit surement y avoir une arnaque quelque part... Et vous n'avez pas tord de le penser !

En fait, les 256 pièces sont toutes carrées, avec un demis-motifs sur chaque côtés. Le but du jeu est de reconstituer le carré 16×16 avec les petites pièces, de manière à ce que chaque pièce corresponde avec sa voisine. Ma description n'est pas claire, le plus simple étant de tester la version en ligne, avec 16 pièces.

Le plus amusant la dedans est que l'on ne peut savoir si l'assemblage est bon seulement avant d'avoir posé la dernière pièce, comme on peut le voir sur cette image :

rat_

Mais revenons en au véritable jeu, à 256 pièces. Tout est là pour nous aider : on a déjà la position de l'une des pièces dessinée sur le plateau, on sait quels sont les 4 coins ainsi que les pièces du bord. On sait même qu'il y a 20 000 solutions différentes !

Bon, imaginons que l'on place toutes les pièces totalement au hasard : 256 pièces avec 4 angles différents possibles, ça donne 256!×4^256 façon de les placer, soit approximativement... 1,1×10^561 façons de les arranger...
Dans mon calcul, j'ai pas tenu compte des coins et de la pièce déjà placée, mais si je le fait, je trouve 4!×56!×195!×4^195 façons de les placer au hasard astucieusement.
Ce calcul donne
111531198469622492899759608971914595420947197274350519487727469101946513455
069377676358191758547254409098250127814533366537520303714516904568624054580
457715452150218419881603342689862313004029178711324849404505256052275017987
734577907767291619938991043571658075515174233907285048188722138784099296270
534509243817733468845560076206020218546046771585537232438151046330793578226
302780416097998170704433957446872507749953327176975289802388296970098802251
975215311015541008230129409675866681048622432256000000000000000000000000000
000000000000000000000000000000000
façons de placer nos 256 pièces (1,11×10^557). (Enfin, il y en a encore moins si on considère les pièces symétriques)
Même quand on sait qu'il y a 20 000 possibilités de réponses différentes, cela laisse une chance sur 10^552 d'avoir une bonne réponse en les plaçant de manière totalement aléatoire (à côté, l'Asaṃkhyeya est minuscule, et je ne parle pas des probabilités de gagner au loto, totalement ridicules)

Et pourquoi ne pas utiliser un ordinateur, alors ? Plusieurs solutions s'offriraient à nous :
* Essayer toutes les 10^552 solutions différentes, et regarder si elles fonctionnent. J'ai du oublier de préciser que le jeu est limité dans le temps, il faut trouver la solution avant le 31 décembre 2008 pour espérer gagner le 2 millions de dollars. Dépasser de très loin l'âge de l'Univers pour répondre à la question est tout à fait déconseillé...
* Programmer un logiciel permettant de résoudre la question le plus rapidement possible en prenant le problème dans sa globabilité, et donc, en utilisant la mathématique des nombres complexes, l'analyse combinatoire, la théorie des probabilités, mais aussi et surtout la théorie des pavages dits quasi périodiques, qui n'a qu'une trentaine d'années d'existence...

En fait, dans les deux cas, ça ne sert à rien de l'envisager, c'est pas possible, on a pas assez de temps... Le plus simple, finalement, c'est de prendre son temps et le faire à la main...
...

Et pendant ce temps là, l'institut allemand Fraunhofer IPK tente de reconstruitre le plus grand puzzle du monde, avec 600 millions de pièces, en numérisant toutes les pièces à l'aide de scanner à haute résolution et de bons ordinateurs. Le projet, c'est Stasi Puzzle project. Tout ça pour reconstituer les archives de la STASI de l'ex-RDA, que les agents de cette police secrète ont détruit au dernier moment après la chute du mur de Berlin. 16,5 km d'informations sur la population est-allemande sont à reconstruire pour que les familles puissent accéder à leur dossier. 600 millions de pièces, ce sont des fragments de page A4 déchirées à la main en 8, 12 voire 20 ou 40 morceaux. Ce projet devrait mettre normalement 5 ans à se boucler.
...

En attendant, le grand public a Eternity II pour gagner deux millions de dollars, ou au moins, passer le temps et s'amuser avec un vrai challenge !...


Sources :
Site officiel de Eternity II
L'article du Monde sur le sujet
Archives de la Stasi - Sciences & Vie n°1060, janvier 2006

Posté par El Jj à 20:03 - Commentaires [5] - Permalien [#]
Tags : ,



22 juillet 2007

Au-dessus de la moyenne

"Un grand patron français gagne en moyenne 300 smics", "La durée de vie moyenne d'une faille est de 348 jours", "j'ai déjà vu des threads où la taille moyenne allait autour des 20", "J'ai eu mon semestre avec 16 de moyenne" ou "C'est quoi la vitesse moyenne des coureurs du Tour de France ?" ...
Le mot "moyenne", tout le monde l'emploie, et d'ailleurs, tout le monde sait globalement à quoi cela correspond : une valeur représentative de tout un ensemble de données. Une sorte de milieu, en fait.

Pour la calculer, ça aussi, n'importe quel allergique aux maths peut le faire, parce que ça sert toujours en cours de français pour savoir quelle note il va falloir au prochain contrôle pour rattraper ce 03/20 dans un contrôle sur les probabilités.
Cette moyenne, c'est la moyenne arithmétique. On additionne toutes les valeurs et on divise par leur nombre.

La moyenne harmonique...
Et la vitesse moyenne du coureur cycliste ? Celui qui fait du 20km/h sur 1km en montée et du 80 km/h sur une descente de 1 km ?
Je vous laisse réfléchir.............
(20+80)/2=50. Il aurait donc une moyenne de 50 km/h ?...
Si je pose la question, c'est évidemment parce que cette réponse est fausse. Il aurait plutôt fallu répondre 32km/h, puisque notre ami le coureur va passer beaucoup plus de temps sur la montée que sur la descente (Je ne fais pas le détail des calculs ici).
Avec nos données, on a eu trop vite tendance à calculer la moyenne arithmétique, alors que c'est la moyenne harmonique qu'il fallait utiliser. (On divise le nombre de valeurs par la somme des inverses des données)


La moyenne géométrique...
Autre situation, autre problème.
Le 7 mars 2006, 400 000 personnes (selon la police) ou 1 000 000 (selon la CGT) manifestent à travers la France contre le CPE.
Quels chiffres croire ? La police a plutôt tendance à amoindrir le nombre, et les organisateurs ont tendance à le grossir, en plus de l'imprécision du compte.
Faire une moyenne arithmétique (700 000 personnes), ça donne un très net avantage à la CGT ; en imaginant que la police donne 10 fois moins de manifestants (-90%), la moyenne arithmétique atteindrait 520 000 personnes (-26%). Le chiffre de la CGT écrase celui de la police.
Imaginons plutôt que la police et la CGT fonctionnent de la même manière : d'un côte, la police sous-compte (par exemple, pour 4 manifestants, 3 seront comptés, soit -25%) et de l'autre côté, la CGT sur-compte (pour 4 manifestants, 5 seront comptés, soit +25%). Les deux utilisant les même coefficients. C'est là que la moyenne géométrique intervient ! Il suffit de calculer la racine carrée du produit des deux valeurs.
Dans notre cas, on peut estimer le nombre de manifestants du 7 mars 2006 à 632 500 (La CGT risque de faire la gueule...)


Les autres
Il existe d'autre types de moyenne qui ont leur utilité en mathématiques, comme la moyenne quadratique, la moyenne arithmético-géométrique, la moyenne glissante...

Et histoire de finir joliment cette note, pour tous les gens venant de google cherchant des informations sur les moyennes, voici une petite liste récapitulative :

Moyenne arithmétique :
arithm_tique

Moyenne harmonique :
harmonique

Moyenne géométrique :

g_om_trique

Moyenne quadratique :
quadratique

Et pour finir en beauté, le cas général :
g_n_ral

  • pour m = 1, on a la moyenne arithmétique
  • pour m = 2, on a la moyenne quadratique
  • pour m = -1, on a la moyenne harmonique
  • pour m tendant vers 0, on a la moyenne géométrique
  • pour m tendant vers l'infini, on a la plus grande valeur de la série.

Sources :
BibMath et Wikipédia

Posté par El Jj à 15:51 - Commentaires [10] - Permalien [#]
Tags :

14 juillet 2007

La formule de Marcel Pagnol

Marcel Pagnol : 28 février 1895 - 18 avril 1974. Écrivain, dramaturge, cinéaste et académicien français, on lui doit entre autre ses souvenirs d'enfance... Mais pas seulement ça ! On lui doit aussi ceci :

Si n est impair, alors n+(n+1)+n(n+1) est premier.

Pour n=1, 1+2+1×2=5 (premier)
Pour n=3, 3+4+3×4=19 (premier)
Pour n=5, 5+6+5×6=41 (premier)
etc.
Bon, évidemment, si il avait essayé n=11, il aurait vu que 11+12+11×12=155, qui n'est pas un nombre premier (Divisible par 5).

Un formule qui donnerait tous les nombres premiers, ça serait quelque chose de beau, non ?! Ca pourrait permettre d'avoir des nombres premiers aussi grands que l'on veut. Aujourd'hui, on ne connait pas de nombres premiers plus grands que 232582657+1...

Après tout, il y a bien une formule qui donne tous les nombres impairs (2n+1) ou une qui donne tous les nombres de Fibonacci (FiboFormule), alors pourquoi pas une formule qui donnerait tous les nombres premiers ?

Pagnol n'est pas le premier à s'y être cassé les dents avec sa formule (4n²+10n+5), Euler a été le premier à s'y atteler. A l'époque, il a trouvé la formule n² − n + 41... (Qui, évidemment, ne marche pas pour n=41, car le résultat sera divisible par 41). On a fini par démontrer qu'on ne pouvait pas trouver de polynôme a une seule variable donnant tous les nombres premiers.

Si cette formule existait, ça se saurait : on l'aurait depuis longtemps utilisé pour battre ce misérable record du nombre premier le plus grand (9 808 358 chiffres).

Et pourtant ! Il y a bien un polynôme qui donne la totalité des nombres premiers. On doit cette formule à Jones, Sato, Wada et Wiens en 1976. Voici la formule :

Jones

C'est vrai, on a déjà vu des formules plus simples, mais celle-ci fonctionne, elle peut donner tous les nombres premiers, pourvu que le résultat est positif. C'est simplement un polynôme de degré 25 avec 26 variables.

Evidemment, il y a un hic, quand on regarde de plus près la formule. Il s'agit du produit de deux membres : d'un côté, (k+2), et de l'autre, (1-plein de choses). Pour obtenir un résultat positif, il faut nécéssairement que le "plein de chose" soit nul : il s'agit finalement d'un système de 14 équations diophantiennes (à coefficients entiers) à 26 inconnues. Autant le dire simplement : c'est quasiment impossible d'avoir de solutions avec cette formule. A l'heure d'aujourd'hui, on a juste réussit à obtenir 2...

Mais ce n'est pas grave ! Lâchons les polynomes (même s'il y en a d'autres du même genre, dont un avec 10 variables, de de degré 1045) et cherchons une autre formule qui pourrait donner tous les nombres premiers.

Grace au théorème de Wilson (une histoire de congruence sur les nombres premiers), on a pu trouver une très chouette formule, qui donne tous les nombres premiers dans l'ordre :

Wilson1
(Les drôles de traits verticaux, c'est la fonction partie entière)

Sinon, si vous n'aimez pas les sinus et les factoriels, il y a aussi cette charmante formule plutôt basée sur les parties entières...

Wilson

En fait, ces deux formules sont aussi inutilisables que la formule de Jones, Sato, Wada et Wiens, on a plus vite fait de prendre des nombres au hasard et de tester leur primalité par des algorithmes simples.

Tous ça pour dire que l'on cherche encore la formule miracle...
Si elle existe...


Sources :
Fortement inspiré de wikipédia
(Et un peu d'une conférence donnée à la fac sur le sujet)

Posté par El Jj à 10:00 - Commentaires [6] - Permalien [#]
Tags : ,

08 juillet 2007

C'est l'facteur !

« La percée mathématique évidente serait le développement d'un moyen simple de factoriser les grands nombres en facteurs premiers. » [Bill Gates]

Non, je ne donnerai pas la clé du code de mon dernier article, vous n'avez qu'à trouver seuls la factorisation de 284191[...]27. Peut-être pas aujourd'hui, parce que nos ordinateurs en sont parfaitement incapables, mais peut-être que dans quelques années, si la puissance de nos ordinateurs évoluent et que les mathématiciens font bien leur boulot, la factorisation d'un nombre énorme sera quelque chose de faisable...

Mais au fait, pourquoi sommes nous aujourd'hui incapables de factoriser le n de mon précédent article ? Si tout va bien, je devrais y répondre au cours de cette note...

Digressons un peu : petite FAQ sur les nombres premiers ?

Qu'est ce qu'un nombre premier ?
Officiellement, c'est un nombre qui a exactement deux diviseurs : 1 et lui-même. Le genre de nombre impossible à diviser sous peine de se retrouver avec un nombre à virgule.
Qui donc a inventé ces nombres ?
Il s'agit apparemment de Grümf, le même qui a inventé la roue, il y a 23 000 ans...
Laurence Boccolini m'a dit que 1 était le premier nombre premier. C'est vrai ou pas ?
C'est faux, arrête de regarder TF1, ça ne te réussis pas. 1 n'est pas premier, il suffit de relire la définition : c'est un nombre qui a exactement deux diviseurs. Le nombre 1 ne possède qu'un seul diviseur, je vous laisse deviner lequel.
Et pourquoi on met le nombre 1 à l'écart comme ça ?
Parce que c'est bien plus pratique comme ça. Un théorème (appelé aussi théorème fondamental de l'arithmétique, ça serait dommage de l'infirmer) nous dit que tous les entiers naturels possèdent une décomposition unique en un produit de facteurs premier (aux permutations près). Par exemple, on a 12=2×2×3. Si 1 était un nombre premier, on aurait également 12=1×1×2×2×3, et la décomposition ne serait plus unique. Ca lui apprendra à être l'élément neutre de la multiplication !
Y'en a combien, des nombres premiers ?
Il y en a autant qu'on veut. Une infinité, quoi... Vous imaginez ce qu'il se passerait s'il y en avait un nombre fini ? Il suffirait de multiplier ensemble tous ces nombre premiers et d'y ajouter 1 pour se retrouver avec un nouveau nombre premier, ce qui serait embêtant...
C'est lequel le plus grand ?
Je viens de dire qu'il y en avait une infinité... Cependant, le plus grand que l'on ait calculé est un nombre de Mersenne, c'est à dire, de la forme 2n+1, avec n=32 582 657. Ca donne un nombre composé de 9 808 358 chiffres.


Maintenant cette petite mise au point faite, interressons-nous à cette histoire de factorisation. La force de l'algorithme RSA, c'est qu'il s'appuie sur la difficulté de décomposer un nombre composé en produit de nombre premiers, d'autant plus que les facteurs premiers sont de taille conséquentes.

Pour décomposer un nombre, la technique la plus simple est de tester un à un tous les nombres premiers pour voir s'ils divisent notre nombre.
Prenons 140.
2 est un diviseur de 140. On le garde de côté, il reste 70.
2 est encore un diviseur de 70. On le garde de côté, il nous reste 35.
2 n'est pas diviseur de 35, on passe donc au nombre premier suivant, c'est à dire 3.
En procédant ainsi, on trouvera facilement que 140=2×2×5×7.

Maintenant, si on s'amuse à chercher de la même façon pour décomposer 6887, on passera beaucoup plus de temps, puisqu'il faudra tester tous les nombres premiers uns à uns jusqu'à 71 avant de trouver que 6887=71×97.

Quand notre nombre à factoriser possède 309 chiffres, comme dans une clé de cryptage RSA classique, on ne peut pas décemment envisager le fait de tester tous les nombres premiers (ne serait-ce parce qu'il y en a au moins 10305).

Evidement, les algorithmes que l'on utilise en réalité sont plus efficaces que celui-ci, mais aucun d'eux n'arrive à donner des décompositions de gros nombres dans des temps raisonnables. En effet, les temps de calculs ne sont pas proportionnels à la longueur des nombres, mais à leur exponentielle. Ces algorithmes peuvent être rapides quand les nombres sont le produit de nombreux petits nombres premiers, mais dans le cas où l'on cherche à factoriser de grands nombres semi-premiers (un nombre produit de deux nombres premiers), l'attente serait vraiment trop longue.

L'idéal serait de trouver un algorithme rapide permettant de décomposer un nombre. Peut-être pas avec un temps de calcul proportionnel à la taille du nombre, mais au moins proportionnel à son carré, son cube ou autre... Un algorithme polynomial, en fait. Peut-être il existe, mais repose sur une propriété que l'on ne connait pas encore... Peut-être il n'existe pas, mais il faudrait le démontrer... Le mathématicien ou l'informaticien qui réussirait à répondre à cette question pourra finir ses jours heureux, vu l'argent en jeu...

En effet, le laboratoire RSA a lancé son propre concours : décomposez-moi ce nombre, et gagnez une somme conséquente en dollars. 200 000 $ sont prévus pour celui qui pourra donner les diviseurs premiers d'un nombre à 617 chiffres. Pour ceux qui visent moins haut, 30 000 $ sont prévus pour la factorisation d'un nombre à 211 chiffres. Ce challenge est plutôt réservé aux laboratoires qui prennent le temps de faire tourner leur ordinateur plusieurs mois durant, mais si vous vous ennuyez, vous pouvez toujours tester de multiplier des nombres au hasard. Mais c'est surtout un bon indicateur de la puissance des ordinateurs et des mathématiques.

Bref, tout ça pour dire qu'il faut faire attention à cette histoire de challenge RSA. Le jour où les 200 000 $ auront été gagnés, il faudra arrêter de se servir de sa carte bleue... Enfin, surtout pour Bill Gates, qui nargue tout le monde avec son argent protégé par des nombres à factoriser...


Sources :
Ben... Wikipedia !
Le challenge RSA

Posté par El Jj à 10:00 - Commentaires [5] - Permalien [#]
Tags :

02 juillet 2007

Devenir H4ck3rz, pour les nuls

Internet, ce n'est pas que des casinos maltais ou des vidéos de chutes en skate, c'est aussi le commerce en ligne : transactions de fonds, numéros de cartes bleues et date d'expiration associée, tout ça circule tranquillement sur le réseau. De manière codée, certes, mais avec des clefs de codages bien connues de tous puisqu'elles sont publiques... Aujourd'hui, apprenons ensemble à décoder les chiffrements renfermant le code de la carte bleue de Mr Dupont qui vient de s'acheter un chouette vélo d'appartement.


Remontons à l'origine de la cryptographie, avec le code de César (comme son nom l'indique, inventé par Jules César). Le principe de ce code est tout simple : on décide d'une clé k, et on fait correspondre à chaque lettre du message la lettre de l'alphabet décalée de k lettres. Si k=3, on a A->D, B->E etc.

Prenons cet exemple : "VBVYJPYJPYJP KJPNNZ G'VIVIVN ZO HJPYN G'XVAZ".
Donné ainsi, déchiffrer le code peut nécessiter plusieurs minutes.
Si je précise qu'il s'agit d'un code de César, il n'y aura plus que 25 clés à tester.

Si j'ajoute que la clé est 8, le code sera cassé en quelques secondes.


Le tour de force des cryptages qui ont lieu sur internet, c'est que tout le monde sait que le codage utilisé est le codage RSA (Du nom de leur auteurs, Ron Rivest, Adi Shamir et Len Adleman), et que la paire de clés de codage est (relativement) publique ! (Pour plus de sécurité, le codage RSA est associé à l'OAEP, mais je ne vais pas en parler dans cet article)

-----

En plus, le codage RSA est plutôt simple à mettre en œuvre pour n'importe qui connaissant l'arithmétique (nombres premiers, nombres premiers entre eux, divisions euclidiennes et congruences) ! Voyons comment cela fonctionne :

Tout d'abord, Arnaud, maître en chef de la cryptographie, choisit deux nombres p et q tous les deux premiers. Il calcule ensuite le produit n=pq. n est alors la première clé de cryptage, qu'il mettra à disposition de tout le monde sur internet. Il choisit ensuite un autre nombre e, premier avec (p-1)(q-1), qu'il mettra à disposition de tout le monde sur internet.

Maintenant, Bernard a une terrible envie de passer un message secret à Arnaud, mais il sait que son ennemi juré, Christophe, guette. Ce message secret, c'est M, un entier positif plus petit que n.
Pour le coder, il suffit simplement de calculer le reste de la division euclidienne de Me par n :

RSA1

Et le tour est joué, le message est codé ! Bernard n'a plus qu'à l'envoyer à Arnaud qui pourra le décoder.
Avant tout ça, Arnaud a aussi calculé l'entier d tel que RSA2.

Pour décoder C, il y a juste à calculer Cd modulo n. Le résultat sera alors M.

Le plus difficile pour Christophe (qui ne connait ni p, ni q, ni d), c'est de trouver ce nombre d. Pour cela, il lui faudra factoriser n en p×q, puis trouver d selon la relation ci-dessus.

-----

Petit exemple :
On prend les clés de cryptage suivantes
n = 1653277069
e = 65537

Et mon message caché, c'est :
C = 305880301

Pour décrypter ce message, il faut donc savoir factoriser. Comme ce n'est pas un nombre trop énorme, on peut encore le faire : 1653277069 = 41113  x  40213.
On a donc T=(p-1)(q-1) = 41112  x  40211 = 1653195744
Il faut à présent calculer d (L'inverse de e modulo T). Cet inverse, c'est d=1104341921.
On décode à présent le message.
Cd modulo n = 1615210520

En le décodant, on a 16.15.21.05.20 -> P.O.U.E.T

Et voilà un beau message décodé !

-----

Allez, passons à un petit exercice ! Saurez-vous décoder ce message codé, sachant que pour le coder, j'ai utilisé :

n =
28419181913810437345824250197567708730088202978694
28913715429476242088608345960904066292721435918199
21106779056877531440875230218032640311325038378896
92339352650802850904343984369558897929963233427

e = 65537

Et voici mon message codé :
C =
11702615899972603057258578189422057798020038730314
78892622538509244478308728446193131481112246707511
12640561090848642523271203957773047992148675956812
22080098315061823288413981706052270284295473961

Le premier ou la première qui réussira à le décoder gagnera un magnifique cadeau d'une valeur inestimable !

 

-----

Bref, pour hacker en toute tranquillité, il suffit simplement de savoir factoriser des grands nombres !

(Ai-je omis de préciser que dans l'état actuel des choses, il est impossible de factoriser un nombre à plus de 200 chiffres ?... Quand on sait que les clés de chiffrements des banques sont de l'ordre de 300 chiffres...)

Il faut tout de même se rassurer : ce système garde encore quelques failles, tout n'est pas perdu pour les hackers !


Sources :
La page Wikipedia sur RSA (avec démonstration)
Générer des grands nombres premiers
Calculs sur de grands entiers

Posté par El Jj à 17:49 - Commentaires [14] - Permalien [#]
Tags : ,

24 juin 2007

Mon papa, il est mille fois plus fort que le tien !

- Mon papa, il est plus fort que le tien !
- Nan, c'est le mien le plus fort !
- C'est pas vrai, parce que le mien, il est 100 fois plus fort !
- Nan, le mien, il est un million de fois plus fort !
- Mais le mien, il est un millions plus une fois plus fort !

Bon, évidemment, à moins de s'essouffler, on peut continuer cette discussion intéressante indéfiniment, tant qu'on arrive à trouver des nombres toujours plus grand... Alors, comment mettre K.O. son adversaire au jeu du "Mon papa, c'est le plus fort" ? Tel est l'objet de cet article !

Pour atteindre des grands nombres, rien ne vaut les puissances de 10, c'est d'ailleurs comme ça que commencent toute bonne partie de "mon papa, c'est l'plus fort". Les choses risquent fort de commencer comme ça, les plus simples des grands nombres :
Cent (100), Mille (1 000) , un million (1 000 000), un milliard (1 000 000 000), etc.

Et après ?
Le débat fait rage, puisque deux écoles s'affrontent. D'un côté, ceux qui adoptent la progression par 1000 et ceux qui adoptent la progression par 1 000 000, ce qui rend les discussions à propos de grands nombres incompréhensibles (d'où l'utilisation des puissances de 10).   
    Selon la règle traditionnelle, on a ensuite le trillion (1012), le quatrillion (1015), le quintillion (1018), le sextillion (1021), le septillion (1024), l'octillion (1027) etc.
    Selon la règle officielle, on a ensuite le billion (1012), trillion (1018), le quatrillion (1024), le quintillion (1030), le sextillion (1036), le septillion (1042), l'octillion (1048) etc.
    Il y a encore d'autres systèmes utilisés, mais on va rester sur le système officiel.

Mais tout ça, finalement, ça reste des petits nombres, on peut aller bien plus loin. Archimède, par exemple, en s'amusant à compter les grains de sables, a supposé que la sphère terrestre pouvait contenir 1064 grains de sable... Carl Sagan, quant a lui, a estimé le nombre d'atomes dans l'Univers a 1080.

Et après ?
On peut toujours trouver des nombres plus grands ! Leur gros problème résidera dans le fait qu'il ne représentent pas grand chose de physique.

C'est histoire de créer des grands nombres que Kasner demanda à son neveu un nom pour le nombre qu'il venait d'inventer, 10100 (utilisé pour parler d'un nombre grand qui n'est pas l'infini). Alors âgé de 8 ans, son neveu lui répondit "gogol". C'est ainsi que le gogol fut né, un "un" suivit de cent "zéros". C'est d'ailleurs de là que vient le nom du moteur de recherche, qui, à terme, devrait recenser un gogol de pages... Ce nombre reste malgré tout à peu près égal à 70! (factorielle de 70, c'est à dire, 1×2×3×...×70).

Et après ?
On a le nombre de Shannon (10120), c'est à dire, le nombre théorique possible de parties d'échec !

Et après ?
Et bien, c'est à ce moment là qu'il faut citer l'asaṃkhyeya (असंख्येय, pour les grammar nazi du sanskrit), qui vaut environ 10140, qui est un nombre bouddhiste, littéralement "au dela des nombres". C'est le nombre considéré comme étant le plus grand. En effet, un bouddhiste jouant au jeu du "Mon papa c'est l'plus fort" ne pourra pas aller plus loin que "Mon papa est un Asaṃkhyeya de fois plus fort que toi"... La valeur de l'asaṃkhyeya reste cependant sujette à caution, puisqu'il vaut 105×2^103 ou 107×2^103 (un nombre possédant environ 1032 chiffres.

Et après ?
Mais ces nombres sont ridiculement petits par rapport à ce qui suit : les plex ! Dans la foulée du gogol fut inventé le gogolplex, égal à 10un gogol. (D'où le nom du siège social de google, le googleplex). D'autres mathématiciens ont prolongé le concept, un disant qu'un N-plex valait 10N, et donc, le gogolplexplex vaut 10un gogolplex.

Et après ?
Et bien, c'est là que Knuth arrive et propose un tout nouveau système de puissance.
Avant, nous avions l'écriture ab, que l'on comprenait comme ça :

a_b

Et bien, Knuth propose un système de doubles flèches verticales :

aflflb

On a, par exemple, 3flfl3
ou   9flfl5, nombre considérablement plus grand que le gogolplex.

Et après ?
Et bien, Knuth a encore agrandi son concept de flèches, en proposant la triple flèche, la quadruple flèche et la n-flèche définie de manière récursive. Ca donne alors quelque chose comme ça :

aflflflb

On a, par exemple, 2flflfl3

Et en généralisant, ça donne :

aflflnb

Ces nombres ont eu une application concrète, celle du nombre de Graham, le plus grand nombre jamais utilisé dans une démonstration mathématique (une sombre histoire de coloration d'hypercube), qui correspond au 64e terme de cette suite :
u1 = 4
u2 = 3flflflfl3     (Avec 4 flèches)
u3 = 3flpoints3     (Avec u2 flèches)
Et ainsi de suite jusqu'à u64, le nombre de Graham, qui aura u63 flèches...

Et après ?
Et bien à ce niveau là, on se dit que les nombres deviennent trop grand (ce qui n'est pas peu dire...) et qu'il serait inutile d'en chercher des encore plus grand... Et pourtant, il existe une notation permettant d'en avoir des encore plus grands ! C'est la notation des flèches de Conway !
Dans la notation de Conway, les nombres s'écrivent sous la forme d'une chaîne, comme 2 → 15 → 42 → 7. Dans ce cas là, la chaîne est de longueur 4, composé d'une chaîne queue (2  → 15  → 42) et d'un terme de tête (7).

La valeur numérique de cette chaîne est définie de manière récursive :

  • Une chaîne de longueur 1 représente le nombre.
    • Si la chaîne est de longueur 2, c'est l'exponentiation classique : 
      p → q = pq
  • Si le terme de tête est 1, la chaîne est égale à sa chaîne de queue :
    Y → 1 = Y
  • De manière similaire, la présence d'un 1 dans la chaîne la coupe :
    Y → 1 → X = Y
  • Si la chaîne est de longueur supérieure ou égale à 3, elle est égale à une chaîne de même longueur égale où le nombre de tête est décrémenté, et où l'avant-dernier terme est considérablement plus grand :
    Y → p → q = Y → (Y → p-1 → q) → q-1 (pour p,q ≥ 2)

Cette dernière propriété permet de réduire la taille des chaînes.
Ainsi, la chaîne 2 → 15 → 42 → 7 est égale à 2 → 15 → (2 → 15 → 41 → 7) → 6 (chaîne de longueur 4, avec un terme de tête plus petit). En appliquant cette règle de récursion encore 5 fois, le dernier terme sera 1, ce qui permet de "diminuer" à 3 la longueur de la chaîne. Seulement, le dernier terme de cette nouvelle chaîne de longueur 3 est immensément grand...

Ainsi, on peut encadrer le nombre de Graham G avec des nombres de la notation de Conway :

encadrement

Mais le nombre de Graham reste ridiculement petit par rapport au nombre 3fl3fl3fl3...

Et après ?
On pourrait toujours s'amuser à définir une notation correspondant à des itérations de notation des flèches de Conway, mais pour l'instant, aucun mathématicien n'a jugé utile de le faire...

- Mon papa, il est plus fort que le tien !
- Nan, c'est le mien le plus fort !
- C'est pas vrai, parce que le mien, il est 100 fois plus fort !
- Nan, le mien, il est factoriel de l'itération d'un nombre de Graham de fois de la notation en flèche de Conway avec le gogolplex...plex avec un Asaṃkhyeya de "plex"  de fois plus fort que ton père !!!!
- Euh... et ben... euh... Le mien, il est factoriel de l'itération d'un nombre de Graham de fois de la notation en flèche de Conway avec le gogolplex...plex avec un Asaṃkhyeya de "plex" plus une fois plus fort !


Sources :
Les grands nombres
Notation des puissances itérés de Knuth
Notation des flèches chaînées de Conway

Posté par El Jj à 03:35 - Commentaires [18] - Permalien [#]
Tags : , ,



« Début   23  24  25  26  27  28  29  30  31  32    Fin »