LE COIN DE L'ENSEIGNANT

Introduction
Le but du projet Mathématiques en couleurs est d'aider les étudiants à expérimenter avec un problème mathématique, à comprendre ses difficultés tout en obtenant des solutions partielles. Chacun des cinq jeux traite un problème actuel de recherche en mathématique, informatique et en industrie.

Mathématiques en couleurs transforme ces problèmes en jeux à colorier qui peuvent être présentés aux étudiants de tous les niveaux scolaires de la maternelle à la douxième année secondaire). Chacun des jeux comprend dix pages de cartes ou graphes présentées en niveaux croissant de difficulté. Il est fort recommandé pourtant que les étudiants créent leur propres graphes pour découvrir et mettre à l'épreuve leurs propres idées; des outils sont incorporés au logiciel à cette fin. Ce processus est à la base du raisonnement mathématique et le logiciel a été créé pour aider les étudiants à développer cette habileté.


Détails sur les jeux
Vous trouverez probablement utile d'imprimer cette page et de l'utiliser comme ressource durant une activité de classe.

Dans tous les jeux, des bannières apparaîtront pour donner des informations appropriées aux étudiants.

Dans les quatres jeux traitant des graphes, il existe une limitation sur le genre de graphe qui puisse être dessiné. D'abord, le nombre de sommets est limité par la grandeur de l'écran. Mais aussi, si trois sommets sont alignés, le premier et troisième sommets ne peuvent pas être reliés par une arête. Cette possibilité a été sacrifiée afin d'assurer plutôt une présentation claire du graphe, laissant quand même une grande variété pour analyser le problème.




Les cartes en quatre couleurs

Ce jeu est basé sur le "Théorème des quatre couleurs", qui affirme que quatre couleurs suffisent toujours afin de colorier une carte de sorte que les régions ayant une frontière commune reçoivent des couleurs différentes. Le but de ce jeu n'est pas de démontrer ce fait, mais plutôt de jouer avec l'idée, de dessiner des cartes et de les colorier avec le plus petit nombre possible de couleurs. Parfois, deux ou trois couleurs suffisent, mais en général quatre couleurs sont nécessaires. Réussir en quatre couleurs n'est pas aussi facile qu'on puisse le croire et on a donc inclus six couleurs donnant à tout le monde une chance de colorier leur carte correctement. Les plus aventureux réduiront ce nombre à cinq, et même encore mieux à quatre.

Après avoir complété une carte, un message demandera à l'étudiant de réduire le nombre de couleurs si possible ou alors, ce qui est aussi difficile mais important, de montrer que le nombre de couleurs utilisées est aussi petit que possible. Les étudiants plus avancés, par exemple, devraient réussir à montrer que deux ou trois couleurs ne suffisent pas en général pour colorier une carte.

Les cartes incluses commencent avec des dessins très simples pour les jeunes, ensuite on trouvera des dessins mathématiques plus abstraits, et une troisième page comprend des cartes "traditionnelles" y compris le Canada, les É.U., l'Europe, l'Afrique, l'Amérique du Sud et l'Asie. Les sept pages suivantes comprennent des dessins de plus en plus complexes. Tout au long du travail, les étudiants peuvent sauver leur cartes dans l'espace de droite, et peuvent aussi leur donner un titre.

L'ordinateur avertira l'étudiant aussitôt que deux régions reçoivent la même couleur et lorsque leur carte est complète en annonçant le nombre de couleurs utilisées. Dépendant de la complexité de la carte, cela peut prendre quelques secondes à l'ordinateur et un message apparaîtra au haut de l'écran pour informer l'étudiant. Cette vérification est intentionnellement souple et même vague de façon à empêcher l'ordinateur de devenir trop pointilleux et d'accorder des frontières très petites. Par exemple, deux régions ayant seulement un coin en commun ne seront pas considérées comme avoisinantes. Lorsque la carte est complétée, un message approprié et adapté au niveau de difficulté informera l'étudiant de ses prouesses.

Voici un échantillon de questions pour amorcer une discussion avec un étudiant curieux:

  1. Peux-tu reconnaître une carte qui ne demande que deux couleurs?
  2. Peux-tu reconnaître une carte qui ne demande que trois couleurs?
  3. Peux-tu reconnaître une carte qui demande au moins quatre couleurs?
  4. As-tu découvert une bonne méthode pour colorier une carte avec seulement six, cinq, quatre couleurs?
  5. Peux-tu exprimer ta méthode sous forme d'algorithme?



Le nombre chromatique d'un graphe

L'objet de ce jeu est de colorier les sommets d'un graphe avec le plus petit nombre possible de couleurs, de sorte que deux sommets reliés par une arête reçoivent des couleurs différentes. Ce plus petit nombre est appelé le nombre chromatique du graphe.

Soulignons une fois de plus que le but de chaque jeu de la série est d'aider l'étudiant à développer leur approche scientifique et expérimentale envers les problèmes mathématiques, comprendre les difficultés du problème et obtenir des solutions partielles. Dans le cas du problème de calculer le nombre chromatique d'un graphe (et de même que pour tous les problèmes suivants), aucun algorithme efficace n'a été découvert jusqu'à maintenant! Trouver ce nombre demeure un problème extrêmement difficile même pour les plus puissants ordinateurs. Le logiciel inclut un algorithme très simple, mais faire partie nulle avec l'ordinateur est quand même un excellent résultat et il est toujours possible de le battre! L'étudiant est en effet encouragé à tenter de faire mieux que l'ordinateur, car c'est ici que l'étudiant devra créer des méthodes d'analyse si importantes en mathématiques.

L'ordinateur vérifiera après chaque coloriage si deux sommets reliés par une arête ont reçu la même couleur et informera l'étudiant. Lorsque le graphe est complété, l'ordinateur comptera le nombre de couleurs et utilisera son simple algorithme pour essayer de faire mieux et finalement annoncera les résultats.

Voici un échantillon de questions pour amorcer une discussion avec un étudiant curieux:

  1. Peux-tu reconnaître un graphe qui ne demande que deux couleurs?
  2. Peux-tu reconnaître un graphe qui demande au moins 5 couleurs? 11?
  3. As-tu découvert une bonne méthode pour colorier ton graphe? Une méthode rapide?
  4. Peux-tu deviner comment l'algorithme de l'ordinateur fonctionne?
  5. Peux-tu faire toujours aussi bien que l'algorithme de l'ordinateur? Créer ton propre algorithme?



Le nombre arête-chromatique d'un graphe

Ce jeu est semblable au précédent mais il faut ici colorier les arêtes du graphes de sorte que deux arêtes jointes au même sommet doivent recevoir des couleurs différentes. Le plus petit nombre possible de couleurs requises pour colorier un graphe de la sorte est appelé le nombre arête-chromatique du graphe.

Les commentaires de l'ordinateur seront aussi très semblables. Par exemple, l'ordinateur informera l'étudiant si deux arêtes jointes au même sommet ont reçu la même couleur. Lorsque toutes les arêtes du graphe sont complètement coloriées, l'ordinateur comptera les couleurs utilisées et tentera de faire mieux; des informations adaptées au niveau de difficulté seront affichées.

Il est quand même facile ici de tracer un graphe qui demandera plus de dix couleurs, bien que seulement dix couleurs soient disponibles en tant que provisions raisonnables. Par exemple, si onze arêtes sont reliées au même sommet, il faudra alors au moins onze couleurs. Pourtant, dix couleurs laissent assez de liberté pour créer des graphes d'assez grande complexité.

Voici un échantillon de questions pour amorcer une discussion avec un étudiant curieux:

  1. Peux-tu reconnaître un graphe qui ne demande que deux couleurs?
  2. Peux-tu tracer un graphe qui demande au moins 11 couleurs? 55?
  3. As-tu découvert une bonne méthode pour colorier ton graphe? Une méthode rapide?
  4. Peux-tu deviner comment l'algorithme de l'ordinateur fonctionne?
  5. Peux-tu faire toujours aussi bien que l'ordinateur? Créer ton propre algorithme?
  6. Est-ce que "Le Nombre Chromatique d'un Graphe" et "Le Nombre Arête-Chromatique d'un Graphe" sont vraiment le même problème? Est-ce qu'un algorithme pour un de ces problèmes pourrait servir à résoudre l'autre?



Le nombre chromatique à deux joueurs d'un graphe

Comme pour le simple nombre chromatique, l'objet de ce jeu est de colorier les sommets d'un graphe avec le plus petit nombre possible de couleurs, de sorte que deux sommets reliés par une arête reçoivent des couleurs différentes. Par contre ici on choisit d'avance le nombre maximum de couleurs permises et on colorie les sommets alternativement avec un autre joueur, ici l'ordinateur. En pratique, l'autre joueur essaie de forcer le plus de couleurs possible; il faut alors être habile pour minimiser ce nombre. Le plus petit nombre possible de couleurs qui permettent quand même au premier joueur de toujours gagner est appelé le nombre chromatique à deux joueurs du graphe. Ce nombre est au moins aussi grand que le nombre chromatique du graphe, et souvent beaucoup plus grand.

L'ordinateur demande d'abord de sélectionner le nombre maximum de couleurs permises. Ensuite, l'étudiant commence à colorier le graphe tour à tour avec l'ordinateur. L'ordinateur vérifiera après chaque coloriage si deux sommets reliés par une arête ont reçu la même couleur et informera l'étudiant. C'est alors à l'ordinateur de jouer et celui-ci tentera de forcer un plus grand nombre de couleurs. L'étudiant qui réussit à colorier tous les sommets avec le nombre de couleurs étable au départ gagne la partie, sinon c'est l'ordinateur qui gagne. Le but est donc d'établir au départ le plus petit nombre possible de couleurs qui laisse au premier joueur assez de loisir pour toujours gagner, quelque soit l'adversaire.

Voici un échantillon de questions pour amorcer une discussion avec un étudiant curieux:

  1. Peux-tu reconnaître les graphes qui ne demandent que deux couleurs? Trois couleurs?
  2. Peux-tu reconnaître un graphe qui demande au moins 5 couleurs? 11?
  3. As-tu découvert une bonne méthode pour colorier ton graphe? Une méthode rapide?
  4. Peux-tu deviner comment l'algorithme de l'ordinateur fonctionne?
  5. Peux-tu faire toujours aussi bien que l'ordinateur? Créer ton propre algorithme?
  6. Quel est le lien entre le nombre chromatique et le nombre chromatique à deux joueurs?



Le nombre dominant d'un graphe

L'objet de ce jeu est d'utiliser une seule couleur pour sélectionner certains sommets de sorte que chaque sommet du graphe soit ou colorié ou alors relié par une arête à un sommet colorié; les sommets coloriés forment ce qu'on appele un ensemble dominant. Le but du jeu est de trouver un ensemble dominant contenant le plus petit nombre de sommets possible.

L'ordinateur informera l'étudiant seulement lorsqu'un ensemble dominant aura été sélectionné; en effet il n'y a dans ce jeu aucune limite sur les sommets qui puissent être coloriés. L'ordinateur comptera le nombre de sommets de l'ensemble dominant et tentera encore une fois de faire mieux en utilisant son propre algorithme. L'étidiant recevra alors des messages adaptés au niveau de difficulté. Il est bien sûr possible de battre l'ordinateur et l'étudiant est encouragé à tracer un graphe qui réussira!

Voici un échantillon de questions pour amorcer une discussion avec un étudiant curieux:

  1. Peux-tu tracer un graphe avec un ensemble dominant à un seul sommet? Exactement deux sommets?
  2. Peux-tu tracer un graphe qui demande nécessairement un ensemble dominant avec beaucoup de sommets?
  3. As-tu trouvé une bonne méthode pour obtenir un petit ensemble dominant?
  4. Peux-tu deviner comment l'algorithme de l'ordinateur fonctionne?
  5. Peux-tu faire toujours aussi bien que l'ordinateur? Créer ton propre algorithme?


Terminologie

Carte
On connait tous la notion familière de carte géographique. Ici, on utilise la notion de carte plus généralement pour indiquer toutes régions qui peuvent être tracées, et frontière ou bordure signifie toute courbe commune.

Le "théorème des quatre couleurs"
Il a fallu plus de cent ans aux mathématiciens pour démontrer que quatre couleurs suffisent toujours pour colorier une carte de sorte que deux régions ayant une frontière commune reçoivent des couleurs différentes. Cela a en effet été vérifié, ou prouvé comme l'on dit en mathématiques, par K. Appel et W. Haken en 1976 utilisant l'ordinateur substantiellement pour classifier des milliers de configurations. Un compte rendu intéressant de leur succès est disponible dans le magazine scientifique populaire "Scientific American", Octobre 1977.

Graphe
Un graphe est un paquet de cercles, que l'on appele "sommets", dont certains d'entre eux sont reliés par des droites (ou courbes) que l'on appele "arêtes".

Nombre chromatique d'un graphe
Le plus petit nombre possible de couleurs requises pour colorier les sommets d'un graphe de sorte que deux sommets reliés par une arête reçoivent des couleurs différentes.

Nombre arête-chromatique d'un graphe
Le plus petit nombre possible de couleurs requises pour colorier les arêtes d'un graphe de sorte que deux arêtes attachées à un même sommet reçoivent des couleurs différentes.

Nombre chromatique à deux joueurs d'un graphe
Le plus petit nombre possible de couleurs requises pour colorier, alternativement avec tout autre joueur, les sommets d'un graphe de sorte que deux sommets reliés par une arête reçoivent des couleurs différentes. Ce nombre est au moins aussi grand que le simple nombre chromatique du graphe, et souvent beaucoup plus grand, n'est-ce pas?

Ensemble dominant d'un graphe
Une collection de sommets d'un graphe de sorte que chaque sommet soit ou bien dans la collection, ou alors relié par une arête à un sommet de la collection.

Nombre dominant d'un graphe
Le plus petit nombre possible de sommets d'un ensemble dominant du graphe. Dans notre jeu, on sélectionne un ensemble dominant en coloriant ses sommets bleu.


MATHÉMATIQUES EN COULEURS

PERSPECTIVE

EST-CE VRAIMENT DES MATHS?

LES JEUX

AUTRES SITES D'INTERET