Exercice académique 1 — Escagone (tous candidats)

3. Deux carrés distincts de la diagonale ne peuvent jamais être couverts par une même tuile (car ils sont à des hauteurs différentes et une tuile carrée ne peut « suivre » l'escalier) : chaque carré de la diagonale nécessite donc sa propre tuile.

4. Si le coin bas-droite est couvert par une tuile qui ne touche aucun carré de la diagonale, cette tuile est « en trop » par rapport aux \(n\) tuiles minimales dédiées à la diagonale, contredisant \(T(n)=n\).

8-10. Raisonner par récurrence/construction : une fois la tuile de côté 2 placée en bas de la 2^e colonne, ce qui reste à couvrir est un escagone « décalé » de forme similaire, permettant d'itérer l'argument et de faire apparaître la somme de puissances de 2.

14. L'aire totale de l'escagone de hauteur \(n\) vaut \(1+2+\cdots+n=\dfrac{n(n+1)}2\) ; pour \(n=8\), l'aire vaut 36. Exprimer aussi cette aire comme \(n_1\times1^2+n_2\times2^2+n_3\times3^2\) et combiner avec le nombre total de tuiles \(n_1+n_2+n_3\) pour contraindre les valeurs possibles.

1. \(T(4)=7\). L'aire de l'escagone de hauteur 4 vaut \(1+2+3+4=10\). Une tuile de côté 3 exigerait 3 colonnes consécutives ayant chacune \(\ge3\) cases : impossible ici (colonne 1 n'a qu'1 case, colonne 2 n'en a que 2). La plus grande tuile possible est donc de côté 2. Avec \(a\) tuiles de côté 2 et \(b\) de côté 1 : \(4a+b=10\), total \(a+b\) à minimiser, donc \(a\) à maximiser. On vérifie géométriquement qu'on ne peut placer qu'une seule tuile \(2\times2\) sans chevauchement (par exemple sur les colonnes 3-4, lignes 1-2) : \(a=1\) donne \(b=6\), soit 7 tuiles. Recouvrement explicite : tuile \(2\times2\) sur colonnes 3-4/lignes 1-2, puis 6 tuiles \(1\times1\) sur les cases restantes \((1,1),(2,1),(2,2),(3,3),(4,3),(4,4)\). Donc \(T(4)=7\).

2. \(T(5)\). Aire \(=1+2+3+4+5=15\). On peut placer 3 tuiles \(2\times2\) disjointes (colonnes 2-3/lignes 1-2, colonnes 4-5/lignes 1-2, colonnes 4-5/lignes 3-4) et 3 tuiles \(1\times1\) sur les cases restantes \((1,1),(3,3),(5,5)\) : \(3+3=6\) tuiles, donc \(T(5)\le6\). Un examen des combinaisons d'aires (\(9+2+2+1+1\) nécessiterait deux \(2\times2\) après la tuile \(3\times3\), géométriquement impossible ici) montre qu'on ne peut pas descendre à 5 tuiles. Donc \(T(5)=6\).

3. \(T(n)\ge n\). Les carrés de la diagonale sont les \(n\) cases \((k,k)\), une par colonne. Deux carrés distincts \((i,i)\) et \((j,j)\) (\(i

4. Si \(T(n)=n\), \(n\) est impair. Puisqu'il y a exactement \(n\) tuiles pour \(n\) carrés de la diagonale et qu'aucune tuile n'en couvre plus d'un (question 3), chaque tuile en couvre exactement un. Soit \(\tau\) la tuile couvrant le coin \((n,1)\) (bas de la dernière colonne), de côté \(c\) : comme elle ne peut s'étendre ni sous la ligne 1 ni au-delà de la colonne \(n\), elle occupe les colonnes \([n-c+1,n]\) et les lignes \([1,c]\). D'une part, la colonne \(n-c+1\) doit avoir au moins \(c\) cases, donc \(n-c+1\ge c\), soit \(c\le\frac{n+1}2\). D'autre part, \(\tau\) doit couvrir un carré de la diagonale \((d,d)\) avec \(n-c+1\le d\le c\) : pour qu'un tel \(d\) existe, il faut \(n-c+1\le c\), soit \(c\ge\frac{n+1}2\). En combinant les deux, \(c=\frac{n+1}2\) exactement, ce qui exige que \(n+1\) soit pair, donc \(n\) impair. (Le carré de la diagonale couvert est alors l'unique \(d=c=\frac{n+1}2\).)

5. \(n\) impair n'est pas suffisant. \(n=5\) est impair, mais \(T(5)=6\ne5\) (question 2). Donc la condition « \(n\) impair » est nécessaire mais pas suffisante.

6. \(T(6)\). \(T(6)\ge6\) (question 3), et \(6\) est pair donc \(T(6)\ne6\) (question 4) : ainsi \(T(6)\ge7\). Un recouvrement à 7 tuiles existe : \(1\times1\) en \((1,1)\), \(2\times2\) sur colonnes 2-3/lignes 1-2, \(1\times1\) en \((3,3)\), \(3\times3\) sur colonnes 4-6/lignes 1-3, \(1\times1\) en \((4,4)\), \(2\times2\) sur colonnes 5-6/lignes 4-5, \(1\times1\) en \((6,6)\). Donc \(T(6)=7\).

7. Si \(T(n)=n\), la case \((2,1)\) est couverte par une tuile de côté 2. Comme en question 4, une tuile couvrant \((2,1)\) ne peut pas empiéter sur la colonne 1 (qui n'a qu'une case, donc ne supporte pas une tuile de côté \(\ge2\)) : elle occupe donc les colonnes \([2,2+c-1]\), et la colonne 2 (qui n'a que 2 cases) impose \(c\le2\). Si \(c=1\), cette tuile ne couvre que la case \((2,1)\), qui n'est pas un carré de la diagonale — or on a vu (question 4) que dans un recouvrement à \(n\) tuiles, chaque tuile couvre exactement un carré de la diagonale : contradiction. Donc \(c=2\).

8. \(n=1+2+2^2+\cdots+2^k\). D'après la question 4, la tuile du coin \((n,1)\) a pour côté \(c=\frac{n+1}2\) et couvre le carré diagonal \((c,c)\). En la retirant, il reste deux morceaux disjoints : les colonnes \(1\) à \(c-1\) (un escagone de hauteur \(c-1=\frac{n-1}2\)), et les colonnes \(c+1\) à \(n\) amputées de leurs \(c\) premières lignes — qui forment également un escagone de hauteur \(\frac{n-1}2\) (la colonne \(c+1\) n'a plus qu'1 case libre, la colonne \(c+2\) en a 2, etc., jusqu'à la colonne \(n\) qui en a \(\frac{n-1}2\)). Comme le recouvrement total utilise \(n\) tuiles dont 1 pour le coin, les \(n-1\) tuiles restantes doivent couvrir ces deux escagones de hauteur \(m=\frac{n-1}2\) chacun, qui nécessitent chacun au moins \(T(m)\ge m\) tuiles (question 3) : \(2T(m)\le n-1=2m\), donc \(T(m)\le m\), et avec \(T(m)\ge m\) on obtient \(T(m)=m\). La propriété « \(T=\text{hauteur}\) » se retrouve donc à l'identique sur \(m=\frac{n-1}2\) : par récurrence descendante (avec \(m\) impair à son tour d'après la question 4 appliquée à \(m\), jusqu'à atteindre 1), on obtient \(n=2^{k+1}-1=1+2+2^2+\cdots+2^k\) pour un certain \(k\ge0\).

9. Réciproque. Si \(n=2^{k+1}-1\), construisons un recouvrement à \(n\) tuiles par récurrence sur \(k\) : pour \(k=0\) (\(n=1\)), une seule tuile \(1\times1\) suffit, \(T(1)=1\). Pour l'hérédité, supposons \(T(m)=m\) avec \(m=2^k-1\) ; posons \(n=2m+1=2^{k+1}-1\). En plaçant la tuile de côté \(c=m+1=\frac{n+1}2\) dans le coin bas-droite (colonnes \(m+1\) à \(n\), lignes 1 à \(m+1\)), il reste exactement deux escagones de hauteur \(m\) (colonnes \(1\) à \(m\), et colonnes \(m+2\) à \(n\) amputées), chacun recouvrable en \(T(m)=m\) tuiles par hypothèse de récurrence. Total : \(1+m+m=2m+1=n\) tuiles. Donc \(T(n)\le n\), et avec \(T(n)\ge n\) (question 3), \(T(n)=n\). La récurrence \(T(2m+1)=1+2T(m)\) redonne bien \(T(1)=1,T(3)=3,T(7)=7,T(15)=15,\ldots\)

10. Conclusion : \(T(n)=n\iff n=2^{k+1}-1\). Les deux sens ont été établis aux questions 8 et 9.

11. \(T(7)=7\). Ici \(7=2^3-1\), donc \(T(7)=7\) par la question 10. Recouvrement explicite (construction récursive de la question 9) : \(1\times1\) en \((1,1)\) ; \(2\times2\) sur colonnes 2-3/lignes 1-2 (couvrant le diagonal \((2,2)\)) ; \(4\times4\) sur colonnes 4-7/lignes 1-4 (couvrant le diagonal \((4,4)\)) ; puis, sur le sous-escagone restant (colonnes 5-7, hauteur 3) : \(1\times1\) en \((5,5)\), \(2\times2\) sur colonnes 6-7/lignes 5-6, \(1\times1\) en \((7,7)\). Total : 7 tuiles.

Hauteur 8.

12. Une tuile de côté 4 tient sur les colonnes 5-8/lignes 1-4 (colonne 5 a exactement 5 cases \(\ge4\)). En complétant avec des tuiles plus petites, on obtient une borne \(T(8)\le12\) environ ; comme \(8\) est pair, \(T(8)\ne8\) (question 4), donc \(T(8)\ge9\).

13. On peut placer deux tuiles de côté 3 disjointes (colonnes 6-8/lignes 1-3 et colonnes 6-8/lignes 4-6 par exemple), ce qui, complété par des tuiles \(1\times1\)/\(2\times2\) sur le reste, donne un recouvrement à 12 tuiles au plus. Avec la question 12, on obtient l'encadrement \(9\le T(8)\le12\).

14. Pour un recouvrement utilisant uniquement des tuiles de côté \(1,2,3\) (en nombres \(n_1,n_2,n_3\)), l'aire totale (36 pour \(n=8\)) donne \(n_1+4n_2+9n_3=36\), et le nombre de tuiles est \(n_1+n_2+n_3\).

15. \(T(8)=11\). Un recouvrement explicite à 11 tuiles (non symétrique) : \(1\times1\) en \((1,1)\) ; \(2\times2\) sur colonnes 2-3/lignes 1-2 ; \(1\times1\) en \((3,3)\) ; \(2\times2\) sur colonnes 4-5/lignes 1-2 ; \(2\times2\) sur colonnes 4-5/lignes 3-4 ; \(1\times1\) en \((5,5)\) ; \(3\times3\) sur colonnes 6-8/lignes 1-3 ; \(3\times3\) sur colonnes 6-8/lignes 4-6 ; \(1\times1\) en \((7,7)\) ; \(1\times1\) en \((8,7)\) ; \(1\times1\) en \((8,8)\). Vérification de l'aire : \(6\times1+3\times4+2\times9=6+12+18=36\) ✓, soit \(n_1=6,n_2=3,n_3=2\) dans l'équation de la question 14, pour un total de 11 tuiles. Une recherche exhaustive (voir note ci-dessous) confirme qu'aucun recouvrement à 9 ou 10 tuiles n'existe : donc \(T(8)=11\).