Syracusia : gare de triage ?

L’algorithme « 3x+1 » au collège
lundi 2 avril 2012
par  Pierre MARELLO

Une possible utilisation du tableur : trier les nombres par congruences.

Avant de commencer, il serait souhaitable que chacun soit muni d’un petit bagage, adapté aux voyages en train et en avion. Pour cela nous vous invitons à visiter les sites wikipedia ici ou , qui est plus complet mais en anglais.

Notre voyage commence lorsque l’idée m’est venue de mettre en place une sorte de narration de recherche grandeur nature pour des élèves volontaires du collège. Le problème choisi est donc la conjecture de Collatz. L’objectif est de faire chercher et faire rédiger un compte rendu des recherches en cours, de quelque résultats.

La méthode utilisée est alors de tester via un tableur, un maximum de valeurs, de visualiser les « vols », les altitudes maximales, espérant y trouver quelques régularités.

Les nombres premiers, les nombres parfaits, les multiples de 10, de 3, les nombres pairs ou impairs ne livrent aucun miracle.

Par contre l’algorithme semble accepter assez bien les entiers négatifs. Une étude statistique semble même nous montrer que les atterrissages sont possibles cette fois à trois altitudes, avec la même fréquence d’apparition 1/3 (il s’agit des altitudes -1 ; -5 et -17).

Nous avons alors élargi notre étude aux nombres réels, mais très vite nous nous sommes essoufflés. Il devenait très lassant d’entrer une ligne de nombres aléatoires, puis d’observer des colonnes de nombres ou des graphiques correspondant aux vols. Tout semble baigner dans un désordre aléatoire parfait !

Il devenait urgent de passer à un autre moyen de visualiser la suite des valeurs d’un nombre. Nous avons beaucoup travaillé sur le tableau blanc, puis sur une très grande feuille en papier. Il nous fallait construire à la main le début du graphe obtenu à partir de 1. Nous n’avons pas d’éditeur de graphes et c’est tant mieux. Cela nous a d’ailleurs permis de parler d’algorithme inverse (c’est surtout moi qui ai parlé là, je crois...). Mais le fait d’avoir à calculer les valeurs une à une, a obligé les élèves à bien comprendre comment « inverser » l’algorithme. Il ne s’agissait plus de « faire » 3x+1 quand x est impair, mais de faire (X-1)/3 quand X-1 est dans la table de 3... Une excellente gymnastique qui n’a pas été tout de suite maîtrisée.

Pour une raison inexpliquée, nous trouvions plus commode de ranger la suite des puissances de 2 horizontalement, et de faire ensuite « partir » les autres voies verticalement.

Une fois qu’on avait bien compris le principe des création des voies [1], et introduit au passage un vocabulaire s’inspirant non plus de l’aviation mais des chemins de fer, nous avons commencé à reproduire ce graphe en nous servant des lignes et des colonnes du tableur. Artisanal et maladroit, ce bricolage se révélera salutaire pour la suite. Le résultat se trouve dans le doc « visualisation en voies ferrées ».

Toujours dans notre souci de trouver quelques régularités ou répétitions, on a fini par remarquer une formule permettant d’anticiper une valeur [2]. L’avantage d’avoir fait ce graphe sur le tableur, c’est que les nombres sont clairement rangés sur des lignes et des colonnes. Des alignements apparaissent plus facilement. Des rythmes (« ça fait un sur deux en couleur » ) semblent s’imposer. Des arrangements en colonnes ou en lignes correspondent à des formules donnant des familles de nombres (c’est surtout moi qui assure cette partie algébrique pour l’instant pour plein de raisons évidentes ; je n’ai pas envie de transformer le club en séance sur les écritures algébriques)

Cependant, la construction de ce graphe n’est pas aisée, car l’aspect fractal vient enfin jouer son trouble-fête et nous oblige à une gymnastique d’espacement des colonnes qui n’est pas aisée et ne nous permet pas de visualiser clairement beaucoup de valeurs [3]. En plus il se fait « à la main », c’est-à-dire sans possibilité d’utiliser des formules. Artisanal et maladroit disais-je.

C’est pour éliminer cette contrainte d’espacement que l’on à continué à chercher une logique entre les nombres aiguillages et les nombres terminus.

Au retour des vacances de Janvier, après une longue pause, et une fois les machines en marche, l’arrangement des nombres nous est apparu assez évident, bien que cela ait été progressif. Il me semble que c’est en constatant que les nombres terminus semblaient tous impairs, et en observant comment les gares de la voie qui part (ou arrive) de ce terminus sont calculés : ils sont égaux au produit d’une puissance de 2 et du nombre terminus en question. L’exposant étant le numéro d’ordre de la gare sur cette voie, qui correspond au numéro de ligne d’un tableau. Bref, il devenait inutile de faire des espaces entre les colonnes pour visualiser les voies ferrées, les aiguillages et les terminus. Cela a donné le « tableau des correspondances ». Voir la pièce jointe.

Depuis nous prenons plaisir à jouer avec ce tableau qui nous offre enfin une vision (hyper) organisée des nombres entiers, aussi grands qu’on veut, tout en montrant clairement le vol d’un nombre, c’est-à-dire les différentes voies qu’il emprunte et les différentes gares qu’il traverse, jusqu’à 1 [4].

Nous travaillons également sur d’autres formulations de la conjecture de Collatz, notamment sur celle qui ne fait intervenir que les nombres aiguillages. La suite de ces nombres, qui se répartissent avec une régularité remarquable dans le tableau des correspondances, nous intéresse fortement. Ne nous permettrait-elle pas de prévoir l’altitude maximale, c’est-à-dire la taille de la plus grosse gare traversée ?

Je fais aussi finalement retrouver quelques formules (les plus simples) qui apparaissent via le tableau [5].

Et une élève m’a amené cette semaine, sur une clé, le graphe en arbre circulaire que son grand-frère, en terminale, lui a fait avec Graphviz. Zut, je vais devoir m’y coller...

Le voyage, j’espère, vous aura amusé autant que nous. Je tiens à féliciter mes élèves pour leur investissement et leur assiduité. Venir faire ce qu’ils font pendant la pause méridienne, je trouve ça remarquable. Mais la magie de cet algorithme y est sans doute pour quelque chose.


[1Ce qui consistait alors à détecter les gares N telles que N-1 est dans la table de 3.

[2Voir le commentaire en cellule H6 du doc « voies ferrées ».

[3Il est temps de voir ce document « voie ferrées » pour mieux comprendre.

[4Les colonnes bleutées du doc « tableau des correspondances » en offrent un aperçu.

[5Cela fait penser à ce qui se passe avec le triangle de Pascal, essayez c’est rigolo.


Documents joints

Synthèse
Synthèse
introduction et travaux d’élèves. Mode d’emploi du tableau des correspondances
Visualisation en « voies ferrées »
Visualisation en « voies ferrées »
Première tentative d’organiser un phénomène bien chaotique en apparence. En couleur, les cellules (...)
Tableau des correspondances
Tableau des correspondances
Facile à construire, il permet de visualiser rapidement et pour de très grand nombres, les vols. (...)

Commentaires

lundi 4 juin 2012 à 12h39

c’est super cool monsieur marello

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 22 novembre 2017, 14h-18h, campus du Tampon, amphi 120 D
- Mercredi 7 février 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 7 mars 2018, 14h-18h, campus du Tampon
- Mercredi 4 avril 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 2 mai, 14h-18h, campus du Tampon
- Mardi 5 juin 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 6 juin, 14h-18h, campus du Tampon

Fête de la science

Campus du Moufia, 16 et 17 novembre 2017.
Thème : « La recherche à l’heure du numérique »

Semaine des mathématiques

Du 26 au 31 mars 2018.
Thème : « Mathématiques et mouvement »


Brèves

Comprendre la logique Shadok

dimanche 30 avril

Le meilleur cours de maths Shadok jamais réalisé...
Vidéo succulente ajoutée sur la canal des archives de l’INA le 26 avril 2017.

Décès de Kenneth Arrow

mercredi 15 mars

La vedette de la théorie du choix social, bien connue de nos lecteurs, est décédée récemment, à l’âge respectable de 95 ans.

CHAOS : une aventure mathématique

vendredi 8 mars 2013

CHAOS est un film mathématique constitué de neuf chapitres de treize minutes chacun. Il s’agit d’un film tout public autour des systèmes dynamiques, de l’effet papillon et de la théorie du chaos. Tout comme DIMENSIONS, ce film est diffusé sous une licence Creative Commons et a été produit par Jos Leys, Étienne Ghys et Aurélien Alvarez.

Sur le Web : CHAOS

Rencontres Mondiales Du Logiciel Libre Décentralisées à Saint-Joseph

mardi 28 juin 2011

C’est une manifestation qui aura lieu sur 3 jours, avec de nombreux
ateliers et conférences sur les logiciels libres.
C’est vendredi 1, samedi 2 et dimanche 3 juillet.

C’est une première dans l’île, petite soeur des Rencontres Mondiales du Logiciel Libre nationales qui se déroulent chaque année.

Le site des rencontres réunionnaises se trouve ici :
http://2011.d.rmll.info/

Yves Martin y donnera une conférence d’introduction à la géométrie hyperbolique avec CarMetal, Alain Busser parlera de sa contribution en tant que développeur à CarMetal et Nathalie Carrié présentera un logiciel d’élaboration de connaissances.
De nombreux ateliers vous y attendent : Ruby, Smalltalk, Stellarium, Audacity, Freeplane et d’autres encore...

Il y aura un « repas du libre » le samedi soir, si certains veulent s’y
inscrire en ligne.
Il y aura même une conférence sur l’agriculture libre.

Merci de consulter le programme régulièrement pour plus d’infos.

Médailles Fields 2010

mardi 24 août 2010

Les noms des quatre médaillés Fields 2010 ont été dévoilés lors de la cérémonie d’ouverture du Congrès international des mathématiciens à Hyderabad :

- Elon Lindenstrauss
- Ngô Bào Châu
- Stanislas Smirnov
- Cédric Villani.

Sur le Web : ICM 2010

L’univers de Labomath sur Netvibes

dimanche 23 mai 2010

Quand on aime les maths et qu’en plus on est prof de maths, on ne peut pas passer à côté de cet univers mathématique créé par Kostrzewa Bruno, auteur de l’excellent site personnel Labomath.
Il vous donnera peut-être envie de vous créer votre propre espace sur Netvibes et votre propre univers mathématique.
Allez-voir, c’est hallucinant !
Nathalie Carrié

MathRider : L’outil ultime ?

mardi 24 novembre 2009

MathRider ressemble un peu à Maple (serveur de maths avec calcul formel). Mais il est plus léger (moins de fonctionnalités, on s’y retrouve donc mieux). Et il est conçu pour faire de la programmation...

Cette suite logicielle (dedans il y a 3d-Xplor, GeoGebra, LaTeX etc.) est multiplateforme et les exemples correspondent assez bien au programme actuel du Lycée. Le seul reproche qu’on puisse lui faire est que l’aide est en Anglais (mais de toute façon si on veut programmer on écrit souvent des « for » et des « while »). Le chapitre sur les branchements conditionnels fait appel à un vocabulaire assez original.

Le moteur de calcul formel, MathPiper, est celui qui a été incorporé à GeoGebra.

Le blog du prof geek

lundi 16 novembre 2009

Voici un blog publié sous licence Creative Commons à consommer sans modération pour les enseignants qui utilisent l’outil informatique (et les TICE).

J’ai adoré notamment la vidéo sur le cahier de textes en ligne.

Blog découvert dans le Café pédagogique de ce matin.

Nathalie Carrié

Sur le Web : Le blog du prof geek

Cours vidéo en ligne pour le collège

dimanche 30 août 2009

Philippe Mercier, professeur à Morhange (Moselle), a mis en ligne un cours vidéo couvrant l’ensemble du programme de mathématiques du collège, de la 6e à la 3e. Cet outil pédagogique peut être utile aux collégiens, aux parents d’élèves, aux personnes en formation continue et aux formateurs. Le cours est complété par un forum d’aide en mathématiques.

Un merveilleux travail mathématique et artistique

jeudi 25 juin 2009

Maria Carla Palmeri est professeur de mathématiques dans un collège de Florence (Italie). Cette année, elle a fait utiliser Cabri à ses élèves de 11 ans, une heure par semaine pendant toute l’année. Il en est résulté une magnifique vidéo mettant en scène quelques-unes de leurs constructions et animations : Le Fabuleux Monde de Cabri.

Statistiques

Dernière mise à jour

lundi 20 novembre 2017

Publication

774 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

136 aujourd'hui
1353 hier
2168515 depuis le début
34 visiteurs actuellement connectés