Choux romanesco, Vache qui rit et intégrales curvilignes

23 février 2014

[#] Cravate club

L'info a largement été relayée dans les médias, il existerait 177 147 façons de nouer une cravate, et c'est une équipe de mathématiciens et d'informaticiens suédoise qui vient de le publier. Cette étude fait suite à une autre étude qui n'avait compté *que* 85 nouages de cravates différents. 

Mais concrètement, comment ont-ils compté tout ces nœuds de cravate ? Et quel est le rapport entre le film Matrix et cette histoire de cravates ? Détaillons un peu leur méthode.

Les 85 nœuds de Fink et Mao
Thomas Fink et Young Mao, deux physiciens anglais, sont les premiers à s'être formellement penché sur l'épineux problème du nœud de cravate en 1999. 

Pour aborder le problème, pensons cravate. Pour avoir une belle cravate, selon Fink et Mao :
- c'est la partie large de la cravate que l'on manipule
- on commence en plaçant cette partie large du côté gauche du corps (au-dessus ou en dessous de la partie fine, selon le nœud)
- on la passe alternativement au dessus et au-dessous du nœud.
- on termine en passant ce bout à l'intérieur du nœud, pour le "fermer".

La plus simple des variantes est le nœud "quatre en main", qui s'élabore en 4(+1) étapes, de la façon suivante :

Quatre mouvements pour un quatre en main

- on commence en plaçant la partie large de la cravate au-dessus et à gauche de l'autre partie (Li)
- on passe la partie large en-dessous et à droite de l'autre partie (Ro)
- on passe la partie large au-dessus et à gauche de l'autre partie (Li)
- on passe la partie large en-dessous du nœud et on la fait sortir par le col (Co)
- on passe la partie large dans le nœud de la cravate (U)

Les opérations que l'on peut finalement faire, c'est passer la partie large en-dessous (noté o) et au-dessus (noté i) de l'autre partie ; on peut, selon les situations, faire ressortir ce bout du côté droit de la cravate (R), gauche (L) ou au niveau du col (C). La dernière opération faisable, c'est celle qui consiste à passer la partie large dans le nœud de la cravate (et qui n'interviendra qu'une seule fois, à la fin) : la fermeture, notée U.

Bref, il y a 7 opérations possibles : Ro Ri Lo Li Co Ci et U. Un nœud de cravate sera alors complètement défini par une suite de ces opérations, en respectant tout de même certaines règles :

  • Règle 1 : on commence par Lo ou Li (commencer par Ro ou Ri entrainerait des nœuds miroirs, oublions-les).
  • Règle 2 : on ne peut pas faire successivement deux opérations R, L ou C identiques
  • Règle 3 : les opérations o et i doivent être alternées.
  • Règle 4 : la fermeture U n'intervient qu'à la fin, et seulement après les opérations Ro Li Co ou Lo Ri Co (car la cravate doit venir par le dessous du nœud, en passant par le côté col)

Ainsi, la succession de mouvements Lo Ri Lo Ri Co Li Ro Li Co U est tout à fait convenable (et il s'agit du nœud Grandchester, le #44 de la liste de Fink, qui requiert 9 mouvements). 

En traduisant les conditions par un graphe, on peut voir qu'une succession de mouvements qui donne un beau nœud de cravate correspond à un chemin sur le graphe ci-dessous, qui commence à D et se termine en U.

Cravate_simple

On peut alors voir qu'il y a un seul nœud faisable en 3 mouvements (Lo Ri Co U, le nœud oriental), un nœud en 4 mouvements (Li Ro Li Co U, le nœud quatre en main présenté plus haut) et 3 nœuds en 5 mouvements (les nœuds Kelvin, Nicky et Pratt). 
En notant an le nombre de nœuds faisables en n mouvements, on peut remarquer que l'on a an+2 = an+1 + 2 an. En se limitant à 8 mouvements au maximum, on dénombre alors 85 nœuds de cravate différents (le mouvement U final n'intervient pas dans le décompte).

85_noeuds

La notation WTU de Vejdemo-Johansson
Sauf qu'en 2003, toute la théorie a sauté, puisque le film Matrix Reloaded est sorti au cinéma. On ne retiendra qu'une seule chose du film : la cravate porté par Lambert Wilson, qui interprète Le Mérovingien, est nouée de façon à ce que la partie large de la cravate termine en-dessous de la partie fine ! Incroyable ! Luke Housego se dépêche de créer un tutoriel sur Internet, et baptise ce nœud le nœud Edeity.

Noeud_Merovingien
Le nœud Mérovingien, ou nœud Edeity, porté avec classe par Lambert Wilson
Séquence : Lo Ci Lo Ri Co Ri Lo Ci U

En 2008, c'est un nouveau nœud qui apparaît sur Youtube, le nœud Eldredge. Tous les tabous de la cravate sautent : ce n'est pas la partie large de la cravate qui est manipulée mais sa partie fine, celle-ci passe plusieurs fois dans le nœud et, ultime affront, elle termine sa course dans le col de son porteur !

Noeud_eldredge
Le nœud Eldredge
Séquence : Li Ro Ci Lo Ri Co Li Ro U Ci Lo Ci Ro U

Les règles imposées par Fink et Mao sont clairement trop restrictives, en particulier la règle n°4. Pour englober davantage de nœuds (dont le nœud Eldredge), disons plutôt que :

  • Règle 4' : le mouvement U peut intervenir n'importe quand, même après un mouvement L ou R, à condition qu'au moins deux mouvements au moins le précède. De plus, sous certaines conditions d'existence, on autorisera le mouvement UU (ou U²) consistant à rentrer la cravate dans deuxième couche du nœud, et, de manière générale, Uk qui consiste à rentrer la cravate dans la k-ième couche du nœud. Un tel mouvement est possible qu'après au moins 2k autres mouvements.

Il faut alors adapter les règles 2 et 3, en précisant qu'un mouvement U n'influence pas le fait que deux mouvements R, L ou C ne peuvent se succéder à l'identique, même chose pour o et i.

D'ailleurs, la notation o et i est complètement superflue. En effet, une fermeture U ne peut exister qu'après un mouvement o, où la cravate passe sous le nœud. Du coup, l'alternance o/i permet de retrouver les directions d'une séquence RLC de mouvements donnée.

Par exemple, la suite de mouvements du nœud Trinity est LCLRCRLCURLU. Le L qui précède le dernier U ne peut être qu'un mouvement de type Lo, et donc, en remontant, on peut retrouver que le mouvement initial est Li :

Noeud_Trinity
Le nœud Trinity (aucun rapport avec Matrix)
Li Co Li Ro Ci Ro Li Co U Ri Lo U

On peut donc se restreindre à seulement 4 symboles pour décrire le nouage de la cravate : L, R, C et U.
Enfin... Pas tout à fait, puisque l'on a pris pour hypothèse que l'on commence toujours à gauche (mouvement L). Il est donc inutile de le noter dans la liste. Comme deux mouvements L, R et C ne peuvent se succéder à l'identique, on peut se contenter de dire si le prochain mouvement est un mouvement dans le sens des aiguilles d'une montre (noté T - comme Turnwise) ou dans le sens inverse (noté W - comme widdershin).

  • T : tourner dans le sens des aiguilles d'une montre (sens indirect) : R -> L, L -> C ou C -> R.
  • W : tourner dans le sens inverse des aiguilles d'une montre (sens direct) : L -> R, R -> C ou C -> L.

Par exemple, la suite de mouvement WTWTWUTTU du nœud Floating Spiral débute, comme tous les nœuds, par L. Puisque le premier mouvement est de type W, la région suivante est R. On peut ainsi en déduire la séquence complète :

Noeud_Floating_Spiral
Nœud Floating Spiral
Li Ro Li Ro Li Ro U Li Co U

Les 177 147 nœuds de Vejdemo-Johansson
Il est temps de dénombrer les différents nœuds de cravate. Pour cela, l'équipe de Vejdemo-Johansson a remarqué que les nœuds de cravate de 1ere espèce (où la cravate ne peut passer que sous la couche la plus récente crée au dessus du nœud) obéissent toujours au schéma ⟨préfixe⟩ ⟨développement⟩ ⟨fermeture⟩, sachant que

  • le préfixe peut être T ou W (ou rien).
  • le développement est constitué d'une suite (pouvant être vide) de paires (TT, TW, WW ou WT) et de fermetures (TTU ou WWU)
  • la fermeture finale est obligatoire (TTU ou WWU).

Ainsi, WWU et TTU sont des nœuds possibles (correspondant respectivement à un nœud de cravate oriental, et à un nœud où la cravate est mise comme une écharpe autour du cou...). Le nœud T.WW.WW.WWU (Windsor) correspond lui aussi parfaitement à cette description.

Ce schéma peut alors se traduire par un graphe, où les nœuds de cravates valides correspondent à un chemin débutant et terminant sur la case centrale :

Graphe_cravates

Avec un peu de théorie des graphes, on peut remarquer que le nombre de nœuds de 1ere espèce de longueur n et ne comportant qu'une seule fois l'opération U est de 2n-1. En se limitant à au plus 11 mouvements (nécéssaires pour Eldredge), on compte un total de 2048 nœuds de référence fondamentalement différents, auquels s'ajoutent les variantes comptant plusieurs fois l'opération U.

On peut alors les répartir en trois classes, selon la position finale de la cravate (CU, LU ou RU), les nœuds classiques recensés par Fink et Mao sont alors ceux de la première classe, (où la différence entre le nombre de W et de T est de 2 modulo 3).

2046_noeuds
Répartition des 2046 nœuds de référence (Le U final ne rentre pas de le décompte des mouvements)

Mais ces 2046 nœuds et leurs variantes ne représentent qu'une petite portion des 177 147 différents nœuds de cravate recensés. Il faut en effet ajouter toutes leurs variantes de fermetures pour obtenir les nœuds de seconde espèce. Les conditions d'existence de ces variantes s'appuient sur des considérations sur le nombre de W et T précédant les différentes fermetures U. A titre d'exemple, TTWTUU est une séquence valide de 2nde espèce, même si elle n'obéit pas au schéma présenté plus haut.

Au final, les 2046 nœuds engendrent 177 147 nœuds de cravate, ce qui est prodigieusement... beaucoup. Ce que la théorie ne dit cependant pas, c'est le caractère esthétique de chacun de ces nœuds, point qui avait été abordé par Fink et Mao. Du coup, il est aujourd'hui impossible de savoir si nous sommes passé à côté d'un nouage de cravate inédit mêlant élégance et originalité. En attendant, vous pouvez toujours tenter de reproduire l'un des nœuds obtenu à partir du générateur !


Sources :
D. Hirsch, M. L. Patterson, A. Sandberg, M.Vejdemo-Johansson, More tie than we though (d'où provient le dernier graphe)
M.Vejdemo-Johansson, Random tie knots
T. Fink, Encyclopedia of tie knot - donne la liste des 85 nœuds de Fink et Mao
T. Fink, Y. Mao, Designing tie knots by random walks (d'où provient la première illustration)


08 février 2014

[#] Just another Huffman tree

La nétiquette, c'est un ensemble de règles à suivre pour être un gentleman des internets, une charte implicite que tout le monde se devrait de suivre. Par exemple, dans son point 2.1.1 relatif aux bonnes règles d'usage du courrier électronique, la nétiquette requiert :

« Soyez conscient de la longueur des messages que vous envoyez. Annexer de grands fichiers, tels que des documents en Postscript ou des programmes, peut rendre vos messages si grands qu'ils peuvent ne pas être transmis ou au moins consommer une part exagérée de ressources. Une bonne règle sera de ne pas envoyer de fichier dépassant les 50 Ko. Comme alternative, réfléchissez au transfert de fichier, ou à découper le fichier en morceaux plus petits et à les envoyer séparément. » netiquette.fr

Il faut d'autant plus faire attention que 50 ko, c'est très vite atteint !... Bon, la nétiquette date de 1995, un temps où les modems 56k chantaient de la dubstep.
Mais il faut se souvenir qu'un gentleman n'envoie pas de fichier trop lourd à ses amis. Non, il commencera par le compresser à l'aide d'un logiciel adéquat, en s'assurant que son ami sache comment décompresser ce fichier.

Mais d'ailleurs, comment ça marche, la compression de fichiers ? De nombreuses méthodes existent aujourd'hui, mais la première d'entre toutes, c'est quand même la méthode de Huffman, qui n'a aujourd'hui rien perdu de sa superbe. En ce dimanche, parlons de Huffman et de ses arbres.

Saut ASCII
Je souhaite stocker, dans la mémoire de mon ordinateur, la phrase suivante « je ne suis qu'une phrase d'exemple mais j'ai quand même un cœur ». Et comme je suis exigent, je veux le faire de la façon la plus économique possible. Le gros problème, c'est que la seule chose qu'il est réellement possible de stocker dans la mémoire d'un ordinateur, ce sont des petits bouts d'information, des 0 et des 1 (les bits). Ma phrase d'exemple, elle, contient quand même 21 caractères différents, ce qui est sensiblement plus grand que 2.

Du coup, la première idée géniale est de regrouper les bits par groupe de 8 (les octets). Avec 8 bits, on peut fabriquer tout de même 256 nombres. Il suffit d'associer à chaque caractère un des 256 octets possibles, et le tour est joué.

On va dire que le « j » est codé par 01101010, que le « e » est codé par 01100101 ou que l'astérique est codé par 00101010 !

C'est ce que se sont dit dans les années 60 les créateurs de la convention de codage ASCII, histoire d'uniformiser tout ce qui prééxistait. Au final, le codage ASCII permet de coder 127 caractères, dont 95 caractères effectivement affichables, chacun codable sur 7 bits seulement, ce qui est bien suffisant pour les américains de l'époque. On se garde de côté le huitième bit de l'octet, il pourra nous servir à l'occasion.

La phrase « je ne suis qu'une phrase d'exemple mais j'ai quand même un cœur » se codera en ASCII (presque) par 

01101010 01100101 00100000 01101110 01100101 00100000 01110011 01110101 01101001 01110011 00100000 01110001 01110101 00100111 01110101 01101110 01100101 00100000 01110000 01101000 01110010 01100001 01110011 01100101 00100000 01100100 00100111 01100101 01111000 01100101 01101101 01110000 01101100 01100101 00100000 01101101 01100001 01101001 01110011 00100000 01101010 00100111 01100001 01101001 00100000 01110001 01110101 01100001 01101110 01100100 00100000 01101101 00111111 01101101 01100101 00100000 01110101 01101110 00100000 01100011 00111111 01110101 01110010

L'ASCII est cependant incapable de coder des caractères farfelus comme « ê » ou « œ ». Tant pis, ils auront été codé par 00111111 (« ? »).

Au final, avec ce codage, on s'en sort avec un texte codé sur 63 octets, soit 504 bits (ou 441 bits si on enlève tous les '0' inutiles au début de chaque octet). C'est quand même beaucoup. En plus, on s'est fait flouer, puisqu'on a perdu deux caractères essentiels à l'intégrité de la phrase.

Ce qui serait parfait, c'est de compresser cette série de bits, mais sans perdre aucune information sur la phrase.

De l'inégalité patente entre les caractères
La norme ASCII est profondément égalitariste : que l'on soit un caractère cool comme le « », une caractère fréquent comme le « e » et l'espace, ou un caractère inutile comme le «|», on est logé à la même enseigne, sur 8 bits. Une idée géniale, ça serait de coder sur peu de bits les caractères très utilisés, et sur plus de bits les caractères superflus.

C'est en fait le principe du code Morse : une lettre fréquente est codée par un signal rapide (le « e » est codé par « · »), alors qu'une lettre rare est codée par un signal plus long (« y » est codé par « — · — —») .

Faisons ça, toujours sur la même phrase d'exemple. L'espace et le « e » sont fréquent, on les code sur un seul bit ; le « x »  et le « c » sont rares, on les code sur 4 bits :

Code_pas_pratique

Ainsi codée, la phrase sera :

01110011 01000001 10010000 01000011 01010000 11011101 01110101 00011000 10101011 00001100 11000110 10110010 10000110 11110000 00100001 00001000 11010000 110

On s'en sort maintenant avec seulement 139 bits ! Le progrès est énorme ! Oui, mais... Comment on va décoder ça ? Les 4 premiers bits sont 0111, qui peuvent se traduire par « je », mais aussi par « na » ou par « _eee ». Impossible de trancher, on a fait tout ça pour rien.
Pour ne pas avoir ce soucis d'ambiguïté, il nous faut un "code préfixe" ; autrement dit, un système de codage binaire où le code d'un caractère ne doit pas pouvoir être prolongé de façon à former le code d'un autre caractère. Ainsi, si l'on décide que l'espace est codé par 0, le codage d'aucun autre caractère ne doit pouvoir commencer par zéro.

C'est sur ce principe que se base la norme UTF-8 (la norme de codage de caractère la plus utilisée) : un caractère sera codé sur un ou plusieurs octets. Si le premier octet commence par 0, c'est qu'il est codé sur un seul octet selon la norme ASCII, dans le cas contraire, le caractère est codé sur plusieurs octets, et il faut se référer à la base de donnée idoine.

Compression de Huffman
Il me faut donc un code préfixe pour coder « je ne suis qu'une phrase d'exemple mais j'ai quand même un cœur » en utilisant le minimum de bits. La construction d'un tel codage, on la doit à David Albert Huffman, qui a mis au point l'algorithme qui suit lors de sa thèse de doctorat en 1952.

Pour cela, on commence par trier par ordre croissant de présence les caractères qui nous intéressent :

etape0étape 0

Puis, on prend les deux arbres de plus petit poids (ici, « l » et « œ », chacun de poids 1), puis on les réunis de façon à former un arbre binaire, qui sera alors de poids 1+1 = 2. L'arbre ainsi formé est alors remis à sa place, selon l'ordre croissant des poids.

etape1étape 1

On poursuit le processus, en réunissant à chaque étape les deux caractères (ou arbres précédemment formés) de plus petit poids sous une même bannière, dont le poids est la somme des deux poids :

etape2
étape 2

etape3
étape 3

(...)

etape15
étape 12

Finalement, après 19 étapes, on obtient un arbre complet, où les feuilles sont les caractères que l'on cherchait à coder. Le code, il est tout trouvé : en partant du haut de l'arbre, on codera '0' si l'on descend à gauche, et '1' sinon.

♫ And all that I can see is just a yellow Huffman tree ♫

L'arbre codant / décodant

Ainsi, 001 codera « u » ou 01101 codera « j ». Par construction de l'arbre, les caractères les plus fréquents seront au plus prêt de la racine et demanderont une chaîne courte de bits, tandis que les caractères les plus rares seront codés par une chaîne plus longue.

Finalement, ma phrase initiale peut être codée sans aucune ambiguité (grâce à l'arbre) sur 249 bits (32 octets) par 

01101110 11110111 10111101 00010001 10101110 11000010 00000110 11110111 01111010 10101110 10011010 11011101 00100001 10010100 11010000 11110100 00110111 10001001 00011010 11101101 00001001 00011110 11000011 00110110 10011111 00001011 11000110 11100110 11111010 11001000 10010111 0

Cela représente tout de même un gain de 50% par rapport au codage ASCII. Il est d'ailleurs impossible de le coder sur moins de bit avec un code préfixe. merci Huffman !

Si je dois déchiffrer cette séquence de bits, il suffit de la lire en suivant l'arbre. Les premiers caractères étant 01101, ils ne peuvent que coder le « j ».

Bon, il a quand même un hic : si je compresse ma phrase et que je la garde telle quelle, j'aurai du mal à retrouver la phrase initiale si je ne garde pas l'arbre de décodage quelque part. L'arbre doit être rattaché au fichier pour qu'il puisse être décompressé, et cet arbre a un poids : au moins 40 octets !
Finalement, mon message compressé pèsera environ 52 octets, ce qui ne représente plus vraiment un énorme gain par rapport au poids du message initial (63 octets). On peut éviter ce problème en utilisant un arbre générique, spécifique à la langue du texte que l'on code (voir commentaires de l'aticle). Il n'y a alors plus besoin de transmettre l'arbre, mais la compression sera forcément moins importante.
Cependant, le surplus représenté par le codage de l'arbre devient négligeable dès que les fichiers deviennent imposant (à partir de quelques ko).

L'algorithme de Huffman est utilisé par la plupart des logiciel de compression (WinZip, 7-Zip, WinRar...), mais il est le plus souvent couplé à un algorithme de compression de type LZ, qui commence par chercher et éliminer les redondances dans le fichier que l'on cherche à compresser.

Je terminerai par un fait tout à fait intéressant qui n'a rien à voir avec le sujet de l'article. David Albert Huffman ne s'est pas intéressé qu'à la compression de données, il a aussi découvert des méthodes d'origami tout à fait inédites en marge de ses travaux de topologie. Le résultat est particulièrement élégant :

Un bel origami
Pavage origami, mis au point par Huffman.
Il est cependant déconseillé de le compresser.


Sources :
D.A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, l'article original de Huffman
E. Davis & friends, Reconstructing David Huffman's Origami Tessellations, d'où provient l'illustration de l'origami

Posté par El Jj à 10:00 - Commentaires [7]
Tags : , ,

19 janvier 2014

[#] 24 jours après le Big Bang

Devinette ! Complétez la suite logique suivante :

3
13
1113
3113
132113
...

Ok, tout le monde la connaît, celle-là. Le terme qui suit, c'est 1113122113, car il s'agit de la suite "look and say" (abrégée LS) inventée en 1987 par Conway : chaque terme de la suite s'obtient en lisant les chiffres du terme précédent. Ainsi, la ligne 3113 peut se lire "un '3' puis deux '1' puis un '3'", ce qui donne 132113.

On pourrait s'arrêter au simple constat "ok, elle est marrante ta suite logique, mais t'es gentil, je regarde le match, là". Mais je me dois d'en dire plus, puisque cette suite possède de nombreuses propriétés. La plus merveilleuse d'entre elle a été intitulée "théorème cosmologique" et, résumé par son auteur, nous apprend que "24 jours après le Big Bang, l'ensemble des éléments exotiques ont disparu" ! Il faut dire que derrière cette suite se cache John Conway, qui baptise toujours ses découvertes par des noms improbables, comme le jeu de la vie, les nombres surréels ou le jeu "Sprouts"...
J'avais déjà écrit un article sur ce sujet en 2007, il est temps de le réactualiser.

Évidemment, on peut changer de terme initial pour former d'autres suites LS, comme

3333
43
1413
11141113
...

Il y a également le cas particulier de la suite 22, qui donne :

22
22
22
22
...

Théorème du jour 1 & théorème du jour 2
Avant que vous me trouviez des contre-exemples, mettons nous d'accord sur une chose : le chiffre 0 n'existe pas, tout comme les nombres supérieurs à 9. Si jamais ils venaient à exister, on les écrira quand même avec un seul chiffre. Par exemple, la chaîne qui suivra 1111111111 n'est pas 101 mais ⁂1 (où ⁂ est le chiffre que je viens d'inventer pour désigner le nombre 10) :

1111111111
⁂1
1⁂11
111⁂21
311⁂1211
...

Quelques définitions : on appellera "graine" la chaîne initiale d'une suite LS. Tous les termes qui suivent sont ses descendants : on dira que le premier est âgé de 1 jour, le suivant de 2 jours, etc.
La graine d'une suite LS peut être aussi compliquée que l'on veut, le terme suivant répondra quand même à quelques propriétés.

Du coup, on peut énoncer le théorème du jour 1 : une chaîne âgée de 1 jour...

  • ne peut pas débuter par yxzx (où x, y et z désignent trois chiffres différents - ou pas), ni contenir une telle chaîne dans une position paire.
  • ne peut pas contenir le même chiffre répété 4 fois ou plus (conséquence de la propriété précédente)
  • ne peut pas contenir la chaîne xxxyyy

En conséquence du théorème du jour 1, on a le théorème du jour 2 : une chaîne âgée de 2 jours...

  • ne peut pas faire naître un nouveau 4 (ou tout autre chiffre supérieur)
  • ne peut pas contenir la chaîne 3x3

Il n'est fait aucune mention d'un théorème du jour 3, mais je reviendrai plus tard sur celui du jour 24.

Théorème de séparation
Le point central de la théorie des suites LS est l'idée qu'elles puissent se scinder, dans le sens où il arrive qu'à partir d'une certain étape, la partie gauche de la chaîne n'interfère plus avec la partie droite. Prenons par exemple la suite débutant par 42 :

4·2
14·12
1114·1112
3114·3112
...

D'après le théorème du jour 2, aucun nouveau '4' ne peut apparaître, en particulier à droite du chiffre '4' déjà présent. De ce fait, il ne peut y avoir que un seul '4' à une étape donnée, ce qui le transformera inexorablement en '14' à l'étape suivante, n'interférant pas sur les chiffres qui suivent. On notera par "·" cette scission. 

Il existe dix cas (et pas plus) dans lesquels une chaîne se scinde (c'est le théorème de séparation). Par exemple, une chaîne contenant ...XY... (avec X≥4 et Y≤3) se scindera sous la forme ...X·Y..., ce qui est le cas dans l'exemple précédent . De la même façon, une chaîne contenant ...2111... se scindera en ...2·111... (voir [1] si vous voulez la liste en détail).

Évidemment, les sous-chaînes obtenues peuvent elles aussi se scinder, donnant au fil des étapes de nombreuses sous-chaînes indépendantes.

Il existe alors des sous-chaînes qui ne peuvent pas se scinder : on les appelle les "éléments" (ou "atomes"). Parmi ces éléments, certains finissent inexorablement par apparaître, quelle que soit la graine de la suite (sauf si c'est 22). Ces éléments particuliers (les "éléments communs") sont au nombre de 92, si bien que Conway les a nommé à partir des 92 éléments chimiques existant naturellement, allant de l'hydrogène H1 = 22 jusqu'à l'uranium U92 = 3, en passant par exemple par le carbone C6 = 3113112211322112211213322112 (tous les éléments communs ne sont pas aussi simples que H1 ou U92). Puisque ces éléments ont la fâcheuse tendance à se désintégrer les uns en les autres, Conway les a baptisé "éléments audioactifs".

On ajoute à cette liste les deux éléments transuraniens Np93 et Nu94, les deux seuls éléments comprenant un chiffre supérieur à 3. De ce fait, ces deux éléments existent sous une infinité de versions (leurs "isotopes"), autant que de chiffre supérieur à 4 possibles.

Enfin, il existe une infinité d'éléments 'exotiques', comme 1, 2 ou 4443333444, qui ne peuvent pas apparaître en tant qu'atome après plusieurs étapes.

Du coup, on peut ranger ces 94 éléments communs et transuraniens dans leur tableau périodique :

Tableau périodique des éléments audioactifs

Le tableau périodique des 94 éléments audioactifs de Conway (click doit / ouvrir dans un nouvel onglet, pour voir en encore plus grand !)

A titre d'exemple, l'élément Sm62 = 311332 devient après un jour 13212312, qui se scinde sous la forme 132·12·312 = Pm61·Ca20.Zn30. : Du coup, on peut réécrire la suite de graine 311332 sous la forme suivante :

Sm62
Pm61·Ca20.Zn30
Nd60·K19·Cu29
Pr59·Ar18·Ni28
Ce58·Cl17·Zn30·Co27
...

Ainsi, si la graine de la suite est un élément commun ou transuranien, tous ses descendants seront uniquement composés d'éléments communs et transuraniens. D'ailleurs, si la graine est composée d'éléments communs et/ou transuraniens (et n'est pas H1 = 22), il arrivera tôt ou tard un descendant composé d'au moins une fois les 92 éléments (plus éventuellement des éléments transuraniens) !

L'ordre des éléments a été choisi de façon à ce qu'un élément n soit le descendant direct de l'élément n+1 . Ainsi, en partant d'une graine U92, on aura après 91 génération l'élément H1, au milieu de beaucoup d'autres. Il en fait 6 autres façons de ranger les 92 éléments en suivant cette règle, le tableau ci-dessus correspond à la liste originale dressée par Conway (voir [2] pour les détails).

Le théorème cosmologique
On arrive au théorème le plus important de la théorie des suites LS, le théorème cosmologique :

Quelle que soit la graine choisie, il arrivera une étape où les descendants seront composés uniquement d'éléments communs et transuraniques. Ceci arrivera en au plus 24 étapes !

Ce théorème prouve en particulier qu'un élément exotique ne pourra pas le rester éternellement. Par exemple, si on choisit la graine 1 (élément exotique), on fini par tomber (après 7 étapes) sur le composé Hf72·Sn50 :

1
11
21
1211
111221
312211
13112221
11132·13211 = Hf72·Sn50
311312·11131221 = Lu71·In49
...

La borne des 24 étapes est optimale, puisqu'il existe un élément exotique demandant les 24 jours pour se scinder en élément commun. Cet élément est 22333222114, découvert et baptisé Mathusalum par Mike Guy, collègue de Conway.

La démonstration de ce théorème est particulièrement difficile, si bien que Conway nous a fait le coup de la démonstration perdue. Du coup, la preuve complète la plus récente du théorème cosmologique date seulement de 2003, et, à l'image du théorème des quatre couleurs, comporte une grande partie de calcul informatique.

La constante de Conway
Entre deux termes consécutifs d'une suite LS (quelle que soit sa graine), le nombre de chiffres est en moyenne multiplié par λ = 1.303678... Autrement dit, en notant un le nombre de termes d'une suite LS, on a :

limite_suite_LS

Ce nombre n'est autre que l'unique solution réelle de l'équation

x71 - x69 - 2x68 - x67 + 2x66 + 2x65 + x64 - x63 - x62 - x61 - x60 - x59 +
2x58 + 5x57 + 3x56 - 2x55 - 10x54 - 3x53 - 2x52 + 6x51 + 6x50 + x49 + 9x48 - 3x47 +
- 7x46 - 8x45 - 8x44 + 10x43 + 6x42 + 8x41 - 5x40 - 12x39 + 7x38 - 7x37 + 7x36 + x35 +
- 3x34 + 10x33 + x32 - 6x31 - 2x30 - 10x29 - 3x28 + 2x27 + 9x26 - 3x25 + 14x24 - 8x23 +
- 7x21 + 9x20 + 3x19 - 4x18 - 10x17 - 7x16 + 12x15 + 7x14 + 2x13 - 12x12 - 4x11 +  
- 2x10 + 5x9 + x7 - 7x6 + 7x5 - 4x4 + 12x3 - 6x2 + 3x - 6 = 0

Il s'agit donc de la racine d'un polynôme de degré 71 ! (D'autant que le polynôme est irréductible, ce qui fait de λ l'un des nombres algébriques ayant le plus haut degré de toute la littérature mathématique)

Pour comprendre d'où sort ce polynôme, regardons plutôt la suite suivante, où chaque terme est obtenu à partir du précédent en transformant a en ab, et en transformant b en a :

b
a
ab
aba
abaab
abaababa
...

On peut remarquer que le nombre de caractères des termes de cette suite correspondent à (Fn), la suite de Fibonacci (1, 1, 2, 3, 5, 8, ...), où le rapport des termes consécutifs converge vers le nombre d'or φ :

limite_suite_Fibo

Une façon de démontrer ceci est de remarquer que le nombre an et bn de a et de b à la n-ième ligne de la suite vérifie :

matrice_Fibo

Dans une telle situation, on peut montrer (avec ce qu'il faut d'algèbre linéaire) que les rapports Fn+1/Fn convergent vers la plus grande valeur propre (en module) de la matrice (et indépendamment du terme initial), qui n'est autre φ. Autrement dit, ce rapport converge vers la plus grande racine du polynôme caractéristique de la matrice, qui est X² - X - 1.

Pour les suites LS, l'idée est la même, sauf que la matrice est un tantinet plus compliquée, puisqu'elle est de taille 92×92 ; mais sa plus grande valeur propre est effectivement λ. Voir [3] pour davantage de détails sur le calcul de la matrice et de son polynôme caractéristique.

 

Bref, la prochaine fois qu'un petit malin vous met au défi de compléter la suite de Conway, n'hésitez pas à lui dire que derrière cette bête devinette se cache un bestiaire chimico-mathématique étonnant et une complexité hallucinante !


Sources 
[1] Oscar Martin, Look-and-Say Biochemistry: Exponential RNA and Multistranded DNA, dont l'introduction est très complète
[2] Henry Bottomley, Seven complete sequences for the Conway Look and Say elements
[3] Nathaniel Johnston, A Derivation of Conway’s Degree-71 “Look-and-Say” Polynomial
[4] John Conway, Weird and wonderful chemistry of audioactive decay

12 janvier 2014

[#] Ordre et désordre

Un dernier verre, peut-être ? Venez, ma mie, je vous invite pour un dernier chocolat chaud. Installez-vous sur le canapé, je reviens dans un instant. Ne faites pas attention à cette pile de papiers sur la table et faites comme si les affaires qui traînent par terre, c'est normal. Ignorez également la vaisselle entassée dans l'évier, toute comme cette casserole dans lequel il reste un fond de... euh... ce que j'ai mangé la semaine dernière. Comment ça, cet appartement est mal rangé ? Absolument pas ! D'ailleurs, le désordre total ne peut pas exister ! Ce n'est pas moi qui dit ça, c'est la théorie de Ramsey... Et n'allez pas croire que je me cache derrière les maths... Eh, revenez, je n'ai pas terminé le chocolat chaud !...

La théorie de Ramsey est la suivante : dans une structure contenant beaucoup d'éléments, on finit toujours par retrouver une propriété donnée. La question qui se pose alors, c'est la valeur numérique de ce "beaucoup", qui, pour certain exemple, peut être démesurément grand. On résume plus souvent la théorie de Ramsey par "le désordre total n'existe pas".

Le principe de base de la théorie de Ramsey est le principe des pigeons (alias principe des tiroirs de Dirichlet). Par exemple, à partir de combien de personnes peut-on être sûr d'en trouver deux possédant le même signe du zodiaque ? Puisqu'avec 12 personnes, on peut avoir le zodiaque au complet, la propriété "au moins deux personnes possèdent le même signe astrologique" devient vraie à partir de 13.

Théorème de Ramsey
Le problème central en théorie de Ramsey (et, de façon plus générale, en combinatoire) est celui du théorème de Ramsey. On présente souvent ce théorème par le célèbre problème des six amis.

Vous invitez un groupe d'amis pour une occasion quelconque (soirée foot à la télé, soirée puzzle ...). Parmi ces invités, certains se sont déjà rencontrés auparavent, d'autres se rencontrent pour la première fois. Mais à partir de combien d'invités peut-on être sûr qu'il y ait
- soit trois invités qui se connaissent deux à deux
- soit trois invités qui ne se connaissent pas deux à deux.
Ce nombre, on le notera R(3).

K5

Graphe de la situation.
Deux invités sont reliés par une arête bleue si ils se connaissent, en rouge sinon.
Pour 5 invités, il n'existe pas forcément de trio qui se connaissent ou qui ne se connaissent pas
Ce contre-exemple prouve R(3) ≥ 6.

La réponse est 6, et je peux le prouver ! On suppose que 6 invités sont là, et que David en fait partie (il y a toujours un David dans les invités). Parmi les 5 autres invités, soit il y en a 3 qui le connaissent, soit 3 ne le connaissent pas (par le principe des tiroirs). Sans pertes de généralité, on peut supposer que ces trois invités connaissent David, et qu'ils s'appellent respectivement Karen, Natalie et Billy. Deux possibilités alors : soit ces trois invités ne se connaissent pas (et on a notre trio gagnant), soit il y en a au moins deux qui se connaissent, et ils forment avec David le trio gagnant. CQFD.

Ce problème se reformule dans la théorie des graphes : si les arêtes d'un graphe complet d'ordre 6 sont colorés à l'aide deux couleurs, alors il existe un triangle unicolore.

Friends_strangers_graph

On peut lister l'ensemble des graphes bicolores complets à 6 noeuds.
Ils admettent tous un sous-graphe complet unicolore.

Mais le problème se généralise : combien faut-il réunir d'invités pour être sûr que, parmi eux, il existe un groupe de k invités se connaissant mutuellement, ou ne se connaissant pas du tout ? Ce que nous dit le théorème de Ramsey, c'est que ce nombre existe toujours. Ce que ne nous dit pas le théorème, c'est sa valeur exacte.

Pour k = 4, on peut montrer R(4) = 18, en raisonnant de façon similaire (en trouvant un graphe contre-exemple à 17 sommets, puis en montrant que cela marche bien dès que n=18).
Pour k = 5, les choses se compliquent. Tout ce que l'on sait dire aujourd'hui, c'est que R(5) est strictement compris entre 42 et 50.
Pour k = 6, cela empire : on ne sait pour l'instant dire qu'une seule chose, c'est que le nombre R(6) est quelque part entre 102 et 165...

A ce sujet, Erdõs a imaginé ce qu'il se passerait si une armée d'aliens belliqueux nous déclarait la guerre, à moins qu'on leur fournisse la valeur de R(5). Dans un tel cas, on pourrait mettre à profit l'ensemble des ordinateurs et des mathématiciens de la planète pour calculer ce nombre. Cependant, si ils nous réclamaient R(6), les ordinateurs et mathématiciens disponibles seraient plutôt réquisitionnés pour mettre au point une stratégie permettant de mettre hors d'état de nuire ces extraterrestres...

Le problème de la fin heureuse
Dès qu'un problème cherche le nombre minimal d'objets à réunir pour qu'une propriété soit vérifiée, on peut l'inclure dans la théorie de Ramsey. Un autre problème représentatif est le problème du Happy ending (parce que, à la fin, ils se marièrent et eurent beaucoup1 d'enfants). Ce théorème nous annonce que :

Etant donné (au moins) 5 points du plan (jamais alignés ni confondus),
il y existe toujours quatre points formant les sommets d'un quadrilatère convexe.

Un quadrilatère (ou n'importe quelle figure géométrique) est convexe quand il ne possède aucun creux. Par exemple, le quadrilatère rouge en dessous n'est pas convexe.

HappyEnding

A gauche : un exemple où 4 points ne forment pas un quadrilatère convexe.
A droite, plusieurs dispositions de 5 points. Dans tous les cas, il existe toujours (au moins) un quadrilatère convexe. L'enveloppe convexe des groupes de 5 points est représentée en jaune.

Pour démontrer ce fait, il suffit d'envisager tous les cas possibles, selon l'enveloppe convexe des 5 points (l'enveloppe convexe, c'est le polygone que l'on obtient quand on place un élastique autour de l'ensemble de ses points. Par essence, une enveloppe convexe est convexe).
- si l'enveloppe convexe est un pentagone, il suffit d'en retirer un point pour retrouver le quadrilatère tant cherché.
- si l'enveloppe convexe est un quadrilatère, inutile d'aller chercher plus loin
- si c'est un triangle, alors les deux points à l'intérieur forment un quadrilatère convexe avec au moins l'un des côté (avec le côté qui ne coupe pas la droite formée par les points intérieurs). CQFD.

Cette histoire de quadrilatère convexe est le problème original du happy ending, découvert et démontré en 1933 par Esther Klein. Elle demande alors a ses collègues si l'un d'eux a une idée pour généraliser la question : étant donné un grand nombre de points, y existe-t-il toujours un pentagone/hexagone/n-gone convexe. George Szekeres revient une semaine plus tard avec sa réponse : oui !

Théorème de Erdös-Szekeres : Étant donné un ensemble suffisamment grand de points du plan (jamais alignés ni confondus), il y existe toujours N points formant les sommets d'un polygone convexe.

HappyEnding5
9 points suffisent pour y trouver un pentagone convexe

Si Erdös a accolé son nom a celui de Szekeres, c'est qu'il a pas mal étudié la question lui aussi. C'est d'ailleurs Erdos qui a surnommé ce théorème "happy ending" en 1937, puisque c'est celui-ci qui a mené Esther Klein et George Szekeres à se marier en 1937 !

On peut être un peu plus précis sur la valeur de "suffisamment grand" :
- si on cherche les triangles convexes, 3 points suffisent (puisqu'on les suppose ni alignés, ni confondus)
- si on cherche les quadrilatères convexes, 5 points suffisent.
- si on cherche les pentagones convexes, il faut au moins 9 points.
- si on cherche des hexagones convexes, c'est 17 points qu'il est suffisant d'avoir. Ceci n'a été démontré qu'en 2006 (Szekeres, Peters)
- pour les polygones plus grand, rien n'est encore sûr. On sait qu'il faut au moins 1+2N-2 points pour y trouver à coup sûr un N-gone convexe, on conjecture que cette borne est optimale.

Le problème du polygone vide
Le théorème de Erdös-Szekeres serait encore plus élégant si, en plus d'être convexe, le polygone pouvait être vide (aucun point à l'intérieur). Pour 5 points, pour peu que l'on modifie légèrement la démonstration, on peut montrer qu'il existe toujours un quadrilatère convexe vide. Pour 9 points, il n'existe pas forcément de pentagone convexe vide, mais il suffit de 10 points pour rendre cette assertion vraie. Mais existe-t-il toujours un hexagone convexe vide dans un ensemble assez grand de points ?

La réponse est oui, mais il a fallu attendre 2007 pour en être sûr. Le nombre exact de points suffisant n'est pas connu exactement, mais on sait quand même qu'avec 463 points, on est sûr d'avoir un hexagone convexe vide.

HexagoneCache

463 points au hasard. Il y existe forcément (au moins) un hexagone convexe vide
Avec moins de 463 points, rien n'est sûr...

Je prèfère ne pas trop évoquer le cas de l'heptagone convexe vide, puisqu'il contredit la théorie de Ramsey : même avec un nombre arbitrairement grand de points, on ne peut pas être sûr d'y trouver d'heptagone convexe vide...

Le nombre de Graham
Un dernière exemple de problème de la théorie de Ramsey, le problème de Graham :

Considérons un hypercube de dimension n où chaque arête et diagonale est coloré en rouge ou en bleu.
Y existe-t-il toujours un plan unicolore défini par 4 sommets coplanaires ?
Si non, à partir de quelle dimension n est-ce toujours vraie ?

Exemple, avec n = 3. On a donc un cube (on ne peut plus classique, en 3D), on colore en rouge/bleu ses 28 arêtes et diagonales. Parfois, on peut y trouver un plan unicolore :

GrahamCube

Et parfois, non :

GrahamCube2
Impossible de trouver un plan unicolore passant par 4 points dans ce cube

A partir de quelle dimension peut-on être sûr d'en trouver ? Les spécialistes conjecturent qu'il suffit de chercher dans un hypercube de dimension 13. Mais entre ce que l'on conjecture et ce qu'on l'on arrive à démontrer il y a un gouffre, ce problème en est le plus gros exemple. Ce que Graham est parvenu à démontrer, c'est que la dimension recherchée est un nombre grand. Très grand. Ce nombre est tellement grand que je ne peux l'écrire sur ce blog. Je ne peux même pas écrire le nombre de chiffres qui le compose, pas plus que le nombre de chiffres qui compose son nombre de chiffresCe nombre est tellement grand que si je l'utilise dans une blague de "ta mère", on pourrait penser que j'exagère un peu. A l'heure d'aujourd'hui, cette borne supérieure reste la pire qui existe de toute l'histoire des démonstrations mathématiques. Et pourtant, grâce à cette démonstration, on peut quand même dire qu'il est vrai que la propriété de Graham est vraie en grandes dimensions...

Ce nombre N*, c'est le 64e terme de la suite
u1 = 4
u2 = 3 ↑ 3
u3 = 3  3 3
... où n désigne la flèche (itérée n fois) de Knuth (voir ce vieil article)

Certaines personnes ont du mal à penser en dimension 3, la plupart des gens sont incapable de penser en dimension 4. Il ne me semble pas que quiconque sur Terre soit capable de réfléchir en dimension N*. 


Sources :
Une démonstration du calcul de R(4)
, et plein d'autres articles intéressants sur cut-the-knot
Colorie-moi le ciel, qui parle aussi du théorème de Ramsey infini
Le désordre total n'existe pas..., Pour la Science N°376 - fevrier 2009

Images :
Friends strangers graph


1 : Encore une fois, la théorie de Ramsey ne nous donne pas la valeur exacte de ce "beaucoup".

05 janvier 2014

[#] 2013+1 (Cette nouvelle année est-elle intéressante ? Episode 05)

Nous venons de changer d'année, et, comme en chaque nouvelle année, je ne peux pas résister à l'envie de passer en revue les différentes propriétés (in)intéressantes du nombre de l'année.

Pour savoir si un nombre est intéressant, l'instrument de mesure officiel est l'OEIS, l'encyclopédie en ligne des suites entières. Plus un nombre apparaît sur l'OEIS, plus il est intéressant. A titre d'exemple, 2011 possédait 378 propriétés et était, ce ce fait, un nombre particulièrement intéressant (il faut dire que c'était un nombre premier, une vertu qui se fait de plus en plus rare chez les nombres). Les années 2012 et 2013 possèdent respectivement 121 propriétés et 96 propriétés, ce qui font d'elles des années bien moins intéressantes.

Et 2014, dans tout ça ? Eh bien... Comment dire ?... Il va falloir faire avec... C'est la crise pour tout le monde, hein ?...

2014 possède seulement 76 propriétés !

Ce n'est pas encore cette année que la courbe des propriétés va s'inverser. Mais j'ai cru comprendre que le changement, c'est l'année prochaine. Voyons tout de même ce que le nombre 2014 a à nous offrir.

Excursions de Motzkin [A057585]
Le n-ième nombre de Motzkin (noté Mn), c'est le nombre de façons de placer des cordes non concourantes sur un cercle, entre n points [A001006].

Par exemple, M4 = 9 : il y a 9 façons de dessiner des cordes qui ne se croisent pas entre 4 points d'un cercle :

Motzkin

En cherchant à la main, on peut voir que M1 = 1, M2 = 2, M3 = 4 et que M4 = 9.

Pour calculer les nombre suivants, il faut réfléchir de manière un peu plus récursive. Supposons que l'on vient de calculer Mn, et cherchons Mn+1. Combien y a-t-il de façons de placer des cordes entre ces n+1 points ?
Déjà, il y en a au moins Mn (il suffit d'ignorer ce n+1-ième point que l'on vient d'ajouter.
Maintenant, prenons en compte ce nouveau point, et reliant-le à l'un des autres points, disons qu'il s'agit du k-ième (n choix possibles). Cette corde sépare le cercle en deux morceaux, l'un comptant k-1 points (donc Mk-1 façons d'y placer des cordes), l'autre en comptant en comptant n-k (et donc, Mn-k placements de cordes possibles). Cette séparation offre donc Mk-1×Mn-k façons de placer les cordes.

Schema_Motzkin
La corde [n+1;k] sépare le cercle en deux zones, l'une comptant k-1 points, l'autre n-k.
Il y a donc Mk-1×Mn-k placements comptant cette corde.

Si on fait le compte, il y a Mn placements qui ne prennent pas en compte le n+1 points, et, pour chaque point k entre le 1er et le n-ième, il y a  Mk-1×Mn-k placements comprenant la corde [n+1 ; k]. Donc :

FormuleMotzkin

A l'aide de cette formule, on peut calculer que M5 = 21, M6 = 51, M7 = 127, M8 = 323, M9 = 835 et que M10 = 2188. Non, 2014 n'est pas un nombre de Motzkin (mais on y arrive...)

Mais il existe d'autres façons d'intérpréter les nombres de Motzkin, en particulier, celle des chemins de Motzkin : un chemin qui peut monter, descendre ou aller tout droit, et qui revient à sa hauteur de départ. Le nombre de chemins de Motzkin de longueur n est donné par Mn. Ainsi, il existe 9 chemins de Motzkin de longueur 4 :

CheminMotzkin
9 chemins de Motzkin de longueur 4, autant que de cercles de Motzkin.

On peut obtenir un chemin de Motzkin à partir d'un cercle cordé en le parcourant dans l'ordre de ses points. Un début de corde se traduira par un chemin montant, une fin de corde se traduit par un chemin descendant.

Chemin_8
Exemple de placements de corde sur un cercle à 8 points, et son chemin de Motzkin de longueur 8 correspondant.

La question primordiale qui se pose alors : quid de l'aire sous les chemins de Motzkin ? Pour n=4, on peut compter que A4 = 16. Mais pour n plus grand ? On peut montrer (la démonstration en question a été coupée au montage de cet article) que l'aire totale An sous les chemins de longueur n est donnée par la formule :

FormuleMotzkin2

On peut calculer que A5 = 56, A6 = 190, A7 = 624 et A8 = 2014.

Bref : l'aire totale sous les 323 chemins de Motkin est 2014 ! (Tout ça pour ça...) Et c'est a peu près la seule propriété qui vaut la peine d'être développée parmi tout ce que l'OEIS a à nous proposer.

Mais 2014 a de nombreuses autres propriétés intéressantes :

  • 2014 correspond à la somme de 12 nombres triangulaires (nombres de la forme T(N)=1+2+3+...+N), en commençant par le 12e : 2014 = T(12) + T(13) + ... + T(23). [A119034
  • 2014 est de la forme n(n+15) : 2014 = 38×(38+15). [A132760]
  • Ma préférée : 2014 = 133 - 132 - 131 - 130.[A083074]
  • 5 × 22014-1 est un nombre premier. [A001770]
  • 2014 peut-être écrit comme la somme de plusieurs carrés impairs distincts de 89 façons différentes, c'est plus que pour n'importe quel nombre plus petit. [A167702]
  • Il y a 2014 4-uplets (a,b,c,d), où 1 ≤ a,b,c,d ≤ 7, tels que ab+cd ≤ 49. [A212150]
  • Les 2014e nombre dodécahédral peut s'écrire comme la somme de deux nombres dodécahédraux. C'est plutôt rare ! [A053017]
  • Le numérateur du 4028e (=2*2014) nombre de Bernoulli est divisible par 233. J'ai du mal à comprendre pourquoi cette liste existe... [A092228]
  • Et c'est à peu près tout...

Du côté des propriétés qui trainent sur Twitter aux alentours du premier janvier, on a :

  • 1024 + 512 + 256 + 128 + 64 + 16 + 8 + 4 + 2 = 2014 (@mikko)
  • (10 + 9 ) × ((8×7) + 6 - 5 - 4) × (3 - 2 + 1 + 0) = 2014 (@alexbello)

Bref : bonne année 2014 !

Et la santé !



01 décembre 2013

[#] Calendrier de l'avent

Et pourquoi pas un calendrier de l'avent, en attendant petit papa Noël ? A la manière des Shots of science, un nouvel instantané mathématique sera ajouté tous les jours dans cet article, histoire de frimer à la machine à café  (pour peu que vous ayez des collègues compréhensifs...)

Posté par El Jj à 00:01 - Commentaires [7]
Tags : ,

24 novembre 2013

[#] Bézout futé

Le théorème de Bézout n'est pas qu'un théorème d'arithmétique vu en Terminale, c'est aussi un des principaux résultats de la géométrie algébrique. Ce qui est chouette avec ce résultat, c'est qu'il est manifestement faux au premier abord, mais qu'il devient particulièrement satisfaisant quand on s'y penche un peu. Je ne vais pas le creuser dans cet article, simplement déblayer le terrain. En quelques mots, il dit que :

Deux courbes algébriques de degré n et p ont exactement n×p points d'intersection.

Une courbe algébrique, c'est une courbe dont l'équation est un polynôme (que l'on peut écrire sous la forme P(x,y)=0, comme par exemple 3x36y6+4x²y-1=0). Le degré de la courbe, c'est le degré du polynôme. Globalement, les courbes algébriques, c'est ce qui se fait de plus joli en matière de courbes.

A titre d'exemple, les courbes algébriques de degré 1 sont les droites (ax + by + c = 0), celles de degré 2 sont les coniques (paraboles, hyperboles, ellipses...). Plus on grimpe en dégré, plus les courbes sont compliquées à appréhender.

Vous avez échappé à des cubiques de tous horizons, faute de place.

Quelques exemples de courbes algébriques de degré 1 et 2.

Ainsi, d'après le théorème de Bézout, deux droites (degré 1) se coupent toujours en un (=1×1) seul point, deux coniques (degré 2) se coupent toujours en 4 (=2×2) points, une droite (degré 1) coupe toujours une cubique (degré 3) en exactement 3 (=1×3) points...

Jusqu ici, tout va bien (Sophia Aram)

A gauche, l'intersection d'un cercle (degré 2) et d'une cubique de Humbert (degré 3) donne 6 points d'intersection
A droite, l'intersection de deux cubiques (de degré 3) donne 9 points d'intersection

Mais ça, c'est ce qu'il se passe dans un monde parfait. Les contre-exemples sont malheureusement légion :

En général, on se contente d un seul contre-exemple. Quand on en a besoin de quatre, c est que l on cherche à compenser quelque chose.

Quatre contre-exemples au théorème de Bézout.

Et pourtant, dans chaque cas, le nombre de points annoncé est bien le bon. Il y a cependant de nombreuses subtilités...

Sauf que... la multiplicité
Dans certains cas, un même point d'intersection comptera plusieurs fois (on parle de la multiplicité de ce point d'intersection). C'est injuste, mais il faut faire avec. Cette situation peut arriver sous plusieurs formes différentes.

Déjà, il y a les courbes qui s'auto-intersectent. C'est par exemple le cas de la cubique x3 - 3x² + y² = 0 (représentée dans le premier contre-exemple), dont la courbe forme une boucle. Au point (0,0), la courbe s'auto-coupe, ce point là sera donc compté deux fois s'il intervient dans une intersection.

On pourrait surement faire une version algébrique du Scrabble, dans lequel les points compteraient double...

Le point (0,0) appartient à la fois à l'arc vert et à l'arc jaune, il sera donc compté deux fois, ce qui donne bien trois points d'intersection.
Remarquons que si on déplace un peu la droite bleue, on retrouve trois vrais points d'intersection.

Lorsque les courbes se touchent sans se croiser, on tombe aussi sur des points comptés double (voire pire). En particulier, c'est ce qui se passe lorsque l'on compte le nombre de point d'intersection entre une courbe et l'une de ses tangentes. 

Ca serait un scrabble où, au lieu de jouer des lettres, on jourait des polynômes !... Non, ça semble définitivement être une mauvaise idée.

La droite bleue est tangente à la courbe rouge au point (2,2), ce point d'intersection comptera double.
En déplaçant un peu la droite, on peut faire apparaître ces deux points.

Le théorème de Bézout est en fait:

Deux courbes algébriques de degré n et p ont exactement n×p points d'intersection, comptés avec leur multiplicité.

Sauf que... les nombres complexes
Le problème de la représentation graphique des courbes algébriques, c'est qu'elles ne sont que la partie émergée de l'iceberg. Rien n'oblige les courbes à se croiser dans le plan réel, les points d'intersection peuvent parfaitement être complexes. Et cette situation arrive bien trop souvent pour être négligée.

On peut reprendre l'exemple des points d'intersection de la parabole d'équation y-x²=0 et de l'ellipse d'équation x²+2y²-y-2=0. Les points (-1;1) et (1;1) sont solutions, mais les points (i;-1) et (-i;-1) aussi (vérifiez par le calcul si vous ne me croyez pas !). On a bien les quatre points attendus.

DesCourbesComplexes

En comptant les points à coordonnées complexes, on a bien 4 points d'intersection.

Le théorème de Bézout est en fait :

Deux courbes algébriques de degré n et p ont exactement n×p points d'intersection dans le plan complexe ℂ² , comptés avec leur multiplicité.

Sauf que... les points à l'infini
Où se coupent deux droites parallèles ? Eh bien, elles se croisent... à l'infini ! Pour le voir, il suffit de pencher un peu la caméra pour regarder ce qu'il se passe au loin. En faisant cela, on fait apparaître la ligne d'horizon, où se rencontrent toutes les droites parallèles.

Là où toutes les droites se croisent...

A gauche : deux droites parallèles, vu de dessus
A droite : deux droites parallèles, vu de biais

Ces deux droites, courbes algébriques de degré 1, possèdent donc bien un unique point d'intersection, mais il est "à l'infini". Ce point d'intersection n'est pas dans le plan, mais dans le plan projectif, où l'on a ajouté tous les points à l'infini (chaque point à l'infini correspond à une direction de droite).

De la même façon, on peut voir que la droite et la parabole du premier exemple possèdent bien deux points d'intersection, dont un à l'infini :

Après 3 heures de réflexion, j ai enfin réussi à dessiner ce f$#$* plan projectif !

En penchant la caméra, la parabole devient une ellipse, faisant apparaître un deuxième point d'intersection à l'infini. On peut en fait démontrer que n'importe quelle conique est une ellipse, pourvu qu'on la regarde sous le bon angle.

C'est aussi ce qui arrive lorsque deux courbes sont asymptotes l'une à l'autre : elle se croisent sur la ligne de l'infini (et en plus, le point d'intersection sera de multiplicité 2 ou plus).

Le théorème de Bézout est en fait :

Deux courbes algébriques de degré n et p ont exactement n×p points d'intersection dans le plan projectif complexe P2(ℂ) , comptés avec leur multiplicité.

Sauf que... des composantes communes
Un dernier point à vérifier pour que le théorème fonctionne parfaitement : il ne faut pas que les courbes aient des composantes communes.

Par exemple, prenons les courbes (de degré 2) d'équation x² - 1 = 0 et xy-x-y+1=0. Selon Bézout, ces courbes devraient avoir 4 points en commun. En réalité, ces courbes ont une infinité de points d'intersection :

Non, ces courbes ne sont pas vraiment intéressantes.
Les deux courbes ont une composante commune, la droite verticale d'équation x=1, qui correspond donc à une infinité de points en commun.

Le problème, c'est que les courbes en question peuvent être écrites comme la réunion de courbes de degré plus petit (des composantes irréductibles). La première est la réunion des droites d'équation x-1=0 et x+1=0, la deuxième est la réunion des droites d'équation x-1=0 et y-1=0. Les deux courbes ont une même composante commune (x-1=0), et le théorème de Bézout n'est pas prévu pour ça.

Le théorème de Bézout est en fait :

Deux courbes algébriques sans composantes communes de degré n et p ont exactement n×p points d'intersection dans le plan projectif complexe P2(ℂ) , comptés avec leur multiplicité.

Maintenant, on peut appliquer le théorème, et jouer au jeu pratiqué dans le cercle très fermé des géomètres algébristes : "où sont passés les points d'intersection manquant ?!".

Par exemple, combien de points d'intersection possèdent ce quadrifolim (en bleu), de degré 6, et ce trifolium (en rouge), de degré 4 ?

Oui, j ai piqué cette image sur wikipédia. Mais on a rarement de si joli points de multiplicité 14.

A première vue, on compte 5 points d'intersection, mais il y en a en fait 24 :
4 points réels, de multiplicité 1
1 point réel, de multiplicité 14
2 points complexes à l'infini (les deux à la fois !), de multiplicité 3

(Et joyeux anniversaire à ce blog, qui vient de fêter ses 7 ans !)


A lire également :
Bézout et les intersections de courbes algébriques, sur BibNum, analyse de Liliane Alfonsi du texte original de Bézout.

13 octobre 2013

[#] Indivisibles

Tout bon agenda de lycéen comporte une page regroupant les formules d'aires et de volumes des figures usuelles. Certaines formules coulent de sens (aire d'un carré, d'un rectangle), d'autres sont évidentes si on prend deux secondes pour y réfléchir (aire d'un triangle, d'un parallélogramme). Et il y a les autres, qui semblent sortir de nulle part : pourquoi l'aire d'un disque de rayon r est πr² ? Et pourquoi le volume d'une sphère est de  4/3 π r3 ?

Ces formules ont été découvertes assez vite, mais au fil de l'histoire, ce sont les démonstrations qui ont évolué. Dans l'antiquité, Euclide et Archimède ont utilisé la méthode d'exhaustion pour prouver l'équivalent de ces formules : l'aire d'un disque ne peut pas être plus grande que πr², elle ne peut pas être plus petite non plus, elle lui est donc égale.
Cette méthode d'exhaustion fait appel aux limites, autrement dit, à l'infini. La notion d'infini étant taboue à l'époque, les calcul d'aires étaient plutôt limités.

Aujourd'hui, pour calculer l'aire ou le volume d'une figure, on utilise l'intégration, qui fait appel à des sommes infinies d'objets infiniment petit. Depuis que l'on sait dompter l'infini, ce genre de calculs ne fait plus peur à qui que ce soit.
Entre temps, il y a eu le XVIIe siècle. A l'époque, l'infini n'était toujours pas parfaitement assimilé, mais plus personne n'avait peur de le manipuler, quitte à faire pleurer n'importe quel mathématicien moderne. C'est à cette période que John Wallis invente le symbole ∞ et que Leibniz et Newton inventent/découvrent le calcul infinitésimal moderne.

Juste avant ces progrès, il y a eu Cavalieri et Roberval, qui ont mis au point une méthode redoutable pour calculer des aires et produire de nouvelles formules. La seule ombre, c'est que cette méthode miracle ne fonctionne pas dans toutes les situations, sans que l'on ne sache exactement pourquoi. Aujourd'hui, on le sait : l'infini doit être manipulé avec précaution pour éviter les paradoxes. Il n'empêche, leur méthode fonctionne !

Robin l'avait évoqué dans cet excellent épisode de Podcast Science sur l'infiniment petit, j'ai voulu creuser un peu. La méthode des indivisibles de Cavalieri, ancêtre du calcul intégral, comment ça marche ?

Le principe de Cavalieri
L'idée de base est de considérer une surface comme l'empilement d'un nombre indéfini de lignes, toutes parallèles. Si deux surfaces sont composées de lignes deux à deux de même longueur, alors les surfaces auront la même aire.

MemeAire

Ces deux triangles sont formés d'un empilement de segments, deux à deux de même longueur. Les deux triangles ont donc la même aire.
Ceci permet de montrer que n'importe quel triangle est équivalent à un triangle rectangle, et donc, d'aire ½ b×h.

Avec cette méthode, pour montrer que deux surfaces ont la même aire, il suffit de montrer que les segments transversaux ont deux à deux la même longueur. La méthode fonctionne également pour le calcul de volumes, comme empilement d'un nombre indéfini de plans.

Ces lignes, on les appelle les "indivisibles". Le gros soucis, c'est que l'on ne comprend pas vraiment leur nature : ce ne sont pas des segments, ce ne sont pas des rectangles, c'est probablement quelque chose entre les deux.

Quadrature de la cycloïde
Le premier morceau de bravoure de cette théorie naissante a été celui de la quadrature de la cycloïde
, la courbe qui correspond à la trajectoire d'un point sur le bord d'un disque qui roule :

Cycloid_f

Fait particulièrement intéressant : l'aire située sous cette courbe correspond à trois fois l'aire du disque qui l'a générée. Ça, c'est Galilée qui l'a découvert, après avoir construit et pesé des cycloïdes en métal. Il a cependant refusé de croire que ce résultat était correct, et a conclu à une erreur de mesure (1599). Le premier calcul de cette aire est dû à Roberval, grâce à la méthode de Cavalieri (qui était un étudiant de Galilée).

Pour cela, nous avons besoin :
- du cercle générateur, en vert, d'aire Adisqueπ
- de la cycloïde, en bleue
- de sa courbe "compagnon", en rouge, définie à partir du cercle générateur de la façon suivante : pour un point A du cercle, on construit le point M à la même hauteur de A, et dont l'abscisse 0N est égale à la longueur de l'arc de cercle 0A.

Cycloide1

Disque générateur en vert (de rayon r, donc de circonférence 2πr)
Cycloïde en bleu. Après déplacement du disque, le point 0 se retrouve en position 0'.
Courbe compagnon en rouge. Par construction, la longueur 0N est égale à la longueur de l'arc violet 0A.

On peut alors montrer que :
- les portions situées entre la cycloïde et sa courbe compagnon ont chacun l'aire d'un demi disque.
- l'aire sous la courbe compagnon est égale au double de celle du disque.
Finalement, l'aire sous la cycloïde est égale à l'aire de trois disques.

* Aentre les courbes = ½ Adisque
On utilise ici la méthode de Cavalieri. Les segments du demi-disque sont de même longueur que ceux de l'entre-deux courbes, les aires sont donc égales.

 

AHegaleEMLes segments à hauteur égale sont de même longueur. D'après la méthode de Cavalieri, les deux aires hachurées sont égales.

Sur le schéma ci-dessus, on prend un point A sur le cercle C, et on considère les points H, E et M à hauteur de A sur, respectivement, le diamètre vertical du cercle C, sur la cycloïde et sur la courbe compagnon. Il s'agit de montrer que AH = EM. Pour cela, on considère le point L, intersection du cercle C et de EM (lui aussi, à hauteur de A). Lorsqu'on fait tourner le cercle C pour qu'il aille en position C', puisque les arcs 0L=0A=0N, L est envoyé sur N, et donc, 0 est envoyé sur E (car 0L=EN). Donc le point E appartient au cercle C'. Le cercle C' peut alors être vu comme le translaté de C, de même pour les segments AH et EM : ils sont donc identiques.

* Acompagnon = 2 Adisque
On se place dans le rectangle (0,0),(πr,0),(πr,2r),(0,2r), d'aire b×h = πr×2r = 2πr².

BallonDeRugbyLa courbe compagnon est symétrique !

Il suffit alors de remarquer que la courbe compagnon est symétrique par rapport au centre de ce rectangle (pour s'en convaincre, on peut tracer une deuxième cycloïde), elle le coupe donc en deux parts égales. Donc l'aire sous cette demie courbe compagnon est πr², qui est l'aire du disque.

Bref : l'aire de la cycloïde, c'est trois fois l'aire du disque. Yeah !

 

Quadrature du cercle
La méthode de Cavalieri fonctionne aussi lorsque les lignes ne sont pas des segments. Il faut évidemment prendre encore plus de pincettes, mais cela donne une méthode assez intuitive permettant de calculer l'aire du disque.

Aire_disquePour calculer l'aire d'un cercle de rayon r, on considère tous les cercles concentriques de rayons k ≤ r. Chacun de ces cercles a une circonférence égale à 2πk. On redresse alors tous ces cercles : on obtient un triangle isocèle de base b = 2πr (la circonférence du disque initial), et de hauteur h = r (le rayon du disque initial).

L'aire de ce triangle est alors de b × h ÷ 2 = 2πr × r ÷ 2 = πr². Yeah !

La quadrature ratée du triangle
Parlons tout de même de ce qui fâche : la méthode de Cavalieri ne fonctionne pas dans tous les cas. Ce n'est pas parce que les lignes sont deux à deux de même longueur que les aires seront égales. On sent bien, sur l'exemple ci-dessous, qu'il y a "plus" de lignes dans le premier triangle que dans le deuxième...

Paradoxe_CavalieriLes deux segments oranges sont de même longueur, les deux rectangles devraient avoir la même aire...

Quadrature du rouleau de PQ
En s'inspirant du calcul de l'aire du disque par la méthode de Cavalieri, on peut en déduire une excellente méthode permettant de calculer le nombre de feuilles de papier toilette dans un rouleau. La principale différence d'avec la méthode de Cavalieri, c'est que les feuilles de papier toilette ne sont pas infiniment fine (et heureusement).

Quadrature_du_PQ

Il suffit finalement de se rendre compte que, en redressant chacune des feuilles du rouleau, on obtient un paquet de feuilles, rectangulaire. En notant R (resp. r) le rayon du rouleau plein (resp. vide), l'aire latérale du rouleau est π(R²-r²). En notant L la longueur d'une feuille, N le nombre de feuilles dans un rouleau et e son épaisseur, on trouve que l'aire du paquet est LNe.

D'après Cavalieri, les deux aires sont égales, donc le nombre N de feuilles dans un rouleau de papier toilette est donné par...

Nb_Feuilles_PQ

Ce qui, pour R = 4.5 cm, r = 2 cm, L = 12.5 cm et e = 0.015 cm, nous donne environ 270 feuilles. Yeah !


Sources :
Cycloids and Paths : Tout sur la cycloïde
Méthode des indivisibles, sur Wikipedia

Images :
Cycloid

Posté par El Jj à 10:00 - Commentaires [11]
Tags : , ,

07 octobre 2013

[#] De l'humour mathématique

Une nouvelle chaîne, initiée par Eric de Rock 'n' science vient de voir le jour sur le c@fé des sciences : blague à caractère scientifique. L'objectif est de mettre en avant ce que la science a fait de meilleur en terme de vannes vaseuses et jeux de mots approximatifs. Je ne pouvais pas passer à côté de cette occasion pour poster mes blagues mathématiques préférées. Celle que j'ai choisi de mettre en valeur, je l'ai découverte il y a quelques mois, et, chose rare, je l'ai retenue ! 

matrix_transform

The best joke ever
Je préfère prévenir : le public succeptible de comprendre cette blague est très restreint. Du coup, je ne suis plus à un snobisme près, et je vais faire l'affront de la publier en anglais... La voici :

A comathematician is a device for turning cotheorems into ffee.

Ce qui, en français, donne :

Un comathématicien est une machine à transformer les cothéorèmes en fé.

(Du coup, on perd le jeu de mot...) 

La meilleur blague jamais : explication
Ce bon mot fait en fait référence à une citation du mathématicien honrois Alfréd Rényi (et non, comme on le voit souvent, de Paul Erdõs, avec qui il a cosigné de nombreux papiers) :

Un mathématicien est une machine à transformer le café en théorèmes.

Autrement dit, un mathématicien n'a besoin que de café pour produire des théorèmes. La citation contiendrait également un jeu de mot en allemand, sans doute volontaire de la part de Rényi : "Satz" signifie à la fois "théorème" ("Lehrsatz") et "marc de café" ("Kaffeesatz").

En anglais, "café" se traduit par "coffee", qui contient le préfixe co- si cher aux mathématicien (cosinus, cotangente...). Ce préfixe intervient surtout quand on parle d'homologie, une technique intervenant dans divers domaines (algèbre, topologie...) et dans lequel on étudie le comportement d'une opération entre des espaces de dimensions décroissantes (l'homologie) ou croissantes (la cohomologie). Généralement, quand il existe une homologie dans un sens, on a une cohomologie dans l'autre sens (son dual). Finesse de vocabulaire des matheux : pour passer de l'homologie à la cohomologie, il suffit généralement d'ajouter ou d'enlever le préfixe co-. 

Avec le vocabulaire de l'homologie, la citation de Rényi devient :

Mathematician : coffee → theorems

Quand on passe en cohomologie, on change de sens et on enlève/ajoute co-, ce qui donne la blague en question :

Comathematician : cotheorems → ffee.

CQFE (ce qu'il fallait expliquer)

Degré d'une blague mathématique
On peut définir récursivement le degré d'une blague mathématique de la façon suivante :

  • Une blague est de degré 0 lorsqu'elle n'a rien de mathématique.
  • Une blague est de degré n+1 lorsqu'elle peut être obtenu à partir d'une blague de degré n en lui ajoutant une notion mathématique.

Quelques exemples :

  • "Qu'est ce qu'un canif ? Un p'tit fien" est une blague de degré 0, puisque, même en cherchant bien, il n'y a rien de mathématique là-dedans.
  • "Quelle est l'anagramme de Banach-Tarski ? Banach-Tarski Banach-Tarski" est une blague de degré 1, puisqu'elle fait référence au théorème de Banach-Tarski, qui démontre que l'on peut découper et réassembler un objet de manière à former deux copies identiques de cet objet.
  • "Il existe 10 sortes de personnes : celles qui connaissent le ternaire, celles qui ne le connaissent pas et celles qui pensent que c'est du binaire" est de degré 2, puisqu'elle s'appuie sur la blague suivante, de degré 1 : "Il existe 10 sortes de personnes : celles qui connaissent le binaire et les autres".
    Notons que cette blague peut servir à construire une blague de degré arbitrairement long, en considérant d'autres bases de numérations - une blague de degré 42 ressemble à "Il existe 10 sortes de personnes, celles qui connaissent la base 41, celles qui ne le connaissant pas, celles qui pensent que c'est de la base 40, celles qui pensent que c'est de la base 39, ..., celles qui pensent que c'est du binaire". Les blagues en question perdent cependant très vite de leur force comique.

La blague du comathématicien est à mon sens le seul exemple vraiment valable de blague de degré 3. En effet, elle s'appuie sur la citation de Rényi, qui est de degré 2 (puisqu'elle mêle réflexion sur le métier de mathématicien et jeu de mot hilarant en allemand).

Le papier introduisant cette notion de degré d'une blague (Pourquoi est-il si diffcile de calculer le degré d’une blague mathématique ?) donne un autre exemple de blague de degré 3, mais je dois admettre qu'elle ne m'a pas vraiment convaincu.

Pour terminer, une autre bonne blague à raconter demain matin à la machine à café :

Trois logiciens entrent dans un bar. Le barman leur demande : "un café pour chacun ?"
Le premier logicien répond : "Je ne sais pas".
Le deuxième répond alors : "Je ne sais pas".
Le dernier conclut : "Oui".

(Et j'attends vos meilleures blagues dans les commentaires. Attention : toute blague à base de jeu de mot sur l'intégration ou la dérivation de fonctions exponentielles, logarithme ou trigonométriques est prohibée.)


Sources :
Dimitri Karpov, Minos Libbouet, Roland Triedich, Pourquoi est-il si difficile de calculer le degré d’une blague mathématique ?,
Bruno Winckler, Recueil de blagues mathematiques : Plus de 100 pages d'humour mathématique, à lire absolument !
Image :
Xkcd, Matrix Transform

Posté par El Jj à 21:00 - Commentaires [30]
Tags :

22 septembre 2013

[#] Cliquez plus pour gagner plus (de cookies)

Alors que les grands médias se gargarisent des coûts de production et de la violence du dernier GTA, c'est un tout autre jeu qui affole la toile de l'Internet : le génial Cookie Clicker. Créé en quelques heures (!), pour rigoler (!!), par Orteil, (le créateur d'excellents chronophages dont la moitié ont disparu de la surface d'internet [mais le BFGFT survivra !]), ce jeu en javascript (!!!) a connu un succès incroyable, à tel point qu'une société japonaises va commercialiser des figurines de la mamie du jeu !

En fait, Orteil était un voisin de blog quand j'ai débuté le blogging il y a presque 10 ans. Je dois être honnête : c'est terriblement émouvant de voir que, du jour au lendemain, un membre de sa famille numérique a le droit à des félicitations de Notch ou à des reprises japonaises !

CookieClickerArtworkNon, les jeux vidéo ne rendent pas violent, mais ils peuvent donner envie de manger des cookies.

Cookie clicker ?
Le concept de Cookie Clicker est très simple : on clique sur un cookie pour gagner des cookies. Quand on a assez de cookies, on peut les échanger contre des curseurs supplémentaires, des mamies ou des bâtiments divers (fermes à cookies, usines à cookies, laboratoires d'alchimie pour transformer l'or en cookies, portail vers le cookieverse...) pour gagner encore plus de cookies. Cookie sur le gâteau : le jeu est bourré de références à la culture geek sous toutes ses formes. L'objectif du jeu, c'est de gagner des cookies, plein de cookies, trop de cookies !

Commeil n'y a pas d'objectif précis, le mien sera le suivant : posséder un million de cookies !

Les différents "bâtiments" sont les suivants :

  • Le curseur, coûte 15 cookies, rapporte 0.1 cookie par secondes (c/s).
  • La mamie, coûte 100 cookies, rapporte 0.5 c/s..
  • La ferme, coûte 500 cookies, rapporte 2 c/s.
  • L'usine, coûte 3 000 cookies, rapporte 10 c/s.
  • Le vaisseau spatial, coûte 40 000 cookies, rapporte 100 c/s.
  • Le laboratoire d'alchimie, coûte 200 000 cookies, rapporte 400 c/s.
  • Le portail interdimensionnel, coûte 1 666 666 cookies, rapporte 6 666 c/s.
  • La machine à remonter le temps, coûte 123 456 789 cookies, rapporte 98 765 c/s.
  • Le condensateur d'antimatière, coûte 3 999 999 999 cookies, rapporte 999 999 c/s.

Cliquer sur le cookie rapporte un cookie par clic. Avec une cadence raisonnable, on peut estimer qu'ils rapportent 6 cookies par seconde.

Le prix indiqué est le prix du premier bâtiment de chaque type. Après chaque achat, le prix d'un bâtiment supplémentaire est augmenté de 15 %. Ainsi, le premier curseur coûte 15 cookies, le deuxième 17 cookies, le troisième 20 cookies, le n-ième coûte 15×1.15n-1  cookies. Le 200e curseur - qui permet de débloquer un achievement - coûte donc environ 18 000 000 000 000 cookies (suite géométrique powaaa) ! Le nombre de cookies dépensés lors de l'achat du n-ième curseur est alors de 100×(1.15n-1). Fait intéressant : les 5 derniers achats représentent la moitié des cookies dépensés au total.

100 curseursNombre de cookies nécéssaires à l'obtention de 100 curseurs.

Il est aussi possible, pour des sommes astronomiques, d'acheter des upgrades qui permettent d'améliorer de manière dérisoire la productivité de chaque bâtiment. Oublions-les pour le moment.

Je veux une mamie !
Une mamie coûte 100 cookies, un curseur rapporte 0.1 c/s.

  • Avec 1 curseur, il faut donc 1000 secondes pour obtenir la mamie.
  • Avec 2 curseurs, il faut 500 secondes pour obtenir la mamie, auxquelles s'ajoutent les 170 secondes nécessaire à l'obtention du deuxième curseur. Il faut donc 670 secondes pour obtenir la mamie.
  • Avec 3 curseurs, il faut 334 secondes pour obtenir la mamie, mais il faut ajouter 170 secondes pour le 2e curseur, et 100 secondes pour le 3e curseur. Il faut donc 604 secondes.
  • Avec 4 curseurs, il faut 597 secondes ;
  • Avec 5 curseurs, il faut 611 secondes.

Autrement dit, le moyen le plus rapide d'obtenir une mamie (sans cliquer sur le cookie) est de préalablement acheter 4 curseurs. Si on s'autorise à cliquer le cookie, 17 secondes suffiront (mais les warriors n'utilisent pas ces artifices !).

Je veux une ferme !
Une ferme coûte 500 cookies ! Avec 4 curseurs et une mamie, LA production est donc de 0.9 c/s.

  • Si je me contente d'une seule mamie et de 4 curseurs, il faudra 556 secondes.
  • Avec 2 mamies et 4 curseurs (1.4 c/s), la ferme demande 357 secondes. La mamie supplémentaire, qui coûte 115 cookies, réclame 128 secondes. Bilan : il faut 485 secondes.
  • Avec 2 mamies et 5 curseurs (1.5 c/s), la ferme demande 333 secondes, auxquelles s'ajoutent le 5e curseur (26 c à 0.9 c/s : 29 s) et la 2e mamie (115 c à 1 c/s : 115 s). Bilan : 477 secondes.
  • Avec 2 mamies et 6 curseurs (1.6 c/s), la ferme demande 313 secondes. On ajoute le 5e curseur (26 c à 0.9c/s : 29 s), le 6e curseur (30 c à 1 c/s : 30s) et la 2e mamie (115c à 1.1 c/s : 105 s). Bilan : 476 secondes (en comptant les arrondis).
  • Avec 2 mamies et 7 curseurs, la ferme demande 481 secondes.

On peut vérifier que, quelle que soit la façon dont on s'y prend, la ferme demandera plus de temps si on achète préalablement une mamie supplémentaire.

Bref, il faut acheter dans l'ordre :
Curseur × 4, mamie, curseur × 2, mamie puis ferme (ce qui demande au total 1072 secondes).

Le hic, c'est que l'on peut faire mieux, en attendant un peu avant d'acheter sa première mamie... La séquence curseur × 5 , mamie, curseur, mamie, ferme ne demande que 1059 secondes !

C'est contre-intuitif : pour gagner plus, il peut être nécéssaire d'attendre un peu avant de faire son premier gros achat... Suivant l'objectif à long terme que l'on cherche, les stratégies sur le court terme sont différentes.

Je veux un millions de cookies !
Quel est donc le temps minimal pour obtenir un millions de cookies ? Le raisonnement s'arrête ici, je laisse ma place au calcul à la pelleteuse.

En cherchant parmi toutes les stratégies de la forme "acheter des curseurs, puis des mamies, puis des fermes,  etc.", la méthode la plus rapide est la suivante : acheter 6 curseurs, 6 mamies , 6 fermes, 7 usines, 6 vaisseaux et 2 laboratoires. Il faudra alors 4920 secondes, pour une production finale de 1485.6 cookies (soit 1 h et 22 minutes, dont 11 minutes à attendre après le dernier achat). 

En ajoutant ici et là d'autres achats de curseurs, de mamies ou de ferme, on peut diminuer le temps total, mais il me semble inenvisageable de faire mieux que 1h21 sans utiliser d'upgrades, sans manger de cookie doré et sans cliquer comme un taré sur ce cookie. A en croire Youtube, le record actuel est de 6 minutes 39 (mais tout le monde s'accorde pour dire que les cookies dorés, c'est de la triche).

Pour résumer les choses :

  • Suivant l'objectif à long terme que l'on se donne, les objectifs à court terme ne seront pas les mêmes.
  • Trouver la bonne stratégie à long terme demande beaucoup trop de temps de calcul, autrement dit, du temps que l'on perd à ne pas cliquer sur le cookie.
  • Orteil est un génie.

Posté par El Jj à 10:00 - Commentaires [4]
Tags : ,


  1  2  3  4  5    Fin »
Licence Creative Commons
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 France.