Sujet n°1 : Optimisation du découpage de l'échiquier.
Nb d'élèves : 7

[Rédaction des éditeurs] On prend une grille carrée (ou rectangulaire...) comportant nxn cases blanches (par exemple n=8). En noircissant des cases de cette grille, on forme des régions blanches séparées par des cases noires : deux régions blanches distinctes n'ont pas de coté de case en commun , mais peuvant avoir un coin en commun.

On s'impose que chacune des régions blanches obtenues comporte au plus k cases blanches (par exemple k=4).

• Quel sera le nombre minimum de cases de la grille à noircir ?

Référence. Ce problème revient à chercher à exlure le placement sur un échiquier carré des polyminos de taille k+1 sur en interdisant le moins possible de cases. Le cas de l'échiquier 8x8 se trouve dans le fameux livre de Solomon W. Golomb sur les polyminos (p. 27) :
Solomon W. Golomb, Polyominoes, puzzles, patterns, problems, and packings, 2nd ed. , Princeton Univ. Press, 1994. 184p.

Remarque : le sujet a une certaine parenté avec un problème de "composantes connexes" traité par le jumelage Mérignac & Pessac au congrès MATh.en.JEANS 2003 : cf. Décomposition de grilles en composantes connexes.