Math 'O Man : le Blog des Maths

Un arbre qui pousse




Dans ce temps de grand froid, je lance un appel au printemps! On fait pousser un arbre selon la règle suivante. De chaque nœud x partent deux branches, l'une vers le nœud x/(1+x) et l'autre vers le nœud (1+x)/x

.

arbre binaire

On suppose que l'arbre repose sur une racine bien costaud, le nombre 1; et qu'on l'arrose si bien qu'il pousse vers le ciel infiniment haut. Quelle est alors son image, c'est-à-dire l'ensemble des nombres qu'il atteint? Y a-t-il des doublons?



Partagez-le sur Facebook Tweetez-le ! S'abonner à ce blog ? Envoyer cet article à un ami ? Le soumettre à Netvibes Ajoutez-le à Google Bookmarks

Commentaires


1. Le mardi 7 février 2012 à 22:10, par Ylrahc

Pas de doublon (par l'absurde).
Je dirais que l'ensemble des nombres atteint est l'ensemble des rationnels strictement positifs, en tout cas il lui est au moins isomorphe, ça doit peut être pouvoir se prouver par récurrence en ordonnant ces nombres avec intelligence...faut que je réfléchisse (dur.)


2. Le mercredi 8 février 2012 à 00:26, par MathOMan

@Ylrahc : Oui, ce n'est pas si simple. (D'ailleurs je viens d'essayer de laisser un commentaire sur votre blog, mais c'est impossible. Cette restriction est peut-être la raison pourquoi il y a si peu de commentaires sur votre blog?)


3. Le mercredi 8 février 2012 à 05:17, par FelixCQ

J'ai cherché un bon bout de temps, et ce problème est en fait plus facile qu'il n'y paraît: l'arbre contient bien tous les rationnels positifs, et chacun n'apparaît qu'une fois. Je dirais même plus, la profondeur dans l'arbre de chaque rationnel \frac{p}{q} est égale au nombre d'étapes dans l'algorithme d'Euclide (par soustraction) pour déterminer le PGCD de p et q.

Pour s'en convaincre, il suffit d'observer tout d'abord que chaque branche gauche sera (strictement) plus petite que 1, et chaque branche droite (strictement) plus grande que 1. Etant donné un rationnel, on peut donc déterminer à coup sûr, s'il est dans l'arbre, d'où il vient. Si \frac{p}{q} < 1, il est la branche gauche de \frac{p}{q-p}, et si \frac{p}{q} > 1, il est la branche droite de \frac{q}{p-q}. N'ayant qu'un ancêtre possible à chaque étape, il ne peut y avoir de doublons.

De plus, en revenant pas à pas à la racine de l'arbre, on effectue bel et bien l'algorithme d’Euclide par soustraction ! Ayant choisi p et q premiers entre eux (comme toute représentation d'un rationnel qui se respecte), on arrive bien à 1. Il suffit ensuite de renverser les étapes de l'Algorithme pour arriver au rationnel souhaité à partir de 1.


4. Le mercredi 8 février 2012 à 10:02, par MathOMan

Bravo, Ylrahc a bien conjecturé et FelixCQ a fourni la preuve. En plus, il a adopté le point de vue élégant qu'il fallait. Et cela malgré l'heure nocturne à laquelle il a posté son commentaire!

Je trouve que c'est une jolie manière de montrer que l'ensemble des nombres rationnels est dénombrable. Ca change de la démonstration habituelle en zig-zag sur les points à coordonnées entières dans le plan.


5. Le mercredi 8 février 2012 à 21:52, par Ylrahc

Héhé, bravo FelixCQ, en réfléchissant un peu aujourd'hui j'avais compris que la clef était la primalité entre eux des numérateurs et dénominateurs (si p et q sont premiers entre eux, ceux des successeurs de p/q [p/(p+q) et (p+q)/p] le sont aussi), prendre le problème à l'envers en trouvant les prédécesseurs et en utilisant l'algorithme d'Euclide est très élégant :)
@Mathoman : Merci de l'info, je vais regarder ça. Il est possible que ne puissent poster de commentaires que ceux qui ont un compte authentifié compatible blogger (openID, google). Je vais l'ouvrir aux anonymes. Mais je pense que l'absence de commentaires est surtout due à la très faible popularité du blog :)


6. Le mercredi 8 février 2012 à 22:09, par FelixCQ

C'est en effet un très jolie manières de classifier les rationnels ! A-t-elle d'autres implications ?
Si je ne dis pas de bétises, on a à chaque niveau les mêmes rationnels que dans l'arbre de Stern-Brocot, mais dans le désordre !

Pour info: fr.wikipedia.org/wiki/Arb...
Ou encore: mapage.noos.fr/r.ferreol/...


Ajouter un commentaire

Pourquoi ne pas lire aussi :


Arbre généalogique de mathématiciens


Lorsque j'ai travaillé avec Gérald Calderon sur le film Origine Océan nous avons consacré une petite scène à un être unicellulaire nommé LUCA (Last Universal Common Ancestor), notre dernier ancêtre commun universel dont sont issues l'ensemble des espèces.

On peut se poser la question amusante s'il existe un LUMA (Last Universal Math Ancestor) — et pour répondre à cette question on peut s'aider d'une base de données de l'université américaine NDSU.

Il s'agit d'un arbre généalogique qui permet d'associer à chaque docteur en mathématiques du monde entier son directeur de thèse. Ainsi j'ai découvert que si je remonte six générations, je trouve parmi mes aïeux l'illustre Hermann von Helmholtz. Mais mon cousin Detlev qui a soutenu sa thèse en 2001 fait encore mieux : il est un descendant scientifique de Hilbert et donc du prince des maths Carl Friedrich Gauß !

Hand waving et dessins en mathématiques


Les chercheurs en mathématiques appellent hand waving une manière d'expliquer une idée oralement et avec les mains, sans faire appel à un formalisme poussé. Dans certaines situations, cette démarche est justifiée et peut être très efficace.

Si on veut être méchant on pourrait dire que, pour expliquer sa nouvelle découverte un mathématicien a besoin de
  • ses mains et 15 minutes s'il s'adresse à un collègue dans la cafétéria de son centre de recherche,
  • cinq transparents et 60 minutes s'il l'expose dans un séminaire,
  • vingt pages qui demandent trois jours de lecture, s'il la publie dans une revue scientifique.
Le problème est que les mathématiques demandent la précision totale, et celle-ci nécessite un formalisme exacte et sans ambiguïté. Oralement, en faisant des dessins avec les mains dans l'air ou sur un brouillon, on peut toujours guider son interlocuteur et l'empêcher de mal comprendre. Mais ce n'est pas le cas en communication écrite où l'auteur est obligé de traduire ses idées en un formalisme que le lecteur devra ensuite retraduire en idées!
Beaucoup d'énergie est perdue dans ces efforts de traduction et re-traduction. Pour minimiser ces efforts le lecteur doit s'entraîner à maîtriser le formalisme et l'auteur, de son côté, doit inventer un formalisme facile à lire et avec des notations intuitives --- et, si possible, ajouter des dessins à son texte!

Malheureusement, dans beaucoup de manuels universitaires, il n'y a pas assez de dessins. Peut-être c'est dû à la paresse des auteurs qui rédigent en LaTeX où il est beaucoup plus rapide d'écrire cinq lignes de formules que de faire un dessin avec PSTricks...

Moi, personnellement, lorsque j'étais étudiant j'adorais les livres de Klaus Jänich, parus dans la série Undergraduate Texts in Mathematics chez Springer, très bien écrits et agrementés de nombreux dessins; en particulier son livre sur la topologie et son livre sur les fonctions holomorphes m'ont beaucoup aidé.
C'est cette démarche, avec beaucoup d'illustrations, que nous avons adoptée pour la rédaction de notre livre Mathématiques L1 pour la première année en université ou en classe prépa.

La collection d'exercices de Vladimir Arnol'd


En 1991 le mathématicien russe Vladimir Arnol'd publia un

Trivium mathématique (fichier pdf).

Il y vise ceux qu'il appelle les mathématiciens ignorants qui ont étudié les super-variétés ou les théorèmes de plongements mais ne savent pas résoudre des problèmes concrets et simples — ou, avec les mots de Pólya, ceux qui ressemblent à des singes qui sont toujours en haut d'un arbre :

A mathematician who can only generalise is like a monkey who can only climb up a tree, and a mathematician who can only specialise is like a monkey who can only climb down a tree. [...] A real mathematician must be able to generalise and specialise. — George Pólya

Selon Arnold le niveau de la culture mathématique baisse. Et il ne parle pas de la baisse du niveau du bac mais de celle du bac+5. (Or, comme le remarque Martin Andler ici, la question de la baisse de niveau est mal posée à cause de la massification de l'enseignement. Le nombre de mathématiciens en l'an 2000 est beaucoup plus grand que celui en 1900, en absolu et aussi en pourcentage de la population.)
Aux yeux d'Arnold je suis certainement un mathématicien très médiocre, voire ignorant ! De la même manière que je suis étonné quand un étudiant titulaire du bac S puisse avoir du mal à dériver sin(2x) ou à distinguer entre condition nécessaire et condition suffisante, Arnold serait choqué par le fait que je ne sais pas faire d'emblée sa liste de problèmes. En fait, si certains exercices de sa liste me sont très accessibles (par exemple les exercices 45 à 55), il y en a d'autres où je ne sais même pas par où commencer, comme par exemple le no. 72 (un problème de diffusion ?).

Pour Arnold cette collection ne contient pas de questions difficiles, mais seulement des questions qui forment le strict minimum essentiel — il serait alors intéressant de savoir combien un agrégé français moyen en résoudra en une semaine si on lui donne acces à wikipedia et à une bibliothèque de recherche. Quelle est votre estimation ? Plus ou moins que la moitié des problèmes ?

Si on regarde la liste des problèmes proposés on voit bien la préférence de l'auteur pour la géométrie et les équations différentielles. Il y a aussi un peu de topologie algébrique, mais on cherchera en vain des questions d'analyse ou algèbre pures, par exemple.

Vladimir Arnol'd est mort il y a trois semaines pas loin de chez moi, dans l'hôpital Saint-Antoine à Paris.

Mise-à-jour : JLT n'a pas chômé pendant le mois de juillet et a résolu la plupart des exercices !

Restent encore à faire: les no. 27, 41, 51, 58, 68, 69, 70, 73, 74.

Les solutions des exercices se trouvent dans les commentaires (pour déplier cliquer ci-dessous) mais ne sont pas dans l'ordre. Pour s'y retrouver utilisez la fonction find (Ctrl+F) de votre browser et recherchez le numéro de l'exercice par exemple sous la forme "no.54" ou "no.04".

MacBook. Première impression : plus chic que pratique


Depuis quelques jours je possède un MacBook Pro. C'est le troisième système d'exploitation que je rencontre dans ma vie. Mon premier était Unix à l'université ; je l'utilisais principalement pour envoyer des emails avec Eudora, pour éditer du code LaTeX dans Emacs et pour programmer un peu en Html.

C'est seulement plus tard, lorsque je me suis acheté un PC, que j'ai fait la connaissance du système d'exploitation du plus riche homme de la planète. Mais je ne l'utilisais pas exclusivement ; en fait mon PC avait une double-fonction pour moi : je le bootais soit sous Linux pour faire du LaTeX comme avant, soit sous Windows pour lancer d'autres applications qui n'existent pas en Linux (principalement des logiciels de MAO, comme Cubase). Plus tard, j'ai découvert MiKTeX de Christian Schenk, une version Windows de LaTeX qui marche très bien avec TeXnicCenter ; cela sonnait alors le glas à mon utilisation de Linux car je pouvais enfin faire fonctionner LaTeX et mes applications audio favoris sous un même système d'exploitation, à savoir Windows.

Alors, dans ce monde si parfait, qu'est-ce qui m'a poussé à acheter un MacBook Pro ? Il y avait principalement deux raisons. D'abord la qualité hardware des PC portables m'a deçu — les touches, le boîtier, tout commencait à se dégrader après un ou deux ans, même avec des bonnes marques comme HP. Beaucoup de mes amis me conseillaient alors les ordinateurs à la pomme. Et il est vrai, mon nouveau MacBook Pro est vraiment agréable à toucher et semble fait pour durer. L'autre raison était que certains logiciels de musique comme le fameux Metasynth de mon ami Eric Wenger ne fonctionnent que sur Mac.

Grâce à BootCamp mon Mac démarre maintenant avec WinXP. Cela me permet de travailler comme toujours avec MiKTeX. Contrairement à ce que je craignais, WinXP fonctionne parfaitement sur le Mac — donc pas de problème au niveau software.

Mais voilà ma grande déception, elle vient plutôt de la hardware : le clavier du Mac. Le clavier du MacBook est conçu pour être chic sans être pratique ! L'élégance a emporté sur la fonctionnalité. Les touches indispensables pour coder en LaTeX n'y existent pas :

~   {   }   [   ]   |   \

Plus précisément, elles existent et sont accéssibles en combinaison avec la touche alt mais il faut connaître leurs emplacements par cœur. C'est assez désagréable. Je ne comprends vraiment pas comment on a pu laisser de côté ces touches si importantes pour tout programmeur.

Sur un Mac on cherchera aussi en vain d'autres touches qu'on connaît d'un PC :

Del   Home   End   PgUp   PgDown

Dans l'édition LaTeX ou Html ces touches sont très pratiques si on veut, par exemple, sélectionner rapidement toute une ligne pour la copier-coller une page plus bas. Leur absence sur le Mac (sous Windows) implique qu'on doit utiliser plus souvent la souris pour sélectionner ou pour descendre et cela signifie une perte de temps ainsi qu'un manque de comfort.

En résumé : Je déconseille le MacBook à tous ceux qui doivent écrire des longs fichiers en un langage de programmation. Le Mac est certainement bon pour un usage multimédia. Pour ceux qui souhaitent, comme moi, faire les deux sur une même machine, ma recommandation est d'acheter plutôt un PC.