Choux romanesco, Vache qui rit et intégrales curvilignes

13 septembre 2009

Savez-vous compter les 82 ?

Les lecteurs assidus de ce blog savent depuis la fin des vacances comment prononcer les nombres dans la langue de Molière.
Les lecteurs encore plus assidus se rappellent comment écrire les nombres dans la langue de Samsu-ditana, de Kukulkan, de Montouhotep II, de Périclès, de Shang, de Shadoko, de Boby Lapointe et même des marchands d'huitre !
Ces systèmes sont malheureusement dépassés et/ou complètement absurdes...

Le système révolutionnaire de Condorcet
Nous sommes à la fin du XVIIIe siècle, et la prononciation des nombres est à peu près celle que l'on connaît aujourd'hui, avec ses dénominations archaïques ("quatre-vingt","quatre-vingt-dix") et illogiques (Si 17 se prononce "dix-sept", pourquoi 16 ne se prononce pas "dix-six" ?). 5 ans après sa mort, le marquis de Condorcet (ou plutôt, sa veuve) publie "Moyens d'apprendre à compter sûrement et avec facilité", dans lequel il expose une façon bien plus rationnelle de nommer les nombres, dans le même élan post-révolution de refonte totale du système en utilisant la base 10 (calendrier républicain et ses semaines de 10 jours, adoption du système métrique...).

Le système de Condorcet est en fait le système français que l'on connait tous, mais en lui ajoutant un brin de de logique pour qu'il puisse être plus facilement enseigné aux enfants :
Les nombres de 0 à 9 : zéro, un, deux, trois, quatre, cinq, six, sept, huit, neuf
Les dizaines de 10 à 90 : dix, duante, trente, quarante, cinquante, soixante, septante, octante, nonante
Pour obtenir n'importe quel nombre entre 11 et 99, il suffit d'accoler le nom de la dizaine et celle de l'unité (si ce n'est pas 0) à l'aide d'un trait d'union.
Pour nommer les nombres de 100 à 999, rien de bien original : on prend l'unité correspondant aux centaines (sauf s'il s'agit de 1), et on ajoute "cent".
Pour les nombres plus grand, on regroupe les chiffres par paquets de trois, et on place le mot qu'il faut : mille (10³), million (10⁶), dillion (10⁹), trillion (10¹²), quadrillion (10¹⁵). Condorcet ne dit rien pour les nombres plus grand, à part un laconique "etc."...

La lecture des nombres est complètement simplifiée, avec un mot par chiffre ou par espace :
13 : dix-trois
21 : duante-un
42 : quarante-deux
84 : octante-quatre
2 090 002 074 : deux dillions, nonante millions, deux mille, septante-quatre

Histoire de garder quelques habitudes, les noms "million", "dillion", "trillion" et "quadrillon" prennent toujours un s au pluriel. Le mot "mille" est définitivement invariable, et plus de problème avec "vingt", puisque qu'il n'existe plus. Condorcet a pris l'habitude de mettre des virgules après les noms (bien qu'il ne donne aucune règle la dessus), on va le suivre...

Inventés lors de la révolution française, le calendrier républicain a eu son petit succès une douzaine d'années, avant que Napoléon ne s'en mêle, et le système métrique est aujourd'hui adopté par le monde entier (en oubliant cette sombre histoire d'heure décimale, qui n'est pas très bien passé - Je crois qu'un parti politique utopiste tente de le remettre à jour...). Le système révolutionnaire de Condorcet n'a en revanche pas eu la même gloire, puisqu'il a été oublié avant même d'avoir été utilisé...

Le système des myriades de Knuth
Nous sommes maintenant à la fin du XXe siècle, au moment où Conway proposait sa réforme de nomenclature des grands nombres (et ses millinillions). Donald Knuth propose lui aussi une nomenclature totalement révolutionnaire, bien plus puissante que celle de Conway (surtout en combinant les deux) et basé sur le principe de récurrence (comme tout ce que fait Knuth, en fait).
Dans le système de Conway, on change le nom des nombres à chaque fois que l'on ajoute six zéros. Dans le système de Knuth, on change le nom des nombres à chaque fois que le nombre de zéro est doublé ! Explications :

Pour les nombres de 1 à 99, on garde les noms classiques.

Pour les nombres de 100 à 9999, on utilise la dénomination traditionnelle des dates, à savoir "dizaine-unité cent dizaine-unité". Par exemple :
1515 : quinze cent quinze
4231 : quarante-deux cent trente-et-un
2000 : vingt cent

Pour les nombres entre 1,0000 et 9999,9999, on commence à grouper les chiffres par paquets de 4 (des paquets de myriades). On découpe ainsi le nombre en deux parties qui se lisent comme des nombres entre 1 et 9999, séparés par le nom "myriade". Par exemple :
1418,1515 : quatorze cent dix-huit myriades quinze cent quinze

Pour les nombres entre 1;0000,0000 et 9999,9999;9999,9999, on écrira "blabla myllions blabla", où blabla est un nombre écrit comme dans le paragraphe précédent. Par exemple :
3,0040;0001,0000 : trois myriades quarante myllions une myriade
2,0000;0000,0000 : deux myriades de myllions (la préposition "de" rend le nom plus agréable à l'oreille que "deux myriades myllions")

On continue de la même façon en prenant "byllion", "tryllion", "quadryllion", "quintyllion" etc. L'écriture des nombres par paquets de 4 utilise différents séparateurs suivant le mot à placer. Ainsi, les séparateurs seront la virgule, le point-virgule, les deux points, l'espace et l'apostrophe pour faire des groupes de respectivement 4, 8, 16, 32 et 64 chiffres.

On a donc :
10⁰ : un
10¹ : dix
10² : cent
10⁴ : une myriade (,)
10⁸ : un myllion (;)
10¹⁶ : un byllion (:)
10³² : un tryllion ( )
10⁶⁴ : un quadryllion (')
10¹²⁸ : un quintyllion

Dans la nomenclature de Conway, le quintyllion vaut cent unvigintillions, le sextyllion (10²⁵⁶) vaut dix mille duoquadragintillions, le septyllion (10⁵¹²) vaut cent quinquaoctogintillions, l'octyllion (10¹⁰²⁴) vaut dix mille septuagintacentillions, le nonyllion (10²⁰⁴⁸) vaut cent unquadragintatrecentillions et le décyllion (10⁴⁰⁹⁶) vaut dix mille duooctogintasescentillions. Puis vient l'undecyllion (10⁸¹⁹²), le duodecyllion (10¹⁶³⁸⁴), jusqu'au myryllion (10^{2^10002}), beaucoup trop long à écrire dans la notation de Conway !

La notation de Knuth simplifie énormément la lecture des très grands nombres mais possède un défaut : comment distinguer par exemple le tryllion de Knuth (10³²) du trillion de Conway (10¹⁸) [sans parler du trillion de l'échelle courte (10¹²) ] ?... Ce système est malheureusement inutilisable pour les non-avertis...

Le système roli de Guery
Alors que le système de Condorcet visait à écrire les petits nombres de manière simple et que celui de Knuth vise à écrire de manière concise les grands nombres, Marcel Guery propose en 2007 un code permettant d'écrire les petits nombres de manière concise. L'idée de base du système roli est de minimiser au maximum le nombre de syllabes : un nombre comme 829 683, qui demande 11 syllabes à être prononcé, le sera en seulement 2 une fois rolifié.

Le principe est simple : un groupe de trois chiffres sera représenté par une syllabe, construit à l'aide du code suivant :

Le code roli

Un groupe de trois chiffres s'écrit C+V+C
Un groupe de deux chiffres s'écrit C+V
Un groupe d'un seul chiffre s'écrit  V

Une syllabe représente ainsi un nombre entre 0 et 999, qui seront séparés à l'écrit par un tiret.

8 : wi
42 : kou
666 : sés
831 : chyoul
31 861 : mi-chél

Le temps de prononciation devient alors ridiculement bas ! Le nombre 789 295 317 demandera 19 syllabes pour être prononcé de manières traditionnelle, 17 dans le système révolutionnaire de Condorcet et seulement 3 dans sa version rolifiée (pwin-tyof-mip). Dans un monde utopique, on pourrait penser à une utilisation par ceux dont le métier est de trasnmettre oralement un grand nombre de chiffres. Les numéros de téléphones seraient bien plus pratique à être transmis ("-Hey, t'es charmante, tu me passes ton ré ? - Bien sûr, c'est le chyot-ryat-fit !)... En attendant, il peut servir à noter discrètement les dates historiques sur le blanco en vue d'un contrôle d'histoire...

En fait, le principal attrait de cette écriture est de pouvoir disposer de nombre dont la lecture sera amusante, comme 74 247 725,  449 940 144 467 ou 82 003 349 966 400 !

------

Et dans la plus pure tradition des articles de numération de ce blog, terminons par un traducteur des nombres en révolutionnaire, en roli ou en myriades ! Pour des raisons de place, on ne pourra écrire que des nombres inférieurs à dix byllion de quintyllions de sextyllions pour la traduiction en myriades ou en roli. La traduction dans le système de Condorcet se limite aux mots utilisés par Condorcet, de l'ordre de cent quadrillions.

 

Système révolutionnaire Système myriade Roli

 

---

Sources :
Le système révolutionnaire de Condorcet : Chez Nicolas Graner
Le système des myriades de Knuth : Chez wikipedia
Le système roli de Guery : Quadrature n°66, Octobre-décembre 2007

30 août 2009

Savez-vous compter les choux ?

Jusqu'à combien savez-vous -théoriquement- compter en français ? Un... deux... trois... (...) neuf cent quatre-vingt-dix-neuf millions neuf cent quatre-vingt-dix-neuf mille neuf cent quatre-vingt-dix-neuf...

Et après ? Un milliard ? Un billion ? Un billiard ? Un trillion ?

Mais au fait, savez-vous vraiment compter ?!

Jusqu'à 999 999 (et un peu au delà)
En français, seulement 23 mots sont nécessaires pour compter jusqu'à 999 999 : "un", "deux", "trois", "quatre", "cinq", "six", "sept", "huit", "neuf", "dix", "onze", "douze", "treize", "quatorze", "quinze", "seize", "vingt", "trente", "quarante", "cinquante", "soixante", "cent" et "mille". Pour les lecteurs belges et suisse, on peut ajouter "nonante" et "septante".

Les 999975 (999973) autres nombres sont composés et, pour les écrire, il faut savoir appliquer la règle du trait d'union et la règle du pluriel. Tous les nombres inférieurs à 999999 sont des adjectifs numéraux, contrairement aux mots comme "million" ou "milliard" qui sont des noms.

La règle du trait d'union
Les nombres composés inférieurs à 99 prennent des traits d'union partout :
vingt-trois, quarante-deux, quatre-vingt-dix-sept...
A l'exception des nombres se terminant par 1, ou la conjonction "et" remplace le tiret :
cinquante et un, soixante et un...
A l'exception de 81 et 91, pour compliquer les choses :
quatre-vingt-un, quatre-vingt-onze

Pour simplifier tout ça, l'Académie française recommande depuis 1990 de toujours mettre des tirets entre les numéraux, les noms restant en dehors de tout ça. Ainsi, "cent quarante et un millions" peut s'écrire aussi "cent-quarante-et-un millions". Mais cette recommandation fait fi de la règle n°1 de la grammaire française (à savoir : "si une règle existe, il existe une exception") et nous sommes libres de ne pas l'appliquer.

La règle du pluriel
En français, seul deux adjectifs numéraux ne sont pas invariables : "vingt" et "cent".  "Mille" reste toujours invariable... Mais attention, on ne peut leur mettre un "s" que si le mot se trouve tout à droite, ou juste avant un nom:
deux cents millions trois cent  quatre-vingts
deux cent vingt et un millions trois cent quatre-vingt-deux
quatre-vingt mille

Les noms comme "millions" ou "milliards" sont des noms, et donc s'accordent

De millions en millions
On vous le dit depuis bien longtemps : lorsque l'on écrit les nombres en tous chiffres, on les sépare par groupes de 3, ça facilite la lecture. Si nous nous comportions en bons français respectueux des choix de nos dirigeants grammaticaux, il serait plus juste de les grouper par six...

Nous nous étions arrêtés à 999999. Juste après vient le premier nombre qui ne s'écrit plus seulement avec des adjectifs, à savoir 1 000000 ("un million"). En multipliant par dix, on trouve 10 000000 ("dix millions"). En ajoutant un zéro, on trouve 100 000000 ("cent millions") et avec un autre zéro, on arrive à 1000 0000 ("mille millions", alias "un milliard"... ou "un billion" ?...).

C'est à ce moment précis que les choses se gâtent, et que le débat devient houleux entre les défenseurs du groupement des chiffres par 3 (Etats-Unis, Royaume-Uni, Irlande, Canada, ...) contre les défenseurs du groupement des chiffres par 6 (France, Espagne, Italie et globalement tout le reste de l'Europe). Au final, tout le monde utilise les mêmes mots ("millions", "billions", "trillions"...), au détail de la langue (-llions pour le français et l'anglais, -llón pour l'espagnol, -ljon pour le suédois...), mais dans les faits, les mots ne représentent pas toujours les mêmes nombres ! "Un billion" en français est égal à "un trillion" en anglais...

Le groupement des chiffres par 3 : l'échelle courte
Pour les anglophones, le groupement des chiffres se fait par blocs de 3. Dans ce système d'échelle courte, les nombres sont donc appelés par groupes de 1000 :
1 000 : mille (10³=1000¹⁺⁰)
1 000 000 : un million (10⁶=1000¹⁺¹)
1 000 000 000 : un billion (10⁹=1000¹⁺²)
1 000 000 000 000 : un trillion (10¹²=1000¹⁺³)
1 000 000 000 000 000 : un quadrillion (10¹⁵=1000¹⁺⁴)
puis viennent, en suivant les noms romains des nombres, les quintillions (10¹⁸) les sextillions (10²¹), les septillions (10²⁴), les octillions (10²⁷), les nonillions (10³⁰) et les decillions (10³³)...

Le groupement des chiffres par 6 : l'échelle longue
Pour les autres, le groupement se fait par 6, et les nombres sont appelés par groupes de 1000000 :
1000 : mille (10³)
1 000000 : un million (10⁶=1000000¹)
1 000000 000000 : un billion (10¹²=1000000²)
1 000000 000000 000000 : un trillion (10¹⁸=1000000³)
1 000000 000000 000000 000000 : un quadrillion (10²⁴=1000000⁴)
puis viennent, en suivant les noms romains des nombres, les quintillions (10³⁰), les sextillions (10³⁶), les septillions (10⁴²), les octillions (10⁴⁸), les nonillions (10⁵⁴) et les decillions (10⁶⁰) ...
Ce système (l'échelle longue) est l'original, inventé par Chuquet en 1484, où la règle était de grouper les chiffres par groupes de 6. Au milieu du XIXe, on a commencé à grouper les chiffres par 3, faisant basculer le système vers l'échelle courte. Les anglophones ont gardé l'échelle courte pendant que les continentaux ont préféré revenir au système original. On garde tout de même depuis cette époque l'habitude de grouper les nombres par blocs de 3 !

Les mots en -lliards, quand à eux, on été inventé par Pelletier en 1550. "Milliard" remplace ainsi "mille millions", "billiard" remplace "mille billions"... Les noms des nombres n'en sont que plus élégants !

Le nombre 1 002003 000000 peut se lire alors :
Un trillion deux billions trois millions (pour un anglophone)
Un billion deux milliards trois millions (pour Pelletier)
Un billion deux milles trois millions (pour Chuquet)

Le système de Chuquet permet donc de nommer n'importe quel nombre entre un et neuf cent quatre-vingt-dix-neuf décilliards neuf cent quatre-vingt-dix-neuf décillions neuf cent quatre-vingt-dix-neuf nonilliards neuf cent quatre-vingt-dix-neuf nonillions neuf cent quatre-vingt-dix-neuf octilliards neuf cent quatre-vingt-dix-neuf octillions neuf cent quatre-vingt-dix-neuf septilliards neuf cent quatre-vingt-dix-neuf septillions neuf cent quatre-vingt-dix-neuf sextilliards neuf cent quatre-vingt-dix-neuf sextillions neuf cent quatre-vingt-dix-neuf quintilliards neuf cent quatre-vingt-dix-neuf quintillions neuf cent quatre-vingt-dix-neuf quatrilliards neuf cent quatre-vingt-dix-neuf quatrillions neuf cent quatre-vingt-dix-neuf trilliards neuf cent quatre-vingt-dix-neuf trillions neuf cent quatre-vingt-dix-neuf billiards neuf cent quatre-vingt-dix-neuf billions neuf cent quatre-vingt-dix-neuf milliards neuf cent quatre-vingt-dix-neuf millions neuf cent quatre-vingt-dix-neuf mille neuf cent quatre-vingt-dix-neuf ! (10⁶⁶-1 = 1000000¹¹-1)

Si on s'arrêtait simplement aux mots reconnus par le dictionnaire français, on s'arrêterait au sextillion. Les mots utilisés pour désigner les nombres au delà du septillion n'existe pas officiellement !

De millinillions en millinillions !
Pour aller au delà, il faudrait se pencher sur l'écriture des nombres en latin, ce qui n'est guère engageant à première vue, et qui apporte son lot d'approximations. Ainsi, les orthographes quadrillion et quatrillon sont acceptées pour écrire 10²⁴...
Il fallait un super héros pour fixer tout ça, et c'est John Conway (toujours dans les bons coups) qui est arrivé ! Aidé par Wechsler, il a mis au point le système actuellement utilisé pour la nomenclature systématique des grands nombres.

Dans un premier temps, commençons simple, en apprenant comment nommer tous les nombres de 1 à 1000000⁹⁹⁹ (=10^6×999). Pour l'instant, on ne connaît que les 9 premiers nombres en -illions grâce aux premières unités latine :

Tableau des unités seules

Pour le n-ième (pour n entre 10 et 999), il suffit simplement de consulter le tableau suivant :

Tableau des 999 premiers nombres en -illion

Le cdu-ième nombre en -illion s'écrira u-d-c-llion, en remplaçant u, d et c par les préfixes adéquats, et en ajustant les liaisons (si les lettres entre parenthèse correspondent, elles apparaitront). Dans le cas où il n'y a pas de centaine, le 'a' se transforme en 'i'. (Attention tout de même, puisque les unités arrivent en premier)

Par exemple, le n-ième nombre en -illion s'écrit :
n = 186 : un sexoctogintaseptingentillion (=10^6×186)
n = 42 : un duoquadragintillion (=10^6×42)
n = 807 : un septemoctingentillion (=10^6×807)
n = 999 : un novenonagintanongentillion (=10^6×999)
n = 4 : un quadrillion (celui-ci se lit dans le premier tableau)

Et pour n = 1000 ?
C'est là que le système de Conway est génial, puisqu'il permet d'écrire en toutes lettres n'importe quel nombre ! Il s'écrit un millinillion !

En fait, pour écrire le N-ième nombre en -illion, on commence par écrire N en regroupant par blocs de 3 chiffres (comme d'habitude). On transcrit ensuite chaque bloc selon les règles déjà énoncées en intercalant "lli". Si le bloc est 000, on écrit "ni".

Par exemple, le n-ième nombre en -illion s'écrit :
n = 186 042 : un sexoctogintaseptingentilliduoquadragintillion (=10^6×186042)
n = 807 999 : un septemoctingentillinovenonagintanongentillion (=10^6×807999)
n = 005 000 000 : un quintillinillinillion  (=10^{30 000 000})

Maintenant, vous pourrez dire "Je sais compter (presque) jusqu'à l'infini" !

A titre d'exercice : comment écrire ce nombre en tous chiffres ?
Trente et un sedécilliards quatre cent quinze sedécillions neuf cent vingt-six quinquadécilliards cinq cent trente-cinq quinquadécillions huit cent quatre-vingt-dix-sept quattuordécilliards neuf cent trente-deux quattuordécillions trois cent quatre-vingt-quatre tredécilliards six cent vingt-six tredécillions quatre cent trente-trois duodécilliards huit cent trente-deux duodécillions sept cent quatre-vingt-quinze undécilliards vingt-huit undécillions huit cent quarante et un décilliards neuf cent soixante et onze décillions six cent quatre-vingt-treize nonilliards neuf cent quatre-vingt-treize nonillions sept cent cinquante et un octilliards cinquante-huit octillions deux cent neuf septilliards sept cent quarante-neuf septillions quatre cent quarante-cinq sextilliards neuf cent vingt-trois sextillions soixante-dix-huit quintilliards cent soixante-quatre quintillions soixante-deux quadrilliards huit cent soixante-deux quadrillions quatre-vingt-neuf trilliards neuf cent quatre-vingt-six trillions deux cent quatre-vingt billiards trois cent quarante-huit billions deux cent cinquante-trois milliards quatre cent vingt et un millions cent soixante-dix mille six cent soixante-dix-neuf.

---

Sources :
Wikipedia : Nom des grands nombres
Générateur de nombre en toutes lettres (pour n'importe quel nombre entre 0 et ... pour n'importe quel nombre !)

19 avril 2008

Goodstein contre l'Hydre

Précédemment sur ce blog :
    La suite de Goodstein (de graine 6), qui commence comme ça : 6, 29, 257, 3125, 46655, 98039, 187243, ... Mais comment est définie cette suite ?  On part d'un nombre [...] qui sera le premier terme de la suite. [...] On le décompose en base 2 itérée [...] On remplace ensuite tous les 2 par des 3. [...]On soustrait ensuite 1, et on obtient le deuxième terme de la suite. Pour obtenir le suivant, on décomposera ce nombre en base 3 itérée, et on remplacera les 3 par des 4, et ainsi de suite. [...] Toutes les suites de Goodstein se terminent par 0 ! [...]

==Générique== Palam palam pam pam ==/Générique==

Aujourd'hui, je vais tenter quelque chose de dingue : démontrer le théorème de Goodstein ! (Je vous renvois à l'article d'il y a 3 semaines pour le (re?)découvrir, et à celui de la semaine dernière pour toutes les histoires d'ordinaux). Si cette histoire ne vous plaît pas, vous pourrez redécouvrir le deuxième des douze travaux d'Hercule un peu plus bas...

Mais juste avant de commencer, une petite chose à ajouter à l'article de la semaine dernière à propos des ordinaux, indispensable pour la  démo de Goodstein : toute suite décroissante d'ordinaux parvient à 0 après un nombre fini d'étapes (comme c'est le cas pour les entiers)
Prenons par exemple une suite strictement décroissante d'ordinaux qui commence à ω+5. Après 5 étapes au maximum, on atteindra ω. Un nombre strictement plus petit que ω n'est pas ω-1 (qui n'a aucun sens) mais un nombre entier n. On doit obligatoirement faire un "saut". On arrive alors dans les nombres entiers, et la suite décroissante atteindra 0 après n étapes (au maximum).  On ne peut pas prévoir le nombre d'étape, mais on est sûr qu'il s'agira d'un nombre fini d'étapes.

L'idée de la démonstration est de faire correspondre à chaque élément de la suite de Goodstein un équivalent ordinal. Par la suite, on va prendre ces notations là:
u_n : n-ième terme de la suite de Goodstein
d_n->n+1 : transformation des n en n+1 dans l'écriture en base n itérée.

Le principe de la suite de Goodstein se résume essentiellement comme ça :

Maintenant, on va définir une super-transformation D_n sur le même principe que d_n->n+1, mais au lieu de transformer les n en n+1, on va transformer les n en ω !
Petit exemple :

(Bon, évidement, l'expression finale est vraiment tordue, mais elle représente bien un ordinal)

Trois choses à voir avec cette super-transformation :
* Appliquer D_n, c'est la même chose que appliquer d_n->n+1 puis D_n+1. En effet, la première transforme les n en ω, et la deuxième transforme les n en n+1 puis en ω.
* Cette transformation est strictement croissante : si on a u < v, on aura forcément D_n(u) < D_n(v).
* Si D_n(x)=0, c'est que x=0.

Il y a juste à remarquer que la suite U_n=D_n-1(u_n) est une suite strictement décroissante d'ordinal : elle tombera donc sur 0 après un nombre fini d'étapes, tout comme u_n ! CQFD comme on dit dans le métier.

---

Un autre problème dans le même style (qui demande aussi de passer par les ordinaux pour être démontré) est celui du deuxième des 12 travaux d'Hercule : tuer l'hydre de Lerne.

L'Hydre de Lerne est un serpent d'eau à corps de chien possédant de multiples têtes qui peuvent se régénérer, ainsi qu'une haleine empoisonnée pour corser un peu les choses.

Kirby et Paris ont bien étudié les hydres, et ils se trouvent qu'ils ressemblent tous plus ou moins à un arbre (dans le sens de graphe), comme on peut en voir un exemple juste à gauche.
Pour tuer un tel hydre, il faut lui couper ses têtes :
* Lorsque l'on coupe une tête directement reliée au corps, celle-ci ne repousse pas.
* Si elle n'est pas reliée au corps, l'ensemble des coups et têtes reliés à des nœuds inférieurs peuvent se dupliquer autant de fois que l'hydre le décide (Mais un nombre fini de fois).

Quelle stratégie doit prendre Hercule pour détruire toutes les têtes ?

Imaginons que Hercule décide de couper la tête la plus à droite (en rouge, ici). L'hydre va pouvoir dupliquer en deux temps ses têtes ; d'abord à partir du nœud le plus proche de la tête, l'hydre va se dupliquer en 4 exemplaires, et dans un deuxième temps, elle va dupliquer toute la partie droite à partir du corps (ici, en deux exemplaires). Il ressemblera alors à ceci :

Hercule n'a plus qu'à choisir quelle nouvelle tête il va couper, si possible, sans désespérer de le tuer un jour.

En fait, même si l'hydre fait preuve de vice (dans le nombre de duplications) et Hercule preuve d'une extrême stupidité (dans le choix des têtes qu'il va choisir de couper), Hercule finira un jour par anéantir totalement l'hydre. (Après un nombre fini de têtes tranchées)

De la même façon que pour la suite de Goodstein, on ne peut pas utiliser la simple récurrence pour montrer que Hercule terminera un jour son travail, mais on peut le démontrer en utilisant les ordinaux !

Le seul problème, c'est que l'Univers risque de se détruire avant que Hercule ait terminé le boulot, vu le temps qui sera nécéssaire... L'histoire raconte que Hercule appela son oncle à la rescousse, enflamma quelques arbres pour cautériser les moignons de cou...

---

Sources :
Pour la science - n°278 - décembre 2000
Le coq et l'Hydre [pdf] (pour la démo de cette histoire d'Hydre)

30 mars 2008

Ne pas croire ce qui croît

Une célèbre conjecture lycéenne dit que si une suite a l'air simple (1), à l'air de grimper vite au vu de sa définition (2) et a une croissance à peu près régulière sur ses premiers termes (3), alors cette suite est croissante ! Il est temps de vérifier la validité de cette étonnante conjecture !

Cette conjecture se vérifie bien avec des suites définies à base de fonctions puissances, du genre U_n=2ⁿ. La suite a l'air simple, elle a l'air de grimper vite au vu de sa définition (ya une puissance, quand même) et a une croissance régulière, et même de plus en plus rapide, sur ses premiers termes (2, 4, 8, 16, 32, 64, 128...). Cette suite est bien croissante !

Prenons un autre exemple, alors : la suite de Goodstein (de graine 6), qui commence comme ça :
6, 29, 257, 3125, 46655, 98039, 187243, ...
Avec un petit graphique, ça donne :

Sur ses 30 premiers termes, cette suite a l'air de grimper de plus en plus vite, on vérifie bien la troisième partie de notre conjecture.

---

Mais comment est définie cette suite ?

* On part d'un nombre, (la graine, ici 6) qui sera le premier terme de la suite.

* On le décompose en base 2 itérée. C'est comme décomposer le nombre en base 2 (En somme de puissances de 2), sauf qu'on décompose également les puissances en base 2, jusqu'à n'avoir que des nombres inférieurs ou égaux à 3.*
Exemple avec 303 :
En base 2, 303 s'écrit  1×2⁸+0×2⁷+0×2⁶+1×2⁵+0×2⁴+1×2³+1×2²+1×2¹+1×2⁰
(Qui s'écrit plus agréablement 2⁸+2⁵+2³+2²+2+1)
Ensuite, on remplace 8, 5 et 3 par leur décomposition en base 2, ce qui donne :
Il reste encore un 3, donc on le remplace par 2+1, ce qui donne la décomposition de 303 en base 2 itérée:

La décomposition de 6 en base 2 itérée est plus facile : 6=2²+2

* On remplace ensuite tous les 2 par des 3.
À partir de 303, on aurait (Ce qui vaut a peu près 4,43×10³⁸)
À partir de 6, on aurait 3³+3 (=30)

* On soustrait ensuite 1, et on obtient le deuxième terme de la suite. Pour obtenir le suivant, on décomposera ce nombre en base 3 itérée, et on remplacera les 3 par des 4, et ainsi de suite.

Voici un petit script permettant de voir ces suites (Qui bugue dès que les valeurs deviennent trop grandes, ce n'est que du javascript) (Si je savais mettre du LaTeX directement dans mes pages, il y en aurait dans ce script, mais en attendant, il n'y a que la syntaxe...)

Nombre à transformer :
  Nombre de pas :

En tout cas, cette suite a une définition, certes tordue, mais assez simple. Elle ne met en jeu que la décomposition d'un nombre en une certaine base, et des remplacements. Elle vérifie bien le critère 1 de simplicité.
Et à le regarder de loin, on a des puissances de plus en plus grandes, ya pas de raisons, d'après sa définition, elle a l'air de plus en plus grande.
D'après notre géniale conjecture qui simplifie grandement le travail des mathématiciens, cette suite est toujours croissante !

Et évidement, si je parle de cette suite ici, c'est parce qu'elle contredit notre conjecture stupide :
Toutes les suites de Goodstein se terminent par 0 ! Saperlipopette !

---

Expliquons quand même ce mystère, je suis là pour ça.

La suite qui commence par 2 n'est pas la plus intéressante :
(Le D_i->j désigne la transformation des i en j)
U₀ = 2
U₁ = D_2->3(2)-1 = 3-1 = 2
U₂ = D_3->4(2)-1 = 2-1 = 1
U₃ = D_4->5(1)-1 = 1-1 = 0

La suite qui commence par 3 n'est pas la plus intéressante non plus :
U₀ = 3
U₁ = D_2->3(2+1)-1 = (3+1)-1 = 3
U₂ = D_3->4(3)-1 = 4-1 = 3
U₃ = D_4->5(3)-1 = 3-1 = 2
U₄ = D_5->6(2)-1 = 2-1 = 1
U₅ = D_6->7(1)-1 = 1-1 = 0

Mais celle qui commence par 4  est déjà plus intéressante :
U₀ = 4
U₁ = D_2->3(2²)-1 = (3³)-1 = 26
U₂ = D_3->4(2.3²+2.3+2)-1 = 2.4²+2.4+1
U₃ =  2.5² + 2.5 + 0
U₄ = 2.6² + 6 + 5
U₅ = 2.7² + 7 + 4
U₆ = 2.8² + 8 + 3
etc.
Ce que l'on peut remarquer, c'est qu'à partir du deuxième terme, la décomposition est toujours de la forme a.p²+b.p+c. Le nombre p est la base dans laquelle est décomposé le nombre (qui vaut n+2, n étant l'indice de la suite). En effet, la décomposition itérée en base p (>2) n'affectera pas les puissances, les seuls nombres qui seront modifiés par le remplacement seront les p)
Ainsi, quand on ne s'intéresse qu'aux coefficients a, b et c, on peut voir la suite comme ça :

* Quand le coefficient c est différent de 0, il n'y a que lui qui sera atteint par le -1.
* Si c=0 et b≠0, le coefficient b sera décrémenté, et c prendra la valeur p-1.
En effet, à la base p, on aura U_n = a.p²+b.p et donc, U_n+1 = a.(p+1)²+b.(p+1)-1. (Ce qui n'est pas une décomposition acceptable, il nous la faut en somme) On la transforme alors :
U_n+1 = a.(p+1)²+b.(p+1)-1 = a.(p+1)²+(b-1).(p+1)+(p+1)-1 = a.(p+1)²+(b-1).(p+1)+p
* Si a≠0, b=0 et c=0, c'est a qui sera décrémenté ; b et c prendront les valeur courantes de la base.

En fait, les valeurs a b et c fonctionnent comme un compte à rebours. La différence, c'est qu'au lieu d'être en base 60 (1 h 00 min 00 sec -> 0h 59 min 59 sec...), c'est une base qui change en permanence, et qui est croissante.

Ainsi, les coefficients a b et c vont bien arriver à 0 à un moment ou un autre... Pour être précis, elle atteindra la valeur 0 lorsque p sera égal à (A peu près 120 millions de chiffres...)

Ca, c'est pour la suite qui commence par 4. Celle-ci a pour particularité de ne pas grandir si vite que ça... Si on commence par 18 ou 19, ça ira beaucoup plus vite au début ! Mais l'idée du compte à rebours reste à peu près valable.

---

 

Le théorème de Goodstein, qui dit que toute suite de Goodstein se termine par 0, est un théorème d'arithmétique. Il traite de nombre entier et n'utilise que des notions d'arithmétiques. Mais ce qui est fâcheux, c'est que c'est un théorème indémontrable... d'un point de vue arithmétique !

Kirby (La boule rose, pas le mathématicien)

Pour le démontrer, il faut passer utiliser des notions d'infinis (une sombre histoire d'ordinaux infinis) qui dépasse de loin le cadre de la théorie de l'arithmétique dans lequel le théorème est énoncé. Il est donc impossible de démontrer ce théorème par récurrence, même avec la meilleure imagination du monde, et ça, c'est Laurence Kirby (pas la boule rose, le mathématicien) et Jeffrey Paris qui le disent (Et ils l'ont rigoureusement démontré) !

---

Sources :
Pour la science n°278 Décembre 2000, L'infini est-il nécessaire ?

10 février 2008

Racines treizièmes vs racines 1789emes

Petit jeu : A votre avis, quelle est la chose la plus difficile à réaliser mentalement entre :
- Trouver la racine carrée d'un nombre à 80 chiffres aléatoire (ce nombre étant un carré parfait)
- Trouver la racine 13eme d'un nombre à 100 chiffres aléatoire (ce nombre étant une puissance 13eme parfaite)
- Trouver la racine 1789eme d'un nombre à 7000 chiffres aléatoire  (ce nombre étant une puissance 1789eme parfaite)

(Alexis Lemaire calcule en 72 secondes la racine 13e d'un nombre à 200 chiffres, 15 novembre 2007)

Si je pose la question, c'est qu'il y a évidemment un piège, le paradoxe de la fausse difficulté ! Extraire une racine 1789eme d'un nombre à 7000 chiffres est un jeu d'enfant, alors qu'aucun "prodige" en math n'a pu extraire de tête une racine carrée d'un nombre à 80 chiffres.

Petite explication
Le nombre p à 7000 chiffres tiré aléatoirement sera une puissance 1789 parfaite : sa racine 1789eme sera donc un nombre entier. On peut se poser la question dans l'autre sens : comment faut il choisir un nombre pour que, élevé à la puissance 1789, donne un nombre de 7000 chiffres ?
Un petit calcul donne la solution, il faut que ce nombre k satisfasse l'inégalité suivante (r étant la puissance, l la longueur des nombre) :

Dans notre cas, avec l=7000 et r=1789, on trouve que le nombre que l'on va devoir retrouver est compris entre 8171 et 8180, ce qui signifie qu'il n'y a en fait que 10 solutions possibles. Il suffit d'apprendre les 10 puissances 1789 parfaites à 7000 chiffres, et on trouve directement la réponse... Ca reste encore compliqué.

Heureusement, 1789 est un nombre de la forme 4k+1, et quand on élève un nombre à une puissance 4k+1, la dernière décimale du nombre reste la même (, démonstration pas bien compliquée avec des congruences et une récurrence).

Ainsi, la racine 1789 de ce nombre à 7000 chiffres (Cliquez pour agrandir):

- Est compris entre 8171 et 8180
- Termine par un 4
La solution est donc 8174 !

En faisant les mêmes calculs pour l=13 (nombre de la forme 4k+1) et n=100 nous informe que la racine treizième d'un nombre à 100 chiffres :
- est compris entre 41246264 et 49238826 (commence par 4, donc)
- ont le même chiffre des unités
Cela ramène le problème à trouver le nombre de la forme 4xxxxxxu, seulement 6 chiffres à trouver, ce qui est faisable en quelques minutes avec beaucoup d'astuce et d'entraînement.

Pour la racine treizième de nombre à 200 chiffres, il va falloir retrouver un nombre entre 2.03×10¹⁵ et 2.42×10¹⁵. Cela laisse tout de même 12 chiffres inconnus, la difficulté de faire ceci mentalement reste bien présente !

 

En fait, la difficulté de ces problème ne dépend pas comme on pourrait le penser de la longueur des données, mais de celle des informations à calculer soi-même. Rien dans le troisième problème, toutes dans le premier problème...

Cela explique également pourquoi ces évènements de calcul mental se font sur des racines treizièmes. Il faut déjà un nombre premier (calculer une racine neuvième, c'est calculer 2 fois une racine cubique), mais surtout c'est bien plus impressionnant de calculer la racine treizième d'un nombre à 100 chiffres que la racine carrée d'un nombre à 13 chiffres, alors que les difficultés restent comparables !
Cela n'enlève cependant pas la difficulté d'extraire une racine treizième d'un nombre de 200 chiffres de tête en 70 secondes... Mais ça reste quand même plus facile que d'en trouver la racine carrée... Toutes proportions gardées...

---

Sources :
Plus que largement inspiré de cet article

13 janvier 2008

Découpages curvilignes et dissections tridimentionelles

Faire du découpage avec des polygones, c'est bien.
Faire du découpage avec des surfaces délimitées par des courbes, c'est encore mieux !
(Ca permet par exemple la transformation d'une croix pattée alésée arrondie en carré)

Et les surfaces curvilignes ?
Toujours sur leur problème de quadrature du cercle, il arrivait que les grecs lâchent leur règle & compas au profit de ciseaux. Peut-on découper un cercle de manière à pouvoir à former un carré ? (Même si les découpages ne sont pas traçables à la règle et au compas)
En effet, pour calculer les aires de certaines surfaces (appelées "lunules"), les Grecs commençaient par les découper pour former des carrés, et ensuite, calculer leur aires. C'est donc naturellement qu'est arrivé le problème de la quadrature du cercle en découpage, posé par Hippocrate de Chios (vers -430)

Exemple de lunule grecque

Pour la solution, il faut attendre 1963, avec Dubins, Hirsch et Karush : c'est impossible ! On ne peut pas découper un cercle pour former un carré, un triangle, une ellipse.
Enfin, ça, c'est seulement si on impose aux découpages d'être des courbes régulières et de former de beaux morceaux.
En 1925, Tarski repose à nouveau la question, en permettant de faire des morceaux qui ne ressemble à rien qui puisse exister ou être imaginé...

Il faut attendre 1989 pour que Miklós Laczkovich propose sa façon personnelle de découper le cercle de manière à obtenir un carré. Malheureusement, il m'est impossible de fournir une représentation graphique ;
- Le découpage qu'il propose compte plus de 10⁵⁰ pièces.
- Les pièces sont d'une complexité hallucinante (pire que des fractals)...
- Ces pièces n'ont même pas d'aire...
- Et ces pièces ne sont pas bien définies... En effet, le découpage nécessite l'utilisation de l'axiome du choix. (J'en reparlerai de manière plus précise la semaine prochaine)

Et la 3eme dimension ?
Transformer un polygone en un autre polygone avec des ciseaux, c'est faisable sans (trop de) problèmes. Et transformer un cube en tétraèdre (pyramide) à l'aide seulement d'un bon couteau, est-ce faisable ?

Pour fêter le deuxième congrès international de mathématiques en 1900, David Hilbert ramène une liste de 23 problèmes tenant en échec jusqu'alors les mathématiciens. Avec ces problèmes, Hilbert comptait bien faire bosser les matheux pendant tout le siècle.  Il a vu juste, puisque certains problèmes ne sont toujours pas résolus...
Ici, c'est le troisième problème de Hilbert qui nous intéresse :
"Étant donnés deux polyèdres d'égal volume, peut-on découper le premier polyèdre en des polyèdres et les rassembler pour former le second polyèdre ?"
(Cette question fait suite à la question en 1844 de Gauss : "un polyèdre et son reflet dans un miroir ont-ils le même volume ?" La démonstration utilisait l'infini, ce qui est loin d'être élégant pour démontrer un théorème aussi simple. Gerling répondit à Gauss en proposant de découper le polyèdre en tétraèdre, et de transformer chaque tétraèdre en son symétrique par découpage. Les volumes seront ainsi bien gardés.)

Deux ans plus tard, Max Dehn donnait la réponse : non ! Il a montré qu'on ne pouvait transformer un cube en tétraèdre régulier (pyramide à base triangulaire) avec un nombre fini de morceau.
Pour ça, Dehn s'est intéressé aux angles aux sommets des polyèdre, et inventa "l'invariant de Dehn" (un nombre obtenu après un calcul compliqué à parti des angles aux sommets) qui caractérise les polyèdres. Après avoir remarqué que faire des découpage dans ces polyèdres conservait cet invariant (Pour que deux polyèdres soient équidécomposables, il est donc nécessaire qu'ils aient le même invariant de Dehn), il s'est empressé de calculer celui du cube et celui du tétraèdre. Celui du cube est nul, celui du tétraèdre ne l'est pas : il est impossible de découper le premier pour former le deuxième. CQFD.

Mais le plus beau dans cette histoire, ce que Dehn ne pensait pas en inventant son invariant, s'est réalisé en 1965 : Jean-Pierre Sydler a montré que pour que deux polyèdres soient découpables/recomposables, avoir le même volume et le même invariant de Dehn est suffisant !

Finalement, cette histoire de classer les différents polyèdres selon leur invariant, et permettre aux fans de la découpe de ne pas chercher dans le vide.
On apprend ainsi ravi que le cube, le dodécaèdre rhombique, l'octaèdre tronqué, le dodécaèdre rhombique étoilé, le prisme pentagonal ou le prisme hexagonal peuvent tous s'entredécouper !

(Tout un tas de belles illustrations à voir là-bas)

Mais Tarski (celui qui a posé la question de la quadrature du cercle avec des morceaux qui ne ressemblent à rien) n'a pas dit son dernier mot, surtout avec la 3eme dimension !... Comment découper une sphère en or de manière à en obtenir deux, vous le saurez la semaine prochaine ! (Et encore un gros suspens !)

---

Sources :
Les découpages artistiques - Pour la science n°257, mars 1999 (On ne change pas une revue qui marche)
Le point sur le troisième problème de Hilbert (pdf), par Pierre Cartier
Les illustrations des polyèdres proviennent de Mathworld.

---

09 décembre 2007

Quatre quatres codec !

Grenelle de l'environnement, plan Borloo, 2600€ de malus à l'achat d'un 4×4... Et si je parlais du problème d'arithmétique récréative, le problème des quatre quatres ? Et paf, dans l'actu !

Le problème basique des Quatre quatres est celui-ci : avec les 4 opérations élémentaires (celles des chiffres et des lettres, l'addition (+), la soustraction (-), la multiplication (×) et la division (/)), quatre 4 et autant de parenthèses qu'il faut, il faut écrire tous les entiers naturels (du moins, le plus possible).
A noter que ce n'est pas si évident que ça, mais voici quand même la solution.

0 = 4+4-4-4
1 = 4/4 × 4/4
2 = 4/4 + 4/4
3 = (4+4+4)/4
4 = 4 + 4×(4-4)
5 = (4×4+4)/4
6 = 4 + (4+4)/4
7 = 4 + 4 - 4/4
8 = 4 + 4 + 4-4
9 = 4 + 4 + 4/4

Niveau 0
Et pour 10 ? Et bien, avec les règles du départ, c'est tout simplement impossible ! Heureusement, on peut élargir les règles, en permettant :
- La concaténation : écrire 44 avec deux 4
- La racine carrée : v(4) = 2
- La puissance : 4⁴ = 256
- La factorielle : 4! = 24
- La virgule (enfin, le point) : .4 = 0,4 = 2/5

Et avec tout ça, on peut joyeusement continuer :
10 = 4 + √4 + √4 + √4
11 = 44/√(4×4)
12 = 4 ×(4-4/4)
13 = 4! - 44÷4
...

Et ainsi de suite... La question est entière : jusqu'où peut-on aller avec beaucoup de patience ?
Et bien, avec les règles données, il sera impossible de trouver 73.

Niveau 2
(Parce qu'il n'y a pas de niveau 1, j'ai repris la numérotation de David A. Wheeler)
Heureusement, on peut encore élargir les règles données, en ajoutant la possibilité d'écrire .4 (qui signifie 0,444..., alias 4/9).

On peut donc joyeusement continuer :

74 = (4! + 4)/.4 +4
75 = [4!/(.4+.4)]/.4
76 = 4!/.4 + 4×4

Et ainsi de suite, jusqu'à... 112.

Niveau 3 & 4
Il nous faut encore avancer... Pourquoi ne pas permettre de faire des racines n-ièmes, avec un n arbitraire ? Par exemple, on pourra écrire .
Mais en fait, même avec cette fonction, on ne peut pas écrire 113... !

On a alors besoin d'une nouvelle opération pour pouvoir avancer. La fonction qui aura la chance de nous aider à avancer sera alors... La fonction Gamma d'Euler !
Cette fonction est une généralisation de la factorielle à l'ensemble des nombres complexes, mais elle nous intéresse ici grâce à la relation Γ(n)=(n-1)!

Maintenant, on peut vraiment y aller gaiement :
113 = Γ(Γ(4)) - (4!+4)/4
114 = 44/.4 + 4
115 = (√4 + 44)/.4
116 = (4/4 + 4)!-4
etc.

Et jusqu'à où peut on aller ? La réponse, c'est 196. 197, c'est pas possible...

Niveau 5 & 6
Il nous faut encore d'autres opérateurs pour avancer ! Pourquoi pas %, le signe du pourcentage ? Ca donne une division par 100 gratuite !

C'est une bonne idée, mais ça ne servirait à rien pour obtenir 197. Il va falloir utiliser l'opérateur ². C'est vrai, c'est un peu de la triche, c'est un 2 et pas un 4, mais on a quand même l'ensemble des entiers naturels à écrire...

Et hop :
197 = [(4! + 4)² + 4]/4
198 = 44 × √4/.4
199 = Γ(4)!/(4 - .4) - Γ(√4)
200 = 4×44 + 4!

Et on continue comme ça jusqu'à... 1650... Il va encore falloir trouver de nouveaux opérateurs pour obtenir 1651...

Niveau 7 et supérieur
Et pour continuer, il va falloir utiliser des fonctions encore plus ardues, comme les opérateurs booléens ET, OU et XOU (à partir de la représentation binaires). Avec ceci, on peut atteindre 2236. Il faudra ensuite d'autres opérateurs booléens, qui permettraient d'aller jusqu'à au moins 40000.

On aurait pu parler d'autres opérateurs, comme les combinaisons, la sous-factorielle, les notations rep-digits ou la fonction partie entière.

Solution universelle
En tout cas, pour être sûr d'avoir tous les entiers, il faudrait ajouter la fonction logarithme, qui fournit la solution universelle :

---

Sources :
Le site de Gérard Villemin : toutes les solutions de 1 à 70
The Definitive Four Fours Answer Key : toutes les solutions de 0 à 40000 (à lire absolument !)
Wikipédia : parce que wikipédia, des fois, c'est bien.

18 novembre 2007

Vive les castors

Non, l'informatique, ce n'est pas que Windows et ses bugs ou Mac et ses non-bugs, c'est aussi la programmation. Et la programmation, ce n'est pas qu'un écran noir devant lequel un informaticien à lunette tape d'étranges lignes de code, c'est bien plus que ça... Surtout que la programmation a été inventée avant l'informatique, grâce à Turing et sa machine...
Et les castors, dans tout ça ? Patience, ils arrivent...

Bref, une machine de Turing, qu'est ce que c'est ?
C'est une machine théorique composée
- d'un ruban (de longueur infinie, constitué de cases contenant des symboles ("0","1",...). Initialement, presque toutes les cases sont remplies de "0")
- d'une tête de lecture/écriture
- d'une table d'actions suivie par la tête de lecture.

Initialement, la tête de lecture est à la place 0 du ruban, et l'état de la machine est 0.
La machine lit alors la case sur laquelle se trouve la tête de lecture, et, suivant le symbole lu et l'état de la machine, exécute une action décrite dans la table, composée de trois étapes:
- La tête écrit un nouveau symbole sur la case où elle se trouve
- La tête effectue un mouvement vers la droite où la gauche
- L'état de la machine change
Les deux dernière étapes peuvent être remplacées par une étape "STOP" qui arrête toute exécution de la machine

En pratique, qu'est ce que ça donne ? Un petit exemple :
On part d'un ruban rempli de "0", de l'état 0, et on prend cette table d'action :

Étape 1 (état 0) : la tête est en position 0, elle lit "0". Elle va donc écrire "1", se déplacer à droite, et se mettre dans l'état 1
Étape 2 (état 1) : la tête est en position 1, elle lit "0". Elle écrit alors "1", se déplace à gauche, et revient en état 0.
Et ainsi de suite...

Rien de tel qu'une "vraie" machine de Turing pour voir ce que ce programme donne ;
Copiez-y ce programme :
0 . 1 x D
0 x 1 . D
1 . 0 x G
1 x 2 . D
2 . 0 x D
2 x 3 . =

On remarque alors que ce programme ne sert à rien, puisqu'il ne s'arrête jamais... Mais on peut tout à fait faire des programmes qui servent à quelque chose, c'est un langage de programmation comme un autre (peut-être juste un peu plus compliqué, mais pas plus limité... L'exemple du crible d'Érathostène est donné sur la page linkée). On pourrait, un jour de gros ennui, programmer Windows avec une machine de Turing...

Historiquement, la machine de Turing, concept de base de l'informatique théorique, a été inventée par Alan Turing bien avant l'invention de l'ordinateur. Elle servait alors à donner une définition d'un algorithme. Aujourd'hui, on s'en sert toujours en informatique théorique pour résoudre des problèmes de complexité ou de calculabilité.

Et cette histoire de castors, alors, qu'est ce que c'est ?
Un "castor affairé", c'est LA machine de Turing à n états et à 2 symboles ("0" et "1") qui est capable d'écrire le plus de "1" à partir d'un ruban rempli de "0", et qui s'arrête au bout d'un moment.
(Il faut imaginer tout un tas de castors occupés à grignoter des bandes selon leur ensemble de règles, et chercher le castor le plus bosseur parmis ceux-là...)

Par exemple, le castor affairé à 2 états est celui-ci :
0 . 1 x D
0 x 1 x G
1 . 0 x G
1 x 2 x =

Cette machine de Turing est capable d'écrire 4 "1", en 6 étapes.
Il est impossible de trouver une machine à 2 états et 2 symboles capable d'écrire encore plus de "1", et capable de s'arrêter seule.

Maintenant, vous pouvez tenter de trouver le castor affairé pour n=3, n=4 ou n=5... Enfin, ça, c'est ce que l'on peut penser, puisque trouver un castor affairé est quelque chose de très difficile.

Pour n=3, le castor écrira 6 "1", en 21 étapes :
0 . 1 x d
0 x 3 x d
1 . 1 x g
1 x 2 . d
2 . 2 x g
2 x 0 x g

Pour n=4, on peut trouver une machine qui peut en écrire 13, en 107 étapes :
0 . 1 x d
0 x 1 x g
1 . 0 x g
1 x 2 . g
2 . 4 x d
2 x 3 x g
3 . 3 x d
3 x 0 . d

Ces castors affairés permettent de définir la fonction de Radó et la fonction BB(n) :
Rado(n), ou Σ(n), désigne le plus grand nombre de 1 que l'on peut écrire avec une machine de Turing à n états
BB(n) (De "Busy Beaver", "Castor affairé" en anglais) ou S(n) donne le nombre d'étapes de la machine de Turing correspondant à Rado(n).
Les premiers termes sont dont :
Rado(0)=0
    BB(0)=0
Rado(1)=1
    BB(1)=1
Rado(2)=4
    BB(2)=6
Rado(3)=6
    BB(3)=21
Rado(4)=13
    BB(4)=107
A première vue, ces suites n'ont pas l'air de grandir si vite que ça, et pourtant...
Pour n=5, on ne connait pas les valeurs exactes, la seule chose que l'on sait, c'est que Rado(5)>4098 BB(5)>47 176 870, record trouvé en 1989 par Marxen et Buntrock, qui tient toujours.
Pour n=6, le record date de novembre 2007 (ce mois-ci, en fait), avec Rado(6)> 2.5 × 10⁸⁸¹ et BB(6)>8.9 × 10¹⁷⁶².
Il est improbable que l'on connaisse un jour la valeur exacte de BB(5) ou BB(6), sans parler de BB(7) ou de BB(100)...

 

La particularité de ces suites, c'est qu'elles ne sont pas calculables : on ne peut pas fabriquer d'algorithme permettant d'en avoir la valeur exacte.
De plus, ces suites croissent plus vite que n'importe quelles suites calculables, comme la suite des factorielles, des suites construites avec des puissance, avec la notation de Knuth ou celle de Conway. (Rappelez-vous)

 

Bref... La suite BB(n) permet à coup sûr de gagner au jeu du "Mon papa, c'est le plus fort !" !

---

Sources :
Historique de tous les records de castors affairés.
Wikipédia, avec la preuve de l'incalculabilité de Σ(n)

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

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 :

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

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 millions (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 (10¹²), le quatrillion (10¹⁵), le quintillion (10¹⁸), le sextillion (10²¹), le septillion (10²⁴), l'octillion (10²⁷) etc.
    Selon la règle officielle, on a ensuite le billion (10¹²), trillion (10¹⁸), le quatrillion (10²⁴), le quintillion (10³⁰), le sextillion (10³⁶), le septillion (10⁴²), l'octillion (10⁴⁸) 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 chiffres, 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 10⁶⁴ grains de sable... Carl Sagan, quant a lui, a estimé le nombre d'atomes dans l'Univers a 10⁸⁰.

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, 10¹⁰⁰ (Utilisé pour parlé 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 (10¹²⁰), c'est à dire, le nombre possible de parties d'échec !

Et après ? Et bien, c'est à ce moment là qu'il faut citer l'Asaṃkhyeya, qui vaut environ 10¹⁴⁰, 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"...

Et après ? Tout ça, finalement, ça reste des simples puissances de 10, on peut facilement les écrire sur une feuille de papier...
On peut toujours trouver des nombres plus grand, qui deviennent même impossible à écrire ! Dans la foulée du gogol fut inventé le gogolplex, égal à 10^{un gogol}. (D'où le nom du siège social de google, le googlplex). D'autres mathématiciens ont prolongé le concept, un disant qu'un N-plex valait 10^N, et donc, le gogolplexplex vaut 10^{un 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 :

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

On a, par exemple,
ou   , nombre 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 :

On a, par exemple,

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

Et c'est là qu'il faut parler du nombre de Graham, qui est 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 :
u₁ = 4
u₂ =      (Avec 4 flèches)
u₃ =      (Avec flèches)
Et ainsi de suite jusqu'à u₆₄, le nombre de Graham, qui aura u₆₃ 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 !
Cette notation (utilisant la récursivité) consiste en une suite d'entiers séparés par des flèches (Par exemple, ).
Pour une chaine de longueur 1, on a p=p.
Pour une chaine de longueur 2, on a
Pour une chaine de longueur 3, il faut utiliser les flèches de Knuth dans la définition :

Pour une chaine de longueur supérieur, la définition rigoureuse devient nécessaire :

(Avec p copies de X, p-1 copies de q et p-1 paires de parenthèses... Lisez plutôt ça pour comprendre)

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

Mais le nombre de Graham reste ridiculement petit par rapport au nombre cité un peu plus haut...

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