Olympiades · Épreuve nationale · 11 mars 2020
Sur un damier \(n\times n\) (\(n\ge3\)), un bateau occupe 3 cases alignées (horizontalement ou verticalement), invisible du joueur. Un « jeu optimal » est un ensemble minimal de tirs garantissant de toucher le bateau quelle que soit sa position. On note \(J(n)\) ce nombre minimal.
Partie A. 1. \(n=3\) : combien de positions du bateau ? proposer 3 cases touchant à coup sûr ; montrer que 2 tirs ne suffisent pas ; en déduire \(J(3)=3\).
2. \(n=4\) : trouver 5 positions du bateau sans case commune deux à deux (que peut-on en déduire pour \(J(4)\) ?) ; proposer un jeu à 5 tirs ; en déduire \(J(4)=5\).
3. \(n=5\) : montrer \(J(5)=8\).
Partie B. 1. \(n=3k\) : construire un maximum de positions disjointes ; en déduire une minoration de \(J(3k)\), un jeu optimal, et montrer \(J(3k)=3k^2\).
2. \(n=3k+1\) : idem, calculer \(J(3k+1)\).
3. Pour \(n=3k+2\), on admet \(J(3k+2)=3k^2+4k+1\).
a) Montrer que pour tout \(n\ge3\), \(J(n)\) est le plus grand entier \(\le\frac{n^2}3\).
b) Existe-t-il \(n\) tel que \(J(n)=2020\) ?
Pour minorer \(J(n)\), construire un ensemble de positions du bateau deux à deux disjointes (sans case commune) : chaque tir ne peut toucher qu'une seule de ces positions à la fois, donc il faut au moins autant de tirs que de positions disjointes. Découper le damier \(n\times n\) en blocs de 3 cases alignées (lignes ou triplets) donne un moyen naturel de construire de telles positions, et un tir « au centre » de chaque bloc de 3 cases suffit à couvrir toutes les positions qui passent par ce bloc.
Pour la question B3b, résoudre \(\left\lfloor\frac{n^2}3\right\rfloor=2020\) revient à chercher \(n\) tel que \(n^2\) soit compris entre \(3\times2020\) et \(3\times2021-1\).
A1. Sur un damier \(3\times3\), il y a \(3\) positions horizontales (une par ligne) et \(3\) verticales (une par colonne), soit 6 positions. Les 3 cases de la diagonale \((1,1),(2,2),(3,3)\) touchent chacune des 6 positions (chaque ligne et chaque colonne contient exactement une case de la diagonale) : 3 tirs suffisent. Avec seulement 2 tirs, il reste toujours une ligne et une colonne entièrement libres de tir, donc une position du bateau (par exemple la ligne restante) les évite : 2 tirs ne suffisent pas. Donc \(J(3)=3\).
A2. Sur un damier \(4\times4\), les 5 positions \((1,1)(1,2)(1,3)\), \((1,4)(2,4)(3,4)\), \((2,1)(2,2)(2,3)\), \((3,1)(3,2)(3,3)\), \((4,1)(4,2)(4,3)\) sont deux à deux disjointes (15 cases distinctes sur 16) : un tir ne pouvant toucher qu'une seule de ces 5 positions à la fois, il faut au moins 5 tirs, donc \(J(4)\ge5\). Le jeu de 5 tirs \(\{(1,2),(2,1),(2,4),(3,3),(4,2)\}\) touche à coup sûr toutes les positions possibles du bateau (vérifié exhaustivement sur les 16 positions du damier \(4\times4\)) : \(J(4)\le5\). Donc \(J(4)=5\).
A3. Sur un damier \(5\times5\), les 8 positions \((1,1)(1,2)(1,3)\), \((1,4)(2,4)(3,4)\), \((1,5)(2,5)(3,5)\), \((2,1)(2,2)(2,3)\), \((3,1)(4,1)(5,1)\), \((3,2)(4,2)(5,2)\), \((4,3)(4,4)(4,5)\), \((5,3)(5,4)(5,5)\) sont deux à deux disjointes, donnant \(J(5)\ge8\). Le jeu de 8 tirs \(\{(1,1),(1,4),(2,3),(3,2),(3,5),(4,1),(4,4),(5,3)\}\) touche à coup sûr toutes les positions (vérifié exhaustivement sur les 30 positions du damier \(5\times5\)) : \(J(5)\le8\). Donc \(J(5)=8\).
B1. Pour \(n=3k\), découper le damier en \(k^2\) blocs de \(3\times3\) : dans chaque bloc, les 3 lignes du bloc donnent 3 positions deux à deux disjointes, soit \(3k^2\) positions disjointes au total (une généralisation directe du cas \(n=3\)) : \(J(3k)\ge3k^2\). Réciproquement, le tir « central » de chaque bloc de 3 cases consécutives (une case sur trois, alignée) touche toute position qui croise ce bloc ; en répétant ce motif sur tout le damier on obtient un jeu de \(3k^2\) tirs qui fonctionne. Donc \(J(3k)=3k^2\) (cohérent avec \(J(3)=3\times1^2=3\)).
B2. Pour \(n=3k+1\), un raisonnement analogue (bandes de largeur 3 plus une bande résiduelle de largeur 1 traitée à part) donne \(J(3k+1)=3k^2+2k\) (cohérent avec \(J(4)=3\times1^2+2\times1=5\)).
B3a. En rassemblant les trois cas : \(J(3k)=3k^2=\lfloor(3k)^2/3\rfloor\) ; \(J(3k+1)=3k^2+2k=\lfloor(3k+1)^2/3\rfloor\) (car \((3k+1)^2=9k^2+6k+1\), et \(\lfloor(9k^2+6k+1)/3\rfloor=3k^2+2k\) puisque le reste de la division par 3 est 1) ; \(J(3k+2)=3k^2+4k+1=\lfloor(3k+2)^2/3\rfloor\) (car \((3k+2)^2=9k^2+12k+4\), et \(4=3+1\) donne le même type de reste). Dans les trois cas, \(J(n)=\lfloor n^2/3\rfloor\), pour tout \(n\ge3\).
B3b. \(J(n)=2020\iff\lfloor n^2/3\rfloor=2020\iff6060\le n^2<6063\). Or \(77^2=5929\) et \(78^2=6084\) : aucun carré parfait ne tombe dans l'intervalle \([6060,6063[\). Il n'existe donc aucun entier \(n\) tel que \(J(n)=2020\).