Pour le temps des fêtes, nous proposons un problème à résoudre en famille. Il suffit d'avoir chez soi un oncle Albert (ou une tante Ursule) et une grille de dimensions 2ⁿ par 2ⁿ. Par exemple, un échiquier ordinaire est une grille 8 par 8. Les pièces du jeu sont des "trominos en L", c'est à dire des pièces formées à partir de dominos en ajoutant un troisième carré pour faire un L:

Maintenant, l'oncle Albert place un sou sur une des cases de la grille.

Votre tâche est de recouvrir les 2²ⁿ - 1 cases qui restent avec (2²ⁿ - 1)/3 trominos. Est-ce toujours possible?

Solution au problème MP29

Nous avons reçu des solutions de Francesco Barioli (Regina), Pierre Bornsztein (France), Normand Laliberté (Ontario), Juan Mir Pieras (Espagne), Gordon Robinson (Colombie Britannique), Jayavel Sounderpandian (Wisconsin) et Jason Stein (Regina) en plus de solutions partielles de Rachel Fello (internet) et Lina (Californie). La pluspart des solutions ressemblent à celle de Laliberté reproduite ci-bas:

Nous allons montrer -par induction sur n- qu'il est toujours possible de recouvrir les 2²ⁿ - 1 cases qui restent avec
(2²ⁿ - 1) / 3 trominos.

Comme base d'induction nous pouvons prendre soit n = 0 soit
n = 1.

Dans le cas n = 0, la grille ne comprend qu'une case. Une fois le sou posé, il ne reste aucune case à recouvrir; 0 tromino suffit donc.

Dans le cas n = 1, la grille comprend 4 cases. Une fois le sou posé, les 3 cases qui restent forment un tromino qui suffit donc.

[Rachel Fello donne le diagramme suivant pour résoudre le cas de notre diagramme:

]

Supposons la proposition vraie pour n = k.

Considérons le cas n = k + 1.

Il est facile de voir que la grille 2^k+1 par 2^k+1 comprend 4 fois autant de cases que la grille 2^k par 2^k. En effet
2^k+1 x 2^k+1 = 4 x 2^k x 2^k.
Dénotons par A, B, C et D chacune de ces grilles.

On peut supposer qu'elles sont arrangées ainsi:

Tante Ursule doit mettre son sou dans exactement une de ces grilles, disons A. Comme A est une grille 2^k par 2^k, l'hypothèse d'induction s'applique: Le reste de A peut être recouvert avec (2^2k - 1) / 3 trominos.

Appelons caseB caseC et caseD, respectivement, la case de B, C et D où ces 3 grilles se rencontrent. Ces trois cases peuvent être recouvertes par un tromino -- elles en forment un.

Comme B, C et D sont des grilles 2k par 2k, l'hypothèse d'induction s'applique à nouveau: le reste de chaque grille de B, C et D peut être recouvert avec (2^2k - 1) / 3 trominos.

La grille 2^k+1 par 2^k+1 peut donc être recouverte complètement avec des trominos. Il en faut:

(2^2k - 1) / 3 pour A,
1 pour le tromino formé par caseB caseC et caseD,
3 x (22k - 1) / 3 pour le reste B, C et D.

Au total:

(2^2k - 1) / 3 + 1 + 2^2k - 1

= (2^2k - 1) / 3 + 2^2k

= (2^2k - 1 + 3 x 2^2k) / 3

= (2^2k x (1 + 3) - 1) / 3

= (2^2k x 2² - 1) / 3

= (2^{2 x (k + 1)} - 1) / 3

QED

Barioli donne une démonstration différente, utilisant des "2ⁿ-trominos", c'est à dire des trominos "gras" formés en assemblant trois grilles 2^n-1 par 2^n-1 en forme de L. Le diagramme suivant montre qu'un 2ⁿ-tromino peut être recouvert par quatre 2^n-1-trominos:

En recouvrant ensuite ces 2^n-1-trominos par des 2^n-2-trominos, puis ceux-ci par des 2^n-3-trominos, et ainsi de suite, on recouvre le 2ⁿ-tromino initial par des 2¹-trominos, c'est à dire des trominos ordinaires. Ainsi, lorsque l'oncle Albert pose son sou sur une des cases de la grille 2ⁿ par 2ⁿ, on peut procéder séparer la grille en un 2ⁿ-tromino et une grille 2^n-1 par 2^n-1 contenant le sou, recouvrir le 2ⁿ-tromino avec des trominos, puis passer à la grille 2^n-1 par 2^n-1 et faire de même. On recouvrira ainsi toute la grille avec des trominos.

Remarque 1. La stratégie de recouvrement est unique
seulement pour n = 1, 2.

Remarque 2. On peut se demander ce qui arrive avec des grilles
de dimensions différentes: si on place un sou sur une grille
m par n, où m ≤ n et mn - 1 est un multiple de 3, est-ce que
le reste des cases peut être recouvert par (mn - 1)/3 trominos?
Barioli a un argument qui ressemble à sa démonstration
précédente, réduisant de nouveaux cas à des cas déjà
rencontrés. Avec un peu de patience, il arrive à démontrer
qu'il existe seulement quelques grilles qui ne peuvent pas
être recouvertes. Ces cas impossibles se répartissent en
quatre classes:

1. m = 1.
2. m = 2, n = 5 + 3k, k ≥ 0, et le sou est placé
   comme suit (où k' + k'' = k):
   
   
   
3. m = 5, n = 8 + 3k, et le sou est dans la ligne du milieu,
   à deux colonnes de la fin:
   
   
   4. m = n = 5, et le sou est dans une des 16
   positions suivantes: