• Accueil
  • À propos
  • Accrom\(\alpha\)th en PDF
  • Commanditaires
  • Contact
  • Contributions des lecteurs
  • Sites amis

Logo

À qui appartient le zèbre?

Par Denis Lavigne
Volume 3.2 - été-automne 2008

La modélisation mathématique d’une énigme permet l’utilisation de l’ordinateur dans la recherche efficace d’une solution.

Lorsque j’étais au primaire, mon frère, de onze ans mon aîné, me proposait parfois une énigme qui faisait intervenir, neuf fois sur dix, une maison bleue. Avec des indices comme: le Norvégien habite à côté, le violoniste boit du jus d’orange, le sculpteur élève des escargots, il fallait découvrir à qui appartenait le zèbre.

Une enseignante m’a fait parvenir l’énigme suivante qu’elle a proposée à ses élèves de sixième année que, semble-t-il, seul un adulte sur dix est capable de résoudre. Amis détectives, voici votre défi du jour!

Énigme

Cinq maisons alignées et de couleurs différentes sont habitées par des hommes de nationalités et de professions différentes. Chacun a une boisson préférée et un animal domestique différent des autres. Voici les indices dont vous disposez:


1. Une personne du groupe préfère boire de l’eau.
2. L’Anglais habite la maison rouge.
3. Le chien appartient à l’Espagnol.
4. On boit du café dans la maison verte.
5. L’Ukrainien boit du thé.
6. La maison verte est située immédiatement à droite de la blanche.
7. Le sculpteur élève des escargots.
8. Le diplomate habite la maison jaune.
9. On boit du lait dans la maison du milieu.
10. Le Norvégien habite la première maison à gauche.
11. Le médecin habite la maison voisine de celle où habite le propriétaire du renard.
12. La maison du diplomate est voisine de celle où il y a un cheval.
13. Le violoniste boit du jus d’orange.
14. Le Japonais est acrobate.
15. Le Norvégien habite à côté de la maison bleue.

Et la question, bien sûr: à qui appartient le zèbre?

Avant de poursuivre la lecture, je vous invite à prendre une pause et à jouer le jeu en complétant le tableau ci-dessous.
zebre_img1

Pour résoudre l’énigme, il faut remplir chacune des cases en considérant les ensembles utilisés dans l’énoncé de l’énigme. Ce sont:

a) Les couleurs:
blanche, rouge, jaune, verte, bleue

b) Les professions:
violoniste, acrobate, sculpteur, médecin, diplomate

c) Les nationalités:
Anglais, Ukrainien, Japonais, Espagnol, Norvégien

d) Les animaux:
chien, escargots, cheval, renard, zèbre

e) Les boissons:
eau, jus, thé, lait, café

f) Le rang, de gauche à droite:
1, 2, 3, 4, 5.

Puisque le troisième indice indique que le chien appartient à l’Espagnol, on ne peut pas avoir dans le tableau une ligne sur laquelle serait écrite la combinaison:

Jaune-Diplomate-Anglais-Chien-Jus-5

C’est une combinaison fausse car elle ne respecte pas un des indices. Cependant, la combinaison:

Bleue-Médecin-Ukrainien-Cheval-Thé-2

est vraie car elle ne contrevient à aucun des indices.

Il existe évidemment une quantité impressionnante de combinaisons (au fait, savez-vous combien?) et, pour chacune, le défi consiste à déterminer si elle est vraie ou fausse. Si les indices sont cohérents, il doit y avoir au moins cinq combinaisons gagnantes (c’est-à-dire vraies) telle que, par exemple, la seconde des deux mentionnées ci-dessus.

La question est maintenant de déterminer cinq combinaisons, parmi toutes celles possibles, qui respectent chacun des indices.

zebre_img2

Véracité d’une combinaison

Ce sont les indices qui permettent de déterminer la véracité d’une combinaison. Par exemple, à lui seul, le huitième indice (le diplomate habite la maison jaune) permet de conclure à la fausseté de plusieurs combinaisons. En voici quelques-unes:

Jaune-acrobate-Japonais-cheval-eau-1
Jaune-sculpteur-Japonais-chien-jus-1
Rouge-diplomate-Anglais-renard-eau-2
Bleue-diplomate-Anglais-zèbre-thé-2

Il peut s’avérer difficile de bien noter toutes les conséquences liées à un indice particulier ou à un groupe d’indices donnés. Heureuse- ment qu’il ne s’agit pas d’une énigme faisant intervenir une centaine de maisons! L’énigme, chers enquêteurs, peut être résolue sans l’aide de mathématiques savantes. Toutefois, il existe un outil formidable, élégant et puissant, qui permet de résoudre ce genre de problème: la modélisation mathématique! Jumelée aux performances remarquables de l’informatique et aux progrès fulgurants des méthodes de résolution développées par des chercheurs en mathématiques appliquées et en recherche opérationnelle (RO), voilà une stratégie efficace qui permet de résoudre des problèmes d’une complexité inouïe.

La modélisation mathématique consiste à étudier un problème décrit dans le langage ordinaire pour le formuler en un problème décrit par des symboles mathématiques. Le défi consiste ensuite à communiquer ce modèle mathématique à un logiciel spécialisé capable de le comprendre et de le résoudre. Ces tâches peuvent être difficiles. Le résultat, lui, est toujours spectaculaire!

Le calendrier d’activités, une énigme

Pouvez-vous imaginer la difficulté de produire un horaire acceptable pour le calendrier régulier de la Ligue Nationale de Hockey1? Pensez aux milliers d’indices plus précis les uns que les autres:

  • Le Centre Bell n’est pas disponible le 23 janvier puisqu’il y a un concert de Christina Aguilera ce soir-là.
  • Le Canadien doit jouer huit parties contre les Bruins de Boston, dont quatre à domicile au cours de la saison.

Ou encore, pouvez-vous imaginer la création d’un horaire des vols de la flotte d’appareils d’Air Canada pour la semaine qui vient2?

  • Le Boeing 737 numéro 8 de la compagnie doit quitter Toronto et passer par Montréal avant d’aller vers Paris mardi.
  • Ce même avion sera donc disponible à Paris pour revenir en ligne directe vers Québec mercredi.
  • Il ne faut pas oublier qu’un avion est contraint de subir un entretien après un certain nombre d’heures de vols.

Pas de doute, nous avons besoin de méthodes efficaces! Modélisation mathématique3, peux-tu m’aider?

En mathématiques, la lettre x est souvent utilisée pour représenter un élément inconnu. Par exemple, la véracité d’une combinaison donnée pourrait être notée x. Ainsi, la combinaison:

Bleue-médecin-Ukrainien-cheval-thé-2

pourrait dorénavant être connue sous le simple nom x. Cette combinaison, comme toutes les autres, peut être soit vraie, soit fausse. Il n’y a aucune autre possibilité. On dit alors que le résultat est binaire (« bi » pour « deux » et « naire » pour « nombre »). Il est fréquent en mathématiques d’associer des nombres aux mots « Vrai » et « Faux ».

Chaque fois qu’une combinaison est vraie, sa valeur est 1. Si elle est fausse, sa valeur est 0. On a nécessairement l’une ou l’autre des deux possibilités suivantes : x = 1 ou x = 0. On dit que x est une variable puisque sa valeur, au départ, est inconnue et peut varier. On dit aussi que x est ici une variable binaire puisqu’elle ne peut prendre que les valeurs 1 ou 0.

On pourrait ainsi associer une lettre à chacune des combinaisons possibles. Nous avons déjà mentionné qu’il y a une multitude de ces combinaisons. Les lettres de l’alphabet sont vite épuisées et il faut utiliser une notation cohérente. Par exemple, je choisis de représenter la combinaison:

Bleue-médecin-Ukrainien-cheval-thé-2

par la variable.

Dans un logiciel spécialisé tel MPL, (Mathematical Programming Language, de l’entreprise Maximal Software (www.maximalsoftware.com)), c'est ainsi qu'on écrit une variable.

Dans un logiciel spécialisé tel MPL, (Mathematical Programming Language, de l’entreprise Maximal Software (www.maximalsoftware.com), c’est ainsi qu’on écrit une variable.

La chasse aux indices!

Nous sommes maintenant prêts à effectuer la modélisation mathématique de notre énigme. Chaque indice mentionne un fait à respecter. La solution finale doit satisfaire chacun de ces indices. Ces derniers nous sont imposés. Nous sommes contraints à les respecter. C’est à cause de cela que les indices sont appelés, en modélisation mathématique, des contraintes.

Il y a tout d’abord des indices qui ne sont pas explicitement donnés mais qui sont sous- entendus dans la définition même de l’énigme. Par exemple, dans la solution finale, exactement une combinaison ayant l’indice couleur égal à Bleue doit être vraie. En effet, quelqu’un doit habiter cette maison. Il s’agit d’une seule personne. Initialement, on ne connaît rien du propriétaire de cette maison, mais on sait qu’une seule personne doit y habiter puisqu’il y a cinq personnes et cinq maisons. Ainsi, parmi toutes les combinaisons ayant la couleur Bleue, une seule est vraie et donc égale à 1. Toutes les autres valent 0. La somme de toutes les combinaisons de couleur Bleue est donc 1. Ceci signifie que dès qu’une combinaison est égale à 1, un nombre important d’autres combinaisons valent 0 et sont du même coup éliminées. Les énoncés suivants sont équivalents et mènent à la représentation mathématique de cette contrainte pour la couleur Bleue:


La somme de toutes les combinaisons ayant la couleur Bleue est 1.
La somme des:

xCouleurProfessionNationalitéAnimalBoissonRang

où couleur = Bleue est 1.
Somme(Profession, Nationalité, Animal, Boisson, Rang:

xCouleurProfessionNationalitéAnimalBoissonRang)=1

où Couleur = Bleue.

Il y a une contrainte de ce type pour chacune des couleurs. Il y a donc 5 contraintes similaires (une pour chaque couleur). Dans ce cas, l’égalité précédente est plutôt écrite de la façon suivante qui résume ces 5 contraintes:


Somme(Profession, Nationalité, Animal, Boisson, Rang:

xCouleurProfessionNationalitéAnimalBoissonRang)=1

où Couleur = Blanche, Rouge, Jaune, Verte, Bleue.

Ce raisonnement mène à des contraintes similaires pour la profession, la nationalité, l’animal, la boisson et le rang.

Je ne mentionne qu’une autre représentation mathématique, soit celle du huitième indice: le diplomate habite la maison jaune. Ceci signifie que parmi toutes les combinaisons possibles, la solution finale en choisira exactement une seule qui propose que le diplomate habite cette maison. Toutes les autres sont alors nulles. La modélisation mathématique suivante représente ce fait:


Somme(Nationalité, Animal, Boisson, Rang:

xCouleurProfessionNationalitéAnimalBoissonRang)=1

où Couleur = Jaune et Profession = Diplomate.

Plusieurs autres indices sont représentés par des contraintes similaires à celles présentées ci-dessus. D’autres, telle que la contrainte 12, exige toutefois une certaine expérience de la modélisation mathématique.

zebre_img4

De la parole aux actes

C’est de cette façon que l’on parvient à obtenir une modélisation mathématique offrant une représentation adéquate de la réalité. Toutefois, bien que le modèle complet puisse tenir sur une ou deux feuilles de papier, comment doit-on s’y prendre pour communiquer un tel regroupement d’équations mathématiques à un logiciel spécialisé capable de le résoudre?

C’est ici qu’intervient l’utilité d’un langage de programmation algébrique. Il en existe plusieurs et je vous propose un exemple utilisant le logiciel MPL de l’entreprise Maximal Software. Ce logiciel permet de représenter, au sein d’un ordinateur, un modèle mathématique sur papier comme celui que nous avons développé jusqu’à présent. Une partie du modèle vous est présentée dans cet article.

La solution complète, trouvée en une seconde, vous est présentée ci-dessous. Notez aussi que MPL ne résout pas le problème. Il fait plutôt appel à un logiciel spécialisé d’optimisation (ici CPLEX de l’entreprise ILOG5).

Ah oui, j’oubliais: le zèbre
appartient à l’acrobate!

zebre_img5

PDF

  1. GIRO, à Montréal, attaque ce genre de problème de création d’horaire pour les sociétés de transports publics (www.giro.ca). ↩
  2. La suite AD OPT, développée à Montréal, permet de résoudre des problèmes de ce type (www.kronos.com/AD-OPT). ↩
  3. Ces problèmes sont traités dans la branche des mathématiques appelée « recherche opérationnelle ». ↩
  • ● Version PDF
Partagez
  • tweet

Tags: Applications des mathématiques

Articles récents

  • Le mouvement brownien : Du pollen de Brown à l’origine de la finance moderne

    Michel Adès, Matthieu Dufour, Steven Lu et Serge Provost
  • Le problème des \(N\) corps

    Christiane Rousseau
  • Comprendre la structure des nombres premiers

    Andrew Granville

Sur le même sujet

  • Le mouvement brownien : Du pollen de Brown à l’origine de la finance moderne

    Michel Adès, Matthieu Dufour, Steven Lu et Serge Provost
  • Le problème des \(N\) corps

    Christiane Rousseau
  • À propos du tic-tac-toe

    Christian Genest

Volumes

  • Volume 18.1 – hiver-printemps 2023
  • Volume 17.2 – été-automne 2022
  • Volume 17.1 – hiver-printemps 2022
  • Journée internationale des mathématiques: Accromath multilingue
  • Volume 16.2 – été-automne 2021
  • Volume 16.1 – hiver-printemps 2021
  • Volume 15.2 – été-automne 2020
  • Thème spécial: Les mathématiques sont partout
  • Volume 15.1 – hiver-printemps 2020
  • Volume 14.2 – été-automne 2019
  • Volume 14.1 – hiver-printemps 2019
  • Volume 13.2 – été-automne 2018
  • Volume 13.1 – hiver-printemps 2018
  • Volume 12.2 – été-automne 2017
  • Volume 12.1 – hiver-printemps 2017
  • Volume 11.2 – été-automne 2016
  • Volume 11.1 – hiver-printemps 2016
  • Volume 10.2 – été-automne 2015
  • Volume 10.1 – hiver-printemps 2015
  • Volume 9.2 – été-automne 2014
  • Volume 9.1 – hiver-printemps 2014
  • Volume 8.2 – été-automne 2013
  • Volume 8.1 – hiver-printemps 2013
  • Volume 7.2 – été-automne 2012
  • Volume 7.1 – hiver-printemps 2012
  • Volume 6.2 – été-automne 2011
  • Volume 6.1 – hiver-printemps 2011
  • Volume 5.2 – été-automne 2010
  • Volume 5.1 – hiver-printemps 2010
  • Volume 4.2 – été-automne 2009
  • Volume 4.1 – hiver-printemps 2009
  • Volume 3.2 – été-automne 2008
  • Volume 3.1 – hiver-printemps 2008
  • Volume 2.2 – été-automne 2007
  • Volume 2.1 – hiver-printemps 2007
  • Volume 1 – été-automne 2006
  • Article vedette

    Auteurs

    • Michel Adès
    • Antoine Allard
    • Jean Aubin
    • Marie Beaulieu
    • Rosalie Bélanger-Rioux
    • Claude Bélisle
    • Marc Bergeron
    • Pierre Bernier
    • André Boileau
    • Véronique Boutet
    • Pietro-Luciano Buono
    • Massimo Caccia
    • Jérôme Camiré-Bernier
    • France Caron
    • Philippe Carphin
    • Kévin Cazelles
    • Laurent Charlin
    • Pierre Chastenay
    • Noémie Chenail
    • Jocelyn Dagenais
    • Marie-France Dallaire
    • Jean-Lou de Carufel
    • Jean-Marie De Koninck
    • Lambert De Monte
    • Jean-Paul Delahaye
    • Marc-André Desautels
    • Florin Diacu
    • Jimmy Dillies
    • Nicolas Doyon
    • Philippe Drobinski
    • Hugo Drouin-Vaillancourt
    • Louis J. Dubé
    • Thierry Duchesne
    • Matthieu Dufour
    • Stéphane Durand
    • Thomas Erneux
    • Philippe Etchécopar
    • Julien Fageot
    • Charles Fleurent
    • Jérôme Fortier
    • Marlène Frigon
    • Jean-François Gagnon
    • André Garon
    • Christian Genest
    • Denis Gilbert
    • Jonathan Godin
    • Frédéric Gourdeau
    • Samuel Goyette
    • Andrew Granville
    • Jean Guérin
    • Hervé Guillard
    • Abba B. Gumel
    • James A. Hanley
    • Alain Hertz
    • Bernard R. Hodgson
    • Isabelle Jalliffier-Verne
    • Guillaume Jouvet
    • Tomasz Kaczynski
    • Patrick Labelle
    • Marc Laforest
    • Nadia Lafrenière
    • Josiane Lajoie
    • Alexis Langlois-Rémillard
    • Simon-Olivier Laperrière
    • René Laprise
    • Steffen Lauritzen
    • Denis Lavigne
    • Adrien Lessard
    • Steven Lu
    • Jean Meunier
    • Erica Moodie
    • Normand Mousseau
    • Johanna G. Nešlehová
    • Pierre-André Noël
    • Dmitry Novikov
    • Ostap Okhrin
    • Laurent Pelletier
    • Jean-François Plante
    • Serge B. Provost
    • Annie Claude Prud'Homme
    • Benoît Rittaud
    • Louis-Paul Rivest
    • Serge Robert
    • André Ross
    • Christiane Rousseau
    • Guillaume Roy-Fortin
    • Yvan Saint-Aubin
    • Maria Vittoria Salvetti
    • Charles Senécal
    • Vasilisa Shramchenko
    • Robert Smith?
    • Anik Trahan
    • Shophika Vaithyanathasarma
    • William Verreault
    • Redouane Zazoun

Sujets

Algèbre Applications Applications des mathématiques Changements climatiques Climat Construction des mathématiques COVID-19 Cristallographie cryptographie GPS Gravité Géométrie Histoire des mathématiques Imagerie Infini Informatique Informatique théorique intelligence artificielle Jeux mathématiques Logique mathématique Lumière Mathématiques de la planète Terre Mathématiques et architecture mathématiques et art Mathématiques et arts Mathématiques et astronomie Mathématiques et biologie Mathématiques et développement durable Mathématiques et littérature Mathématiques et musique Mathématiques et médecine Mathématiques et physique Mathématiques et transport Modélisation Nombres Portrait d'un mathématicien Portrait d'un physicien Probabilités Probabilités et statistique Racines Rubrique des Paradoxes Section problèmes Théorie des groupes Éditorial Épidémiologie

© 2023 Accromath