retrouvez l'article en pdf.

Problème 1 :

On suit l’indication. Par exemple, pour le sommet en gras (figure de gauche), il suffit de regarder comme deuxième sommet potentiel n’importe quel sommet à sa droite, puis on regarde de combien de façons on peut le compléter par-dessous (et non pas par-dessus). Dans ce cas, on trouve 4 :

En effectuant cela pour tous les sommets (figure du milieu), on trouve 13 au total. Pour recompter, on peut par exemple choisir d’abord le sommet en bas à gauche puis celui en haut à gauche (figure de droite), ou toute autre combinaison possible. Ou la forme du rectangle ( 1×1 , 2×1 , 1×2 , …) puis le sommet en haut à gauche, mais cela me semble moins simple.

Problème 2 :

De nouveau, on suit l’indice (qui n’est vraiment pas clair, désolé). Faisons un exemple. Le nombre de chemins les plus courts allant du départ à A vaut 3 (figure de gauche). Par symétrie, c’est aussi valable pour B. Maintenant, pour le point C, les chemins les plus courts du départ à C passent tous soit par A soit par B, et c’est en fait la somme des deux nombres précédents, soit 6.

On comprend donc qu’il suffit d’écrire 1 sur le sommet du départ, puis de haut en bas d’écrire la somme des valeurs des sommets (ou la valeur du sommet) juste au-dessus (figure du milieu). On trouve 20 chemins en tout.

 

Une autre manière de compter est d’utiliser la symétrie selon l’axe horizontal. Un chemin le plus court entre départ et arrivée consiste en un chemin le plus court entre départ et l’un des points w, x, y ou z dans la figure de droite (il y en a respectivement 1, 3, 3 et 1), puis un chemin le plus court entre le même point et l’arrivée (il y en a, par symétrie, également respectivement 1, 3, 3 et 1). Donc, on peut les combiner de 1×1+3×3+3×3+1×1=20 façons.

Problème 3 :

Clairement, un chemin le plus court aura longueur sept (l’unité étant le côté d’un petit carré), et passera exactement par une flèche. On peut donc séparer le problème en quatre problèmes, un par flèche. Pour la flèche a, il n’y a qu’1 chemin possible (j’ai tendance à distinguer les nombres qu’il faut sommer à la fin, par exemple en les écrivant en chiffres plutôt qu’en lettres), pour b 4, pour c 6 et pour d 4 soit 15 en tout.

On peut aussi utiliser la dernière méthode de l’exercice 2. On compte les chemins les plus 

courts partant de A (nombres non entourés de la figure de droite). Le nombre de tels chemins arrivant par exemple en x (non entouré), est égal à celui de ceux arrivant en y plus celui de ceux arrivant en z. On fait de même avec les chemins les plus courts arrivant en B (nombres entourés de la figure de droite), et on a une relation similaire pour les sommets x, y et z entourés. Maintenant, pour chaque flèche, il faut combiner un chemin minimal partant de A et arrivant à la flèche et un chemin minimal partant de la flèche et arrivant en B. On obtient a →1×1, b →4×1, c →3×2 et d →1×4, ce qui redonne bien 15 en tout.

Problème 4 :

Si l’on sépare des cas en fonction du sommet supérieur gauche du carré, on obtient la figure à gauche. On peut vérifier après coup la symétrie selon la diagonale.

En sommant le tout, on trouve 48.

 

Pour ne pas prendre en compte les symétries (ou rotations), travailler sur un sommet précis du carré fonctionne mal, car ce sommet change avec les symétries. (Toutefois, en faisant attention, on doit pouvoir compter le nombre de paires carré / sommet du carré puis diviser par quatre à la fin). Compter en fonction du centre du carré permet de faire le calcul directement. Sur la figure du milieu, chaque nombre est un centre possible de carré dans un huitième du carré, et le nombre lui-même indique le nombre de copies par symétrie de ce centre (voir les exemples du nombre entouré et du nombre encadré). Dans la figure de droite, on indique le nombre de carrés concernés. Il reste à faire la somme des produits correspondants dans les deux figures : (en ignorant les 0) 4×1+4×1+4×1+8×1+8×1+8×1+8×1+4×1=48, le compte est bon !

Problème 5 :

On suit l’indice. Par exemple, le nombre de chemins EPF qui se terminent en un certain F est égal à la somme des nombres des chemins EP se terminant en un P adjacent orthogonalement ou diagonalement à ce F (voir figure gauche).

En comptant les chemins E, EP, EPF, EPFL terminant dans chaque case, on obtient la figure du milieu. En sommant sur les cases L, on obtient le nombre recherché, à savoir 8.

La figure de droite compte le nombre de chemins L, LF, LFP, LFPE. Clairement, le nombre de chemins LFPE doit être égal au nombre de chemins EPFL. Et en effet, on retrouve bien 8.

Problème 6 :

Exercice plus difficile. Pour clarifier l’énoncé, on ne doit pas compter par exemple et  mais on doit compter . Il ne peut donc pas y avoir trois sommets sur une même rangée, colonne ou diagonale. Le nombre de sommets sur chaque rangée, dans l’ordre, peut donc être (2,2,0), (2,0,2), (2,1,1), (1,2,1) ou des cas symétriques à ceux-là. Idem pour les colonnes. On obtient le tableau suivant.

On élimine les doublons (qui sont forcément dans la même case) et ceux qui ont un alignement diagonal, puis on compte le nombre de quadrilatères correspondant à chaque cas (2 ou 3 en fonction des symétries). Remarquons que les cas sont clairement indépendants. On trouve le tableau suivant.

Cela donne en tout 36.

Une façon nettement différente de compter consiste à d’abord décider du côté le plus long, puis de son côté en face (sans alignement de trois points). Chaque cas correspond potentiellement à deux quadrilatères. Il faut également éliminer les doublons.

On fait les comptes (seulement ceux dont le couple de côtés non représentés n’est pas déjà traité) :

 

 

 

 

 

 

 

Un peu compliqué, mais l’important, c’est de retomber sur 36.

Problème 7 :

En écrivant le corrigé, j’ai mal lu l’énoncé, et je n’ai pas souligné l’information importante que deux triangles adjacents doivent être de couleurs différentes. Sans ça, c’est nettement plus compliqué (comme quoi, faudrait que je suive mes propres conseils). Puisque maintenant le corrigé est rédigé...

Exercice bonus : Refaire l’exercice 7 sans la condition que deux triangles adjacents sont de la même couleur.

Correction de l’exercice de départ : On remplace la couleur blanche par vert (blanc signifiant pas encore colorié). On fait une disjonction de cas, comme dans l’indice.

• • sommets monochromes, par exemple  quitte à multiplier par trois,

    • côtés monochromes : deux possibilités, donc en tout 3×2 → 6 ;

    • côtés bichromes : par exemple , mais impossible à compléter dans tous les cas → 0 ;

  • sommets bichromes, par exemple  quitte à multiplier par six,

    • côtés monochromes,  une seule façon de compléter, donc → 6 ;

    • côtés bichromes, rouge, bleu, bleu , une façon de compléter à chaque fois, donc en tout → 12 ;

    • tous les autres cas sont impossibles à compléter, il y aura forcément deux triangles verts adjacents ;

  • sommets trichromes, .

    • côtés bichromes, par exemple rouge, rouge, bleu quitte à multiplier par 6. On ne peut pas mettre le bleu sur le côté opposé au sommet bleu, faute de pouvoir placer le dernier triangle bleu. Donc, on a soit , soit . Seul le deuxième cas se complète, et d’une unique manière, donc en tout → 6.

    • côtés trichromes, aucun côté ne peut être de la même couleur que le sommet opposé, donc on a seulement  et , qui se complètent chacun d’une unique façon → 2.

En sommant le tout, on tombe sur 32 coloriages différents.

On recompte en coloriant maintenant d’abord les rouges puis les bleus. Pour être sûr de tous les prendre en compte, je regarde d’abord le cas de trois sommets rouges, puis de deux sommets rouges et un côté rouge, puis de deux sommets rouges et zéro côté rouge, etc. J’indique à chaque fois le nombre de façons de compléter.  2,  2,  2,  2,  2,  4,  4,  4,  4,  6. On retrouve bien 32 en tout.

Correction de l’exercice bonus : On remplace la couleur blanche par vert (blanc signifiant pas encore colorié). On fait une disjonction de cas, comme dans l’indice.

• • sommets monochromes, par exemple  quitte à multiplier par trois,

    • côtés monochromes : deux possibilités, donc en tout 3×2 → 6 ;

    • côtés bichromes : par exemple , quitte à multiplier par deux. Deux cas possibles, donc en tout 3×2×2 → 12 ;

  • sommets bichromes, par exemple  quitte à multiplier par six,

    • côtés monochromes,  2, donc → 12 ;

    • côtés bichromes, rouge, bleu, bleu 1, 1, donc en tout → 12 ;

    • côtés bichromes, rouge, vert, vert :  2,  3 → 30 ;

    • côtés bichromes, bleu, vert, vert :  3,  6 → 54 ;

    • côtés bichromes, bleu, bleu, vert :  2,  3, → 30 ;

    • côtés trichromes :  3,  3,  3, → 54

  • sommets trichromes, . Cela fixe complètement la figure, donc quelle que soit la façon de colorier l’intérieur en deux triangles de chaque couleur, on obtiendra des configurations différentes. On choisi donc deux triangles à colorier en rouge, puis deux triangles à colorier en bleu. Cela donne .

En sommant le tout, on tombe sur 300 coloriages différents.

Maintenant, on va compter, d’abord en coloriant les triangles rouges, puis les bleus. On va utiliser une astuce pour regrouper des coloriages menant à un même nombre. Pour cela, on remarque que les deux opérations suivantes, qui transposent des triangles, préservent les symétries. Donc, lorsqu’on les applique sur un coloriage partiel, le nombre de façons de compléter le coloriage ne change pas.

On regroupe donc les coloriages en rouge. On donne l’idée pour obtenir 

ces différents cas en expliquant les deux premiers cas.

• • Ceux dont tous les sommets, ou tous les côtés, ou les trois derniers triangles sont rouges : , , , le premier, donc chacun, peut se compléter de six manières, donc en tout → 18 ;

  • Deux sommets rouges et un côté rouge non opposé à un sommet rouge, ou un côté et deux sommets rouges sans opposition, etc. , , , , , , douze façons de compléter → 72 ;

  • , , , , , , on choisit trois triangles bleus parmi les six triangles blancs, les vingt configurations sont clairement différentes → 120 ;

  • , , , idem → 60;

  • , idem → 20 ;

  • , ici ça ne fonctionne plus, on a un axe de symétrie, il n’y a que dix coloriages possibles → 10 ;

En sommant tout, on retrouve bien 300 coloriages.

En pratique, il y a des façons plus efficaces de compter, par exemple en utilisant la formule de Burnside, mais ce sera pour une prochaine fois.