Préliminaires
L’épreuve est composée d’un problème unique, comportant 27 questions. Après cette section de préliminaires, qui présente le jeu du hanjie, le problème est divisé en trois sections qui peuvent être traitées séparément, à condition d’avoir lu les définitions introduites jusqu’à la question traitée.
Dans la première section (page 2), nous résolvons le jeu par des raisonnements logiques. Dans la deuxième section (page 3), nous modélisons le jeu et le résolvons par une stratégie algorithmique de retour sur trace.
Dans la troisième section (page 6), nous appliquons une méthode de parcours de graphe en théorie des automates pour accélérer la résolution du jeu.
Dans tout l’énoncé, un même identificateur écrit dans deux polices de caractères différentes désigne la même entité, mais du point de vue mathématique pour la police en italique (par exemple n) et du point de vue informatique pour celle en romain avec espacement fixe (par exemple n).
Des rappels de logique et des extraits du manuel de documentation de OCaml sont reproduits en annexe. Ces derniers portent sur le module Array et le module Hashtbl.
Travail attendu
Pour répondre à une question, il est permis de réutiliser le résultat d’une question antérieure, même sans avoir réussi à établir ce résultat.
Il faudra coder des fonctions à l’aide du langage de programmation OCaml, en reprenant l’en-tête de fonction fourni par le sujet, sans s’obliger à recopier la déclaration des types.
Quand l’énoncé demande de coder une fonction, sauf demande explicite de l’énoncé, il n’est pas nécessaire de justifier que celle-ci est correcte ou de vérifier que des préconditions sont satisfaites.
Le barème tient compte de la clarté des programmes : nous recommandons de choisir des noms de variables intelligibles ou encore de structurer de longs codes par des blocs ou par des fonctions auxiliaires dont on décrit le rôle.
Description du jeu du hanjie
Le hanjie est un jeu de réflexion à l’intersection de l’art des pixels et de la tomographie discrète, technique d’imagerie courante en médecine, en géophysique ou en science des matériaux entre autres domaines.
Il consiste à retrouver une image par le noircissement de certaines cases d’une grille rectangulaire sur la base d’indications laissées sur les côtés de la grille.
Pour chaque rangée, qu’elle soit horizontale ou verticale, le joueur dispose d’une suite d’entiers non nuls {t_1,t_2,t_3}, etc. qui indiquent que la rangée contient une série de {t_1} cases noires consécutives, suivie plus loin d’une série de {t_2} cases noires consécutives, et ainsi de suite.
Un nombre quelconque de cases blanches peut se trouver en tête ou en queue de rangée ; au moins une case blanche sépare deux séries de cases noires.
Voici un exemple, que nous résolvons à la main. Une grille vide est fournie ci-contre. Elle est de dimension {5\times7}. Nous marquons les cases par des symboles « ? » tant que nous ignorons leur couleur.
Nous comptons les rangées à partir de 0, de gauche à droite pour les colonnes et du haut vers le bas pour les lignes.

La colonne 0 et la colonne 5 sont de longueur 5. Or l’indication est [5] dans les deux cas. Elles doivent donc chacune contenir 5 blocs noirs consécutifs.
Nous les noircissons en totalité.

Dans la ligne 0, il n’y a qu’une seule manière de placer un bloc de 4 cases noires puis 2 cases noires.
De même, dans la ligne 2, il n’y a qu’une seule manière de positionner le bloc de longueur 2 : il doit se trouver au milieu entre les deux blocs déjà isolés. Dans la ligne 3, nous avons déjà placé deux cases noires : les autres sont donc toutes blanches.
Enfin, dans la ligne 4, il n’y a plus qu’une seule manière de placer un bloc de 6 cases noires.

Enfin, en reprenant les indications des colonnes, nous voyons que dans les colonnes 1, 2 et 4, la dernière case inconnue est blanche.
Dans la colonne 3 et 6 en revanche, nous devons noircir la dernière case inconnue. Nous avons obtenu une solution de notre hanjie. Elle est unique.

1. Hanjie et calcul de vérité
Dans cette section, nous raisonnons avec la logique propositionnelle pour déterminer la couleur de certaines cases. Nous nous concentrons sur le hanjie {h_0} défini par

et dont une solution est la suivante :

Nous introduisons six variables booléennes, nommées {x_0,x_1,\ldots,x_5} et correspondant aux cases ci-contre. Nous associons la valeur de vérité V (vrai) à la couleur noire et F (faux) à la couleur blanche.

Soit {L_0} le prédicat : « l’indication de la ligne zéro du hanjie {h_0} est satisfaite ».
En déduire une formule de logique {\varphi} sous forme normale conjonctive qui décrit le prédicat {L_0}.
Soit {C_1} le prédicat : « l’indication de la colonne du milieu du hanjie {h_0} est satisfaite ».
En déduire une formule de logique {\psi} sous forme normale conjonctive qui décrit le prédicat {C_1}.
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres