MP/MP*: Option Informatique
Devoir à rendre après les vacances d'hiver 1998
Figures de pixels, mots de contour et pavages du plan



Présentation

Au début des années 1990, la section de mathématiques de l'École Normale Supérieure de Lyon a progressivement fait évoluer l'esprit de l'épreuve de Mathématiques Appliquées de son concours de recrutement. Le mot Informatique a été introduit dans le titre de cette épreuve; et en 1994 fut posé un problème aussi intéressant que bien construit, amenant l'étudiant à examiner diverses questions posées par des pavages du plan par des dominos. L'une au moins de ces questions était infaisable (en tout cas aucun candidat ne l'a résolue), mais, que le lecteur se rassure, elle ne lui sera pas infligée!

N'ont été gardées que quelques unes des questions sur le pavage par des dominos; une approche d'autres types de pavages a été ajoutée (avec des triominos, avec des tuiles de Wang).

Le sujet abordait aussi la notion de mot de contour d'une partie pavée et connexe du plan. Cette idée a été un peu développée, dans le cadre du programme actuel d'informatique de nos classes: qui dit mots dit aussi langages et reconnaissabilité, voire morphismes, itération de morphismes.

Ce sujet a été soumis à la sagacité des étudiants en févrirer 1998.