Exercice 2 — 1, 2, 3 ... dallez !

Sujet

Dans tout ce qui suit, \(n\) désigne un entier naturel non nul. Une unité de longueur étant donnée, on considère un carré de côtés de longueur \(n\). On note ce carré \(K_{n}\), et on se propose de le paver à l'aide de carrés de côtés de longueur 1, 2 ou 3, c'est-à-dire de le recouvrir sans débordement ni chevauchement. Par commodité, on dira qu'un carré de côtés de longueur \(i\) ( \(i\) valant 1,2 ou 3 ) est de taille \(i\).
On montre ci-contre un pavage du carré \(K_{6}\) comportant cinq carrés de taille 1 , un de taille 2 et trois de taille 3.

1. a. Est-il possible de paver le carré \(K_{6}\) en n'utilisant aucun carré de taille 1 ?
   b. Montrer qu'il n'est pas possible de paver le carré \(K_{5}\) sans utiliser de carré de taille 1 . c. Donner un pavage de \(K_{5}\) comportant quatre carrés de taille 1 . On admettra dans la suite qu'il n'existe pas de pavage de \(K_{5}\) avec des carrés de taille 1,2 ou 3 comportant strictement moins de quatre carrés de taille 1.
   Tout carré \(K_{n}\) peut être pavé avec \(n^{2}\) carrés de taille 1. Certains \(K_{n}\) peuvent l'être sans en utiliser. Dans cet exercice, on détermine le nombre minimal de carrés de taille 1 nécessaires au pavage du carré \(K_{n}\) par des carrés de taille 1 , 2 ou 3 ; on note \(u(n)\) ce nombre.
2. Déterminer \(u(1), u(8)\) et \(u(9)\).
3. Plus généralement, que vaut \(u(n)\) si \(n\) est pair ? Que vaut \(u(n)\) si \(n\) est un multiple de 3 ?

On s'intéresse donc dorénavant aux entiers \(n\) impairs et non multiples de 3 .

1. a. Montrer que si \(n\) est impair et non multiple de 3 , alors \(n+6\) est impair et non multiple de 3 .
   b. Montrer que, pour tout \(n\) supérieur ou égal à 4 : \(u(n+6) \leq u(n)\) (on considérera les carrés \(K_{n+6}\) et \(K_{n}\) ).
2. a. Peut-on paver un rectangle de largeur 5 et de longueur 6 en utilisant des carrés de tailles 2 et 3 ? En déduire que \(u(11) \leq 1\).
   b. Montrer que \(u(13) \leq 1\).
   c. On admet que \(u(5)=4\) (comme dit plus haut) et que \(u(7)=3\). Montrer que, pour tout entier \(n\) impair, non multiple de 3 et supérieur ou égal à \(11, u(n) \leq 1\).

Les carrés de taille \(\mathbf{1

1. Pour tout entier \(n\) impair, on partage le carré \(K_{n}\) en \(n^{2}\) cases carrées de taille 1 et on repère chaque case par un couple \((i, j)\) où \(i\) est le numéro de la ligne et \(j\) le numéro de la colonne en partant de la case inférieure gauche (sur la figure, \(n=5\) ).
   On affecte ensuite à chacune des cases, à partir du couple ( \(i, j\) ) qui la repère, le coefficient -1 si \(i\) et \(j\) sont pairs, 1 si \(i\) et \(j\) sont impairs et 0 sinon.
   a. Exprimer en fonction de \(n\), la somme des coefficients de toutes les cases de \(K_{n}\).
   
   b. Démontrer que, si un carré de taille 3 fait partie d'un pavage du carré \(K_{n}\), alors la somme des coefficients de toutes les cases qu'il recouvre est 3,0 ou -3 .
   c. Quelle est la somme des coefficients des cases d'un carré de taille 2 utilisé dans les mêmes conditions ?
   d. Quelle est la somme des coefficients d'un carré pavé par des carrés de taille 2 ou 3 ?
   e. Conclure que, pour tout entier \(n\) :

• \(u(n)=0\) si \(n\) est un multiple de 2 ou de 3 ;
• \(u(n)=1\) si \(n\) est impair, non multiple de 3 et supérieur ou égal à 11 .
  f. Que vaut \(u\) (2017) ?