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 : , ,



18 juin 2007

La numération des marchands d'œufs

J'en avais déjà parlé sur mon autre blog, mais il est hors de question que je n'en reparle pas ici : la numération des marchands d'œufs (ou d'huitres).

Pour comprendre ce qu'est cette numération, il faut se replacer dans le contexte :
- Bonjour madame la marchande d'œfs, je voudrais 12 œufs !
- Pardon ?
- Euh, je veux dire, je voudrais une douzaine d'œuf !
- Ah ! tenez, les voici.

C'est là que le problème se pose : les marchands d'œufs sont incapables de s'exprimer avec d'autre unités que la douzaine ou la demie douzaine. Résultat, pour commander 72 œufs, il faut faire preuve d'ingéniosité et commander "une demie-douzaine de douzaines d'œufs" (car 6×12=72) !

La numération des marchands d'œufs, c'est simplement une façon de compter les œufs propre au monde de l'ovocommerce. Voici un petit tutorat pour s'exprimer comme un chef et ne plus hésiter lors d'une commande d'huîtres pour la nouvelle année.

Les trois unités de bases sont la douzaine, la demie-douzaine et la demie-demie-douzaine (respectivement 12,6 et 3).
Ensuite, il faut savoir que l'on peut à sa guise multiplier ces nombres de bases grace au mot magique "de". On a alors une demie-demie-douzaine de demie-demie-douzaines pour désigner 9.

Évidemment, cela limite énormément la possibilité de commande, c'est pourquoi on peut ajouter deux autres mots de vocabulaires, "un peu moins d'" et "un peu plus d'" que l'on peut combiner aux diverses douzaines pour leur ajouter ou retrancher une unité. On a alors un peu plus d'une douzaine pour désigner 13 et un peu moins d'une demie-demie-douzaine pour parler de 2.

La multiplication marche toujours avec le "de", ce qui permet d'obtenir comme 8, avec un peu moins d'une demie-demie-douzaine d'un peu plus d'une demie-demie-douzaine.

Dans le jargon de la numération des marchands d'œufs, on appelle les nombres que l'on peut exprimer ainsi des "nombres de classe 1". Il est pas important de voir que les nombres de classe 1 se multiplient à merveille en ajoutant un petit "de".

Il arrive ensuite que des nombres ne soient pas des nombres de classe 1, comme par exemple 17. Par contre, on peut exprimer de 18 (une demie-demie-douzaine de demie-douzaines d'oeufs). Il suffit donc de dire que 17, c'est un peu moins de 18, c'est à dire, un peu moins de une demie-demie-douzaine de demie-douzaines d'oeufs.

A noter que cette fois ci, il n'y a pas d'apostrophe, on dit bien "un peu moins de" et "un peu plus de" dans le début des nombres de classe 2.

Il existe ensuite les nombres de classe 3, que l'on ne peut tout simplement pas exprimer dans la numération des marchands d'œufs, mais qui donc irait songer à acheter 58 œufs ?

Pour vous aider dans ce  nouveau système de numération, voici un petit traducteur très utile ! (Les étoiles indiquent les nombres de classe 2)

Donnez le nombre à traduire :

Et maintenant, il n'y a plus aucune raison à ne pas vouloir s'occuper des courses pour le repas de Noël !


Sources : nulle part, c'est une invention personnelle...

Posté par El Jj à 02:21 - Commentaires [10] - Permalien [#]
Tags :

09 juin 2007

Best online roulette gambling

Qui n'a jamais rêvé de gagner au loto ? A part les trois hippies au fond, personne ! Avec une chance sur 14000000 de gagner le gros lot, finalement, personne n'y crois vraiment...Par contre, pour ce qui est des jeux de casinos, le chance de gain nous sont beaucoup plus favorable.
Pour peu que les machines soient fiables comme dans un casino digne de ce nom (et contrairement à ce que l'on peut trouver sur internet), on peut même facilement calculer ses probabilités de gains. La roulette française, par exemple, contient 37 cases : 18 cases rouges, 18 cases noires et une verte. En misant sur le rouge, la probabilités de gagner est donc de 18/37=48,64%.

Bref, si je mise 1€ sur le rouge, j'ai 48,64% de chance de gagner mon euro, et 51,35% de perdre mon euro.

Depuis de nombreuses années, les joueurs ont tenté de chercher a faire basculer les probabilités en leur faveurs. De nombreuses techniques ont été mises au point : poupées vaudoo, prière, menace procès en justice ou application de la loi des grands nombres sur des petits nombres. Évidemment, rien de tout cela ne marche.

Pendant ces mêmes années, les mathématiciens probabilistes ont également cherché des techniques
pour gagner au casino, alias, martingales. Et en cherchant assez longtemps, ils les ont trouvé !
Le sujet de cette note est donc très simple :

Comment gagner à la roulette ?
(ou tout autre jeu d'argent de hasard pur, comme le pile ou face, la roulette russe ou le dé)

De nombreuses martingales existent, je vais vous présenter les principales :

La martingale classique (comment s'assurer de gagner 1€ ?)
Cette martingale est la plus simple de toutes :
On commence par miser 1€ sur le rouge.
Si le rouge tombe, vous venez de gagner un euro, et vous pouvez vous arrêter là.
Si c'est perdant, vous misez à nouveau sur le rouge, mais cette fois ci, 2€.
Si le rouge tombe, vous gagner 2€-1€(perdu à la première partie)=1€
En cas de perte, il faut miser 4€, puis continuer à doubler tant que l'on perd. (Tant que l'on perd, on mise tour à tour 1,2,4,8,16,32...)
Dès que le rouge sortira, le gain couvrira les pertes qui ont précédé, avec un petit plus de 1€.

La grande martingale (comment s'assurer de gagner 1€ par parties jouées ?)
On procède de la même façon que pour la martingale précédente, mais au lieu de miser le double de la mise précédente, on joue le double plus une unité. (Tant que l'on perd, on mise tour à tour 1,3,7,15,31...)
Au premier gain, on remportera autant de mise que de parties jouées. Ensuite, on peut partir du casino.

Le piquemouche (comment gagner autant en risquant plus ?)
On procède de la même façon que pour la martingale classique, mais au lieu de doubler les gains tout de suite, on se laisse d'abord un peu désirer. Tour à tour, il faut miser 1,1,1,2,2,2,4,4,4 et ainsi de suite.
Gagner au deuxième coup ne fera pas gagner un seul euro, mais aura le mérite de ne pas en faire perdre. En gagnant au troisième coup, la balance sera tout de même déficitaire de 1€, et il faudra recommencer pour espérer gagner cet euro.
De toutes les martingales présentées celle-ci est la pire de toutes, le seul point positif étant son nom rigolo.

La montante américaine (comment se prendre la tête inutilement)
Cette technique est différente des autres, il ne faut l'arrêter qu'une fois que la balance est positive.
On commence par miser une unité, puis deux, puis trois (si les deux premiers jeux sont perdant, dans le cas contraire, on arrête de jouer). En même temps, il faut noter sur un petit papier la suite des mises que l'on fait : 1/2/3.
Ensuite, tant que l'on perd, il faut miser la somme de la première et de la dernière mise inscrite sur le papier (on mise 4 et on l'écrit à la suite de la liste).
Si le jeu est gagnant, on raye de la liste les deux chiffres ayant composé la somme, et on mise à nouveau le premier et dernier nombre inscrit sur la liste. On continue jusqu'à rembourser ses dettes de jeu.

 

Bon, évidemment, si tout cela marchait, ça se saurait : les casinos auraient depuis des lustres mis la clé sous la porte.
Prenons le cas de la martingale classique : pour gagner 1€, il faut pouvoir tenir la perte successive d'une grosse somme d'argent. En perdant 10 fois de suite, par exemple, il faudra miser au onzième coup 1024€, en en ayant déjà perdu presque autant. Il est vrai que 10 noirs/vert de suite est quelque chose de plutôt rare (un peu plus d'une chance sur 1000), mais quand on espère gagner le gros lot avec la martingale classique, il faut compter jouer au moins mille fois, et les dix successive arriveront peut-être... (avec 63% de chances)
En fait, pour être sûr à 100% de gagner, il faudrait posséder un compte en banque infini. En jouant un très grand nombre de fois, même avec un gros compte en banque, on finira toujours ruiné.

En fait, Dubins et Savage ont démontré en 1956 que la meilleure façon de gagner à un jeu aléatoire qui nous est défavorable est de minimiser le nombre de parties jouer ; en fait, si le jeu est défavorable, il n'y a absolument aucun moyen d'inverser les probabilités en notre faveur (à moins d'un compte en banque infini).

Et pour finir, une fois n'est pas coutume, voici un petit script permettant de tester un grand nombre de fois les différentes martingales. On peut paramétrer tout un tas de choses pour adapter les tests à autre chose qu'une chance simple à la roulette. En choisissant "expérimentation" dans le menu déroulant, vous pouvez même jouer à la roulette, comme le titre l'annonçait ! (sauf peut-être pour "best") (Utilisez avec précaution le bouton "jouer 500 fois", les navigateurs ont un peu tendance à faire la gueule)

Compte en banque :

Mise unitaire :

Probabilités de gain : %

Gain : fois la mise

Et comme dirait un sage philosophe : la meilleure façon de gagner au loto, c'est de ne pas jouer. Surtout que plus on gagne d'argent, plus la déprime qui suit est violente...


Sources :
Beaucoup de wikipedia, et un peu d'un site de casino qui proposait à la fin de chaque explication un lien pour aller faire de la roulette online..

Posté par El Jj à 02:17 - Commentaires [23] - Permalien [#]
Tags :

03 juin 2007

Zéro divisé par zéro égalent ?...

Combien ça fait, zéro divisé par zéro ?

En voilà une bonne question qui revient souvent après la remarque "Jj, tu fais bien des études de maths ?..." pendant les dîners familiaux. (Déjà deux fois en une semaine)

Menons donc l'enquête ! Pour celà, rien de plus simple, on prend une calculette qui traîne, par exemple, une TI-30Xa, simple calculette de collégien des années 2000 et on tape "0/0"... "Error"... Testons alors une calculatrice plus évoluée, style lycéen des années 2002, une TI-82. "0/0"... "ERR: DIVIDE BY 0"...Tout porte à croire qu'il ne faut surtout pas diviser par 0...

Quelques règles élémentaires nous donne quelques informations sur "0 divisé par 0" :
* Zéro divisé par n'importe quel nombre, ça donne zéro. (Mais il faudrait que cet autre nombre ne soit pas 0)
* Quand on divise un nombre par lui-même, on obtient un.  (Tant que ce nombre n'est pas zéro)
* Quand on divise un nombre par quelque chose de très proche de zéro, on trouve quelque chose de très grand. (Histoire de ne pas encore rentrer dans les histoires de calcul infinitésimal)
Donc, les trois ensembles, ça devrait donner quelque chose comme 0/0=0 ou 1 ou autre chose.

On est pas plus avancés...

Plutôt que de voir 0 comme le néant, le vide absolu, voyons plutôt 0 comme un nombre extrêmement petit, tellement petit qu'on ne le voit pas. Pour trouver combien vaut 0/0, on va appeller le 0 du dessus x et le zéro du dessous y : ce qu'il faut savoir, c'est à quoi ressemble x/y quand x et y sont deux nombre non nuls, mais presque.

On peut envisager tout un tas de possibilités. Parmi elles, le cas où :
- x est aussi grand que y (par exemple, x=y). Dans ce cas, puisque x≠0, on a 0/0 = x/x = 1. (Soit 0/0=1)
- x est aussi grand que le carré de y (x=y²) : si y est proche de 0, x est encore plus proche de 0. Ca donne donc 0/0 = y²/y = y = 0 (Soit 0/0=0)
- y est aussi grand que le carré de x (x²=y). Ca donne que 0/0 = x/x² = 1/x = ∞ (Soit 0/0=∞)

En fait, pour répondre à la question "combien font zéro divisé par zéro" avec des considération analytiques, il faudrait savoir quel est le plus petit des deux zéros, ce qui, en soit, a autant de sens que la question "combien font zéro divisé par zéro ?" (Malheureusement, la fonction f(x,y)=x/y ne sera pas continue au point (0,0)).

C'est ce qui donne la grande hantise des lycéens : la forme indéterminée ! Le genre de chose qui peut donner des résultats souvent spectaculaires :

limites

Bref :
- Ca fait combien, zéro divisé par zéro ?
- Ca fait zéro puissance zéro...

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

27 mai 2007

J'aimerais tant revoir Syracuse

"Prenez un entier supérieur à 1.
S'il est pair, divisez le par 2.
S'il est impair, multipliez-le par 3 et ajoutez 1.
Réitérez ensuite les deux précédentes étapes"

Ce qui est surprenant dans cette histoire, c'est que la suite obtenue tombera toujours sur 1, peut importe l'entier choisit au départ.

Et ce qui est encore plus surprenant, c'est que personne ne sait pourquoi !

formule

Ce problème est couramment appelé Conjecture de Syracuse. (mais aussi problème de Syracuse, algorithme de Hasse, problème de Ulam, problème de Kakutani, conjecture de Collatz, conjecture du 3n+1 ou plus poétiquement la suite de grêlons)

On a encore beaucoup de mal à en décider la paternité, les tests ADN n'ont pas encore été faits...
En fait, tout commence avec Lothar Collatz, dans les années 1930, qui s'amuse à faire des transformations itératives d'entiers et regarde ce que ça donne.
Dans les années 50, Helmut Hasse se rend à l'Université de Syracuse (près de New York, pas du tout en Sicile) et remporte un grand succès en diffusant son problème.
Pendant la seconde guerre mondiale, le polonais Stanislas Ulam reprend le problème à son nom, et, dix ans plus tard, S. Kakutani reprend le problème pour le diffuser à son tour sous son nom.
Et, dans l'histoire, personne n'a réussit à le résoudre.
A l'époque de la guerre froide, on parlait de ce problème comme d'un complot soviétique pour ralentir les recherches aux États-Unis...
Dans ces années là, un mathématicien hongrois, Paul Erdõs, proposait 500$ à qui arriverait à résoudre le problème (ça vaut pas le millions offert à qui résolverait P=NP...).

Bref, toute cette fabuleuse histoire pour dire que le problème a déjà bien vécu, si bien qu'un joli vocabulaire s'est créé autour du problème.
La trajectoire (ou le vol) d'en entier donné est la suite donnée plus haut.
Le temps de vol, c'est le nombre de terme avant l'apparition du premier 1.
L'altitude maximale est simplement le plus grand terme de la suite.
Le temps de vol en altitude, c'est le nombre de termes nécessaires pour qu'un terme de la suite soit inférieur au premier terme (les plus matheux d'entre vous remarqueront qu'il suffit de démontrer que le temps de vol en altitude est fini pour démontrer la conjecture)
Le facteur d'expansion, c'est simplement l'altitude maximale divisée par le premier terme.

Et pour faire des choses jolies, on peut mettre ça sous forme graphique :

graphiks

Avec tout ça, vous devriez pouvoir comprendre ce petit script :

 

Nombre de départ :

 

 

 

On peut s'amuser à chercher les nombres donnant le plus grand temps de vol, la plus grandes altitude maximale ou le plus long temps de vol en altitude inférieurs à un certain nombre.
Parmi les nombres inférieurs à 100, les champions sont 27 (en altitude maximale et temps de vol en altitude) et 97 (en durée de vol).
Parmi les nombres inférieurs à 1000, les champions sont 703 (en altitude maximale et temps de vol en altitude) et 871 (en durée de vol).
Vous pouvez ensuite tenter de chercher les meilleurs inférieurs à 10000...

En 2004, la conjecture a été vérifiée pour tous les nombres inférieurs à 264 (1,8 × 1019)
Les seules démonstrations que l'on a réussi a réussi à donner pour l'instant sont heuristiques (statistiques) : en considérant que les nombres impairs, on trouve qu'en moyenne, le prochain nombre impair vaut 3/4 du nombre précédent, ce qui a tendance à décroitre.
En 2006, Alain Slakmon et Luc Macot, mathématiciens québécois se basent la dessus pour donner une démonstration probabiliste de la question, démonstration vraie, mais, comme le signale leur auteurs, "Comme il s’agit d’une approche probabiliste, nous ne pouvons affirmer qu’il s’agit d’une preuve absolument irréfutable de la véracité de la conjecture. Il reste une toute petite possibilité que certains nombres y résistent". Cette possibilité est cependant petite... Mais pas impossible...


Sources :
Un site perso et un site moins perso
Article sur la démonstration probabiliste sur CyberSciences

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

20 mai 2007

Si c'est rond, c'est Poincaré

Rappelez-vous, c'était il y a une semaine...
Vous appreniez (sans doute avec effroi) que l'on pouvait concevoir que par un point extérieur à une droite ne passe aucune droite parallèle (géométrie elliptique) ou alors, une infinité (géométrie hyperbolique).
A propos de la géométrie hyperbolique, j'en était resté à un simple "Il y en a tout un tas, et n'en comprenant aucune d'entre elle, je ne peux pas en dire tellement plus".

Et bien, votre humble serviteur s'est renseigné sur le sujet (en fait, il est tombé sur l'article par hasard), et finalement, un monde dans lequel les carrés n'ont pas d'angles droits mérite pleinement sa place dans ce blog... Petite visite guidée au pays de la géométrie hyperbolique selon Poincaré.

Imaginons un disque. Un simple disque. Pour compliquer, appelons le "plan hyperbolique de Poincaré".
Pour avoir une bonne géométrie, il faut des droites et des points. Un "point" sera simplement un point appartenant au plan de Poincaré. Pour la notion de "droite", on prendra les diamètres du cercle et les arcs de cercle orthogonaux au pourtour du disque.
Les choses ressembleront alors à quelque chose comme ça :
poincare

H est le plan hyperbolique de Poincaré

Plusieurs droites y sont représentées. On peut voir que les 4 premiers axiomes d'Euclide sont bien conservés, notamment celui selon lequel il n'existe qu'une unique droite passant par deux points distincts.

Et l'axiome des parallèles ? On voit qu'il n'est pas respecté : il existe plusieurs droites passant par le point M qui ne coupent pas la droite D (T1, T2).






Maintenant, faisons attention à ne pas tout mélanger, surtout en matière de mesure des longueurs ! Le schéma ci-dessus n'est qu'une représentation. Plus on s'approche du bord du cercle, plus deux points proches en apparence seront éloignés. Un être vivant qui se déplacerait sur le plan de Poincaré ne pourrait jamais en atteindre les bords. Et nous, simple observateurs de cet être, le verrions rapetisser au fur et à mesure qu'il avance. Les angles, cependant, restent identiques pour tout le monde.


carrehyp
Ceci est un carré... Si si ! Les quatre angles sont égaux, les quatre côtés aussi

Dans le monde hyperbolique de Poincaré, la somme des angles d'un triangle est toujours inférieure à 180° (pi radians). Et ce qui est épatant la dedans, c'est que la différence avec pi donne la mesure de l'aire de ce triangle ! C'est peut-être un détail pour vous, mais quand même, c'est fou !
Et en conséquence, il n'existe pas de carrés à proprement parler, la somme des angles d'un quadrilatère étant toujours inférieure 360° (2pi radians). Il existe bien des "carrés", mais ils ne possèdent pas d'angles droits.

Autant il n'y a pas de quadrilatère avec quatre angles droits, autant il existe des pentagones droits avec 5 angles droits, des hexagones droits, et ainsi de suite... (heptagone, octogone, nonagone, triacontakaiheptagone...)

pentag
Un magnifique pavage du pan hyperbolique par des pentagones réguliers droits (en blanc)


Et encore plus fort : il existe un infinigone régulier ! C'est un polygone régulier, avec tous ses côtés égaux et tous ses angles égaux (à 120°). Et le plus fort, c'est que l'on peut paver le plan avec !

infinigone
(Plan pavé d'infinigones réguliers)

Mais tout n'est pas si compliqué dans cette vision de la géométrie, puisqu'on peut y faire beaucoup de choses impossibles à faire dans le plan euclidien. On peut, par exemple, y réaliser la quadrature du cercle. Et, encore plus fort, la conjecture P=NP est vérifiée ! (Mais pour le millions de dollars, c'est dans le plan euclidien qu'il faut le démontrer).
Bon, les choses deviennent plus difficiles quand on commence à s'intéresser à un espace hyperbolique de dimension 5 ou supérieures, mais je crois que dans l'état actuel du blog, ce n'est pas très intéressant...

Escher1
Limite Circulaire I
(M.C. Escher)



Sources :

Pour la science, n°316 février 2004 (que l'on peut lire ici)
De jolies illustrations provenant de ici
Ici, un applet java sympathique

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



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