Exercice 14

On repère les cases par leurs coordonnées $(i, j) \in \llbracket 0\,,n - 1 \rrbracket^{2}$, ligne et colonne, et l'on note $\rho$ l'application qui envoie une case sur la case qu'elle occupe après un quart de tour, soit $\rho(i, j) = (j, n - 1 - i)$. C'est une permutation de l'ensemble des $n^{2}$ cases, et $\rho^{4} = \mathrm{id}$. Si $H$ est l'ensemble des trous, la grille tournée de $r$ quarts de tour laisse voir les cases de $\rho^{r}(H)$, pour $r \in \llbracket 0\,,3 \rrbracket$.

$\triangleright$ Orbites. On a $\rho^{2}(i, j) = (n - 1 - i, n - 1 - j)$ : c'est la symétrie par rapport au centre. Une case est fixée par $\rho^{2}$ si et seulement si $2i = 2j = n - 1$, ce qui n'arrive que pour $n$ impair, et pour la seule case centrale. Si une case $c$ vérifiait $\rho(c) = c$ ou $\rho^{3}(c) = c$, elle vérifierait $\rho^{2}(c) = c$, en composant par $\rho$ ; ainsi, lorsque $n$ est pair, les cases $c$, $\rho(c)$, $\rho^{2}(c)$, $\rho^{3}(c)$ sont deux à deux distinctes, et les orbites de $\rho$, au sens du chapitre 17, ont toutes quatre éléments. Il y en a $\frac{n^{2}}{4}$.

$\triangleright$ Caractérisation. Une case $c$ apparaît à travers un trou dans la position $r$ si et seulement si $c \in \rho^{r}(H)$, c'est-à-dire $\rho^{-r}(c) \in H$. Le nombre de positions où elle apparaît est donc le nombre d'éléments de $H$ parmi $c$, $\rho^{-1}(c)$, $\rho^{-2}(c)$, $\rho^{-3}(c)$, qui forment l'orbite de $c$. Lorsque $n$ est pair, la grille est une grille de Fleissner si et seulement si $H$ contient exactement une case de chaque orbite.

La figure numérote les cases d'une grille de côté $4$ selon leur orbite : les quatre coins forment l'orbite $1$, le carré central l'orbite $4$. Une grille de Fleissner choisit un trou portant chacun des numéros $1$ à $4$, par exemple le quart supérieur gauche, grisé en ocre ; le quart de tour $\rho$ envoie chaque case sur une case de même numéro.

1. Pour $n = 6$, il y a $\frac{36}{4} = 9$ orbites, donc $9$ trous, et l'on choisit une case dans chaque orbite, de $4$ façons indépendamment (proposition 2 (iv)). $$\boxed{9 \text{ trous, et } 4^{9} = 262\,144 \text{ grilles de Fleissner de côté } 6}$$

2. Si $n$ est pair, le même raisonnement donne $\frac{n^{2}}{4}$ trous et $4^{n^{2}/4} = 2^{n^{2}/2}$ grilles. Si $n$ est impair, la case centrale $c_{0}$ est fixée par $\rho$ : elle apparaît dans les quatre positions si $c_{0} \in H$, et dans aucune sinon, jamais dans exactement une. $$\boxed{\text{Il existe des grilles de Fleissner de côté } n \text{ si et seulement si } n \text{ est pair ; il y en a alors } 4^{n^{2}/4}}$$ Une énumération exhaustive confirme les valeurs $4$ pour $n = 2$, $0$ pour $n = 3$ et $256$ pour $n = 4$. Le nombre de grilles croît très vite : une grille de côté $10$ se choisit parmi $4^{25} \approx 1{,}1 \cdot 10^{15}$, ce qui rend vaine la recherche de la grille par essais successifs.