Petites enigmes > Réponse Sciences sujet

1. On peut toujours construire un triomino de taille n à partir de quatre triominos de taille n-1 en les combinant de la manière suivante.






Cette construction est valide quelque soit la rotation d'un angle multiple de 90° ; il est possible d'orienter ces triominos n'importe comment dans la grille. L'énoncé nous autorise à placer des triominos de taille 1. Par récurrence, on est donc capables de placer des triominos de taille n > 0 quelconque, de coté 2^n x 2^n.

2. A partir d'une grille de taille 2^n x 2^n avec une seule cellule noircie, on montre qu'on peut tout noircir. On part d'une décomposition en quadtree de la grille, où - la grille étant de dimension 2^n x 2^2 - chaque niveau de l'arbre décompose une sous grille de taille 2^i x 2^i en quatre grilles de taille 2^(i-1) x 2^(i-1).

On noircit récursivement, de sorte que la surface noircie à l'étape i soit de taille 2^i x 2^i, correspondant exactement à un sous-arbre du quadtree de hauteur (i+1). A l'étape 0, on part de la case noircie, soit une zone noircie de 1x1, correspondant à une feuille du quadtree. A chaque étape i suivante, on part de du nœud noirci dans le quadtree, on remonte au nœud parent, et on recouvre les trois autres nœuds fils d'un triomino de taille i. En effet, les trois fils représentent des zones "contingües avec un angle". Après la n-ème étape, on a noirci toute la grille.