L’article étudie un algorithme de déplacements dans une grille carrée $ 3 \times 3$ Rien à voir avec un barbecue mathématique !
Introduction
Un titre qui interpelle sans nul doute, mais rien à voir avec un barbecue mathématique ! Ce brasero va nous conduire à étudier un algorithme de déplacements dans une grille carrée $ 3 \times 3$. D’où vient une telle idée ? Pourquoi passer du temps à comprendre comment se déplacer dans une telle grille ? In fine, quelle est la genèse de cet article ? Parce qu’à partir d’un seul problème, on se rend vite compte que les mathématiques s’y rattachant sont d’une richesse incomparable et source d’applications utilisant le numérique avec nos élèves. Vous êtes prêts ? 3, 2, 1… grillé !
Tout débute il y a quelques années avec la découverte de la distance de Manhattan. Inspirée par Minkowski, cette distance ou taxi-distance est la distance parcourue par un taxi dans les rues de Manhattan quand la ville est formée d’un réseau de rues en forme de quadrillage (comme à New York justement).
Voici l’algorithme de déplacement que nous utiliserons durant tout cet article :
Sont autorisés les seuls déplacements suivants :
- vers la droite ;
- vers le bas.
La distance de Manhattan est la longueur du chemin respectant cet algorithme. Un exemple est proposé ci-contre.
1er objectif : que peut-on dire de cette distance de Manhattan ?
Focalisons-nous sur des grilles carrées simples.
Étude de l’algorithme
Cette étude peut être une 1re activité de découverte pour les élèves dès le cycle 3.
Voici un énoncé possible :
On se déplace du départ D à l’arrivée A en utilisant les seuls déplacements suivants : à droite et vers le bas.
Ce qui donne pour un carré $ 3 \times 3$ :
- Donner tous les déplacements possibles dans un carré $ 2 \times 2$ avec cette règle. Combien y en a-t-il ?
Vous pourrez utiliser les carrés donnés en annexe.
- Donner tous les déplacements possibles pour un carré $ 3 \times 3$.
Combien y en a-t-il ?
Vous pourrez utiliser les carrés donnés en annexe.
- Pour les deux questions précédentes, quelle est la longueur du chemin permettant d’aller de D à A ? Que peut-on remarquer ?
- Sans le démontrer, pourriez-vous donner la longueur d’un déplacement dans un carré $ 4 \times 4$ ? $ 5 \times 5$ ?
- Compléter le tableau ci-dessous :
Côté du carré 2 3 4 5 6 Longueur du déplacement Est-ce un tableau de proportionnalité ? Expliquer.
Voici maintenant une correction de cette activité :
- Dans un carré $ 2 \times 2$ , il y a 6 déplacements possibles :
- Dans un carré $ 3 \times 3$, il y a 20 déplacements possibles :
- Il suffit de faire les symétriques de ces 10 déplacements par rapport à la diagonale [AD].
- Pour les carrés $ 2 \times 2$, la longueur du déplacement est 4 carreaux.
Pour les carrés $ 3 \times 3$, la longueur du déplacement est 6 carreaux.
On remarque que c’est la moitié du périmètre du carré.
- Pour un carré 4x4, on a donc $ \frac{4 \times 4}{2}=8$ carreaux.
Pour un carré 5x5, on a donc $ \frac{4 \times 5}{2}=10$ carreaux.
Au cycle 4, on fait conjecturer que la longueur d’un chemin dans une grille carrée $n \times n$ est $2n$ car il y a $n$ déplacements vers le droite et autant vers le bas pour chaque chemin.
- Il y a proportionnalité, car le coefficient est évident : c’est 2.
Côté du carré 2 3 4 5 6 Longueur du déplacement 4 6 8 10 12
Conclusion : Le déplacement vaut toujours le demi-périmètre du carré !
Faire émerger une conjecture aux élèves à l’issue de cette 1re activité est un bel objectif à atteindre, valorisant ainsi la démarche expérimentale des mathématiques ainsi que la démarche essai-erreur.
Un 2e objectif peut être la programmation de tels déplacements. Le logiciel scratch semble être approprié pour ce script que voici (fichier ZIP à télécharger ci-contre, à consulter en ligne ou à tester ci-dessous).
Détails du programme :
- Bloc construisant la grille carrée de la dimension souhaitée par l’utilisateur (variable number1) :
- Blocs construisant les colonnes et le lignes de la grille carrée :
- Le programme principal (le côté de la grille est demandé à l’utilisateur ; les déplacements vers la droite ou vers le bas sont effectués aléatoirement avec une probabilité $ \frac{1}{2}$ pour chacun) :
La taille de la grille carrée est demandée à l’utilisateur et le script propose un chemin aléatoire respectant l’algorithme sus-cité. Voici quelques exemples :
À travers ce programme, les élèves peuvent ainsi vérifier tous les différents chemins possibles dans une grille carrée $ n \times n$.
Plusieurs questions restent en suspens et méritent d’être posées aux élèves suite à cette vérification :
- La symétrie par rapport à la 1re diagonale évite de dessiner tous les chemins. Cette méthode permet-elle d’obtenir tous les chemins possibles ?
- Que se passe-t-il si on regarde la symétrie par rapport à la 2e diagonale ?
Mathémagie #1
Introduction : L’enjeu de ce tour est de prédire le résultat final d’un algorithme de déplacement dans une grille carrée $ 3 \times 3$ en connaissant juste le nombre de départ du spectateur ! De nombreuses variantes sont possibles en respectant certaines contraintes. Dès le cycle 2.
Matériel : La grille carrée $ 3 \times 3$ en annexe et de quoi écrire.
Déroulement du tour : Le magicien demande à un spectateur de choisir un nombre entre 1 et 10 et de l’écrire dans la case en haut à gauche de la grille carrée.
Deux déplacements sont possibles dans cette grille :
- de la gauche vers la droite en multipliant par 6 ;
- du haut vers le bas en multipliant par 5.
Le spectateur choisit un chemin dans cette grille via ces deux déplacements afin d’arriver dans la case en bas à droite. Il complète les cases de la grille suivant son chemin en effectuant les calculs sans montrer la grille au magicien :
Le magicien devine alors aisément le résultat final : 6300 ! Et cela quel que soit le chemin emprunté par le spectateur...
Explication : Tout repose sur l’algorithme proposé et les opérations choisies !
Lemme 1 : Tous les chemins d’une grille $ 3 \times 3$ sont équivalents et sont constitués de deux déplacements vers la droite et de deux déplacements vers le bas.
Lemme 2 : Le nombre d’arrivée vaut 900 fois celui de départ.
En effet, si n est le nombre de départ :
- avec 2 déplacements vers la droite : $ n \times 6 \times 6 = n \times 6^2 = 36n $ ;
- avec 2 déplacements vers le bas : $ n \times 5 \times 5 = n \times 5^2 = 25n $ ;
- finalement avec les 4 déplacements : $ 5^2 \times 6^2 \times 2 = 30^2 \times n = 900n $.
Astuce du magicien : Il multiplie le nombre de départ par 900
➔ $7 \times 900 = 6300 $
➔ de quoi réviser la table du 9 !
Variantes : On peut adapter cette grille carrée en respectant la contrainte suivante : les deux opérations correspondant aux deux déplacements doivent avoir le même degré de priorité !
Exemples :
- multiplication par 4 et division par 2 ;
- addition par 5 et soustraction par 3.
On peut ainsi obtenir l’astuce du magicien sans souci suivant les notions que l’on souhaite aborder avec les élèves.
Avec des fractions :
 |
Dans ce cas, l’astuce du magicien est de multiplier le nombre de départ par 4 car les déplacements conduisent aux multiplications : $ \frac{3}{2} \times \frac{3}{2} \times \frac{4}{3} \times \frac{4}{3} \times = \frac{9}{4} \times \frac{16}{9} = 4 $ |
ANNEXE – LA GRILLE $ 3 \times 3$
Compléments
Combien existe-t-il de déplacements dans une grille carrée $ n \times n$ ? L’association Maths en jeans propose de tels défis aux différents ateliers insérés dans les établissements.
Le nombre de chemins possibles dans une grille carrée $ n \times n$ est le coefficient binomial ${2n}\choose{2}$.
Exemples :
- pour n=2, il y a ${{4}\choose{2}} = 6$ chemins possibles. Ce qui correspond au tour de mathémagie ci-dessus.
- pour n=3, il y en a ${{6}\choose{3}} = 20$.
Pour aller plus loin, on peut également s’intéresser à un algorithme autorisant le déplacement en diagonale. Les nombres de DELANNOY répondent à ce problème encore plus riche. On peut consulter à ce titre, l’excellent et incontournable site de Gérard Villemin.
Enjeux didactiques
En introduction, la question de l’intérêt d’une telle activité a été posée. Il est temps d’explorer un scénario pédagogique possible pour mettre en place dans nos classes cette thématique. Ingénieur pédagogique, tel est le rôle d’un enseignant au quotidien. À travers la lecture rigoureuse des programmes en vigueur, le professeur réfléchit en amont aux points suivants :
1. À quel niveau va-t-on proposer cette activité ?
Du primaire au lycée, Algo’ grillo est adaptable. Tout dépend des objectifs visés. Il faut évidemment se recentrer sur les 6 compétences mathématiques. Chercher en est une primordiale, quel que soit le niveau visé ! La seule manière d’apprendre les mathématiques est de faire des mathématiques par soi-même. Se confronter à la démarche expérimentale à travers la recherche de différents chemins possibles est une expérience à faire vivre à nos élèves. Essais, erreurs parsèment naturellement cette phase de recherche. Une mise en commun in extenso favorise une 2e compétence : communiquer !
Par exemple, au cycle 3, on fait conjecturer que la longueur d’un chemin est constante et vaut le demi-périmètre du carré. Au cycle 4, le calcul littéral prolonge l’activité par une démonstration plus formelle du résultat.
2. Quels sont les prérequis pour les élèves ?
De manière identique, tout dépend du niveau de classe. En primaire, le périmètre d’un carré semble être un prérequis louable, au début du cycle 4, les rudiments du calcul littéral une nécessité.
3. Quel scénario préparer pour atteindre les objectifs visés ?
Cette activité a été testée en classe de 6e dans l’ordre mentionné ci-dessus. Une recherche individuelle des chemins puis une mise en commun suivies d’une vérification via le programme scratch. La connexion avec le tour de mathémagie s’effectue comme une application concrète des différents chemins possibles.
Prolongements
Construire d’autres grilles est une belle piste à explorer avec les élèves et adaptable au niveau et à la notion souhaitée. Par exemple, au cœur du cycle 4, les fractions demeurent un enjeu de taille. Remplir une telle grille permet l’entrainement essentiel aux automatismes sur une règle comme l’addition de fractions. On peut, à ce propos, demander aux élèves ce qu’il se passe si on va en diagonale c’est-à-dire :
Afin d’aller plus loin, on peut utiliser le calcul littéral au lycée pour mener un projet de réflexion autour du problème suivant :
La grille de droite s’obtient en ajoutant $ \frac{1}{p}$ vers la droite et $ \frac{1}{q}$ vers le bas de sorte qu’en diagonale, on ajoute $ \frac{p+q}{pq}$. On supposera $ p $ < $ q $.
Exemple 1 :
Avec $p=2 $ et $q=6 $, on obtient la grille de gauche avec $ \frac{1}{6}$ comme 1er nombre en haut à gauche de la grille.
Exemple 2 :
Avec $p=5 $ et $q=7 $, on obtient $\frac{1}{pq} =\frac{1}{35} $. Pour obtenir le nombre en bas à droite, la grille nous donne la formule à appliquer :
Ce qui nous conduit au problème suivant :
« Quelles sont les conditions sur $p$ et $q$ pour que la fraction en bas à droite soit $\frac{p}{q}$ sachant que le nombre de départ en haut à gauche est $\frac{1}{pq}$ ? »
Autrement dit : $\frac{2p+2q+1}{pq} =\frac{p}{q} $ soit $p$ divise $2p+2q+1$ donc $p$ divise $2q+1$.
Ainsi il existe $k$ entier tel que $2q+1=pk$ d’où $2p+2q+1=2p+kp=(2+k)p$.
Conditions :
$ p $ < $ q $ impairs tous les deux avec $2q+1=p(p-2)$ soit $q=\frac{p(p-2)-1}{2}$.
Le tableau suivant donne les premières fractions répondant au problème :
On peut faire remarquer que $2p+2q+1$ est toujours un carré. Pouquoi ? De quoi explorer encore ce type de grille sans relâche… ! Il ne reste plus qu’à transformer ce dernier résultat en tour de mathémagie… Place aux lectrices et lecteurs de MathémaTICE !