Shortlist 2010, C3

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Russia

Concepts : Coloriages et pavages · Principe des tiroirs

Solution officielle : Shortlist officielle 2010 (avec solutions), p. 27 (page 28 du PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

\(2500\) chess kings have to be placed on a \(100 \times 100\) chessboard so that

(i) no king can capture any other one (i.e. no two kings are placed in two squares sharing a common vertex);

(ii) each row and each column contains exactly \(25\) kings.

Find the number of such arrangements. (Two arrangements differing by rotation or symmetry are supposed to be different.)

Indices : les idées clés

• Blocs \(2 \times 2\) : chaque bloc contient au plus un roi, donc, par les tiroirs, exactement un ; on note T/B et L/R la demi-position du roi dans son bloc.
• Propagation : un B-bloc force un B-bloc en dessous, un T-bloc un T-bloc au-dessus ; d'où \(25\) colonnes B, \(25\) colonnes T, \(25\) lignes L, \(25\) lignes R.
• Frontière : à la jonction d'une colonne T et d'une colonne B voisines, les lignes L sont toutes en bas (ou toutes en haut) ; il ne reste que deux dispositions.

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2010 (une solution).

Réponse : il y a deux telles dispositions.

Solution

Supposons qu'on ait une disposition vérifiant les conditions du problème. Découpons l'échiquier en morceaux \(2 \times 2\), qu'on appelle blocs. Chaque bloc contient au plus un roi (sinon ces deux rois s'attaqueraient) ; donc, par le principe des tiroirs, chaque bloc contient exactement un roi.

Associons maintenant à chaque bloc la lettre T ou B selon que le roi est dans sa moitié haute ou basse. De même, associons à chaque bloc la lettre L ou R selon que le roi est dans sa moitié gauche ou droite. On définit ainsi des T-blocs, B-blocs, L-blocs et R-blocs. On combine aussi les lettres : un bloc est un TL-bloc s'il est à la fois T-bloc et L-bloc ; on définit de même les TR-blocs, BL-blocs et BR-blocs. La disposition des blocs détermine de façon unique la disposition des rois ; dans la suite, on considère donc le système de \(50 \times 50\) blocs (voir figure 1). On repère les blocs par des couples de coordonnées : le couple \((i, j)\), avec \(1 \leq i, j \leq 50\), désigne le \(j\)-ième bloc de la \(i\)-ième ligne (ou le \(i\)-ième bloc de la \(j\)-ième colonne). Le bloc en haut à gauche est \((1, 1)\).

Le système de blocs a les propriétés suivantes.

(i') Si \((i, j)\) est un B-bloc, alors \((i + 1, j)\) est un B-bloc : sinon les rois de ces deux blocs pourraient se prendre. De même, si \((i, j)\) est un T-bloc, alors \((i - 1, j)\) est un T-bloc ; si \((i, j)\) est un L-bloc, alors \((i, j - 1)\) est un L-bloc ; si \((i, j)\) est un R-bloc, alors \((i, j + 1)\) est un R-bloc.

(ii') Chaque colonne contient exactement \(25\) L-blocs et \(25\) R-blocs, et chaque ligne contient exactement \(25\) T-blocs et \(25\) B-blocs. En particulier, le nombre total de L-blocs (ou de R-blocs, T-blocs, B-blocs) vaut \(25 \cdot 50 = 1250\).

Considérons un B-bloc de la forme \((1, j)\). D'après (i'), tous les blocs de la \(j\)-ième colonne sont des B-blocs ; on appelle une telle colonne une colonne B. D'après (ii'), la première ligne contient \(25\) B-blocs, d'où \(25\) colonnes B. Ces \(25\) colonnes B contiennent \(1250\) B-blocs, donc tous les blocs des autres colonnes sont des T-blocs, et l'on obtient \(25\) colonnes T. De même, il y a exactement \(25\) lignes L et exactement \(25\) lignes R.

Considérons maintenant une colonne T et une colonne B voisines quelconques (colonnes de numéros \(j\) et \(j + 1\)).

Cas 1. Supposons que la \(j\)-ième colonne soit une colonne T et la \((j + 1)\)-ième une colonne B. Considérons un indice \(i\) tel que la \(i\)-ième ligne soit une ligne L ; alors \((i, j + 1)\) est un BL-bloc. Par conséquent, \((i + 1, j)\) ne peut pas être un TR-bloc (voir figure 2), donc \((i + 1, j)\) est un TL-bloc, et la \((i + 1)\)-ième ligne est une ligne L. En choisissant pour \(i\) la ligne L la plus haute, on obtient de proche en proche que toutes les lignes de la \(i\)-ième à la \(50\)-ième sont des lignes L. Comme il y a exactement \(25\) lignes L, il s'ensuit que les lignes \(1\) à \(25\) sont des lignes R, et les lignes \(26\) à \(50\) des lignes L.

Considérons maintenant la ligne R et la ligne L voisines (les lignes de numéros \(25\) et \(26\)). En échangeant lignes et colonnes dans le raisonnement précédent, les colonnes \(1\) à \(25\) sont des colonnes T, et les colonnes \(26\) à \(50\) des colonnes B. On a donc une disposition unique des blocs qui mène à une disposition des rois vérifiant la condition du problème (voir figure 3).

Cas 2. Supposons que la \(j\)-ième colonne soit une colonne B et la \((j + 1)\)-ième une colonne T. En reprenant les arguments du cas 1, on obtient que les lignes \(1\) à \(25\) sont des lignes L (et toutes les autres des lignes R), et que les colonnes \(1\) à \(25\) sont des colonnes B (et toutes les autres des colonnes T) ; on trouve donc exactement une disposition de plus (voir figure 4). \(\blacksquare\)