Shortlist 2014, C3

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

Concepts : Principe des tiroirs · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 30 (page 31 du PDF)

Problème 2 de l'OIM 2014

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2014, où il était le problème 2 (jour 1).

Figures reprises du livret officiel de la Shortlist.

Énoncé

Let \(n \geq 2\) be an integer. Consider an \(n \times n\) chessboard divided into \(n^2\) unit squares. We call a configuration of \(n\) rooks on this board happy if every row and every column contains exactly one rook. Find the greatest positive integer \(k\) such that for every happy configuration of rooks, we can find a \(k \times k\) square without a rook on any of its \(k^2\) unit squares.

Indices : les idées clés

• Reformuler : pour \(\ell \geq 1\), montrer que si \(n > \ell^2\) il y a toujours un carré \(\ell \times \ell\) vide, et que si \(n \leq \ell^2\) il existe une configuration sans carré \(\ell \times \ell\) vide.
• Tiroirs : \(\ell\) lignes consécutives, dont celle de la tour placée dans la première colonne, privées de leurs \(n - \ell^2\) premières colonnes, forment \(\ell\) carrés \(\ell \times \ell\) pour au plus \(\ell - 1\) tours.
• Construction pour \(n = \ell^2\) : tours en \((i\ell + j, j\ell + i)\) ; les colonnes des tours de \(\ell\) lignes consécutives sont espacées d'au plus \(\ell\). Puis on retire des lignes et des colonnes pour \(n < \ell^2\).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2014 (une solution et une remarque).

Solution

Réponse : \(k = \left\lfloor \sqrt{n - 1} \right\rfloor\).

Soit \(\ell\) un entier strictement positif. On va montrer que (i) si \(n > \ell^2\), toute configuration heureuse contient un carré \(\ell \times \ell\) vide, et que (ii) si \(n \leq \ell^2\), il existe une configuration heureuse sans carré \(\ell \times \ell\) vide. Ces deux énoncés donnent la réponse.

(i) Supposons \(n > \ell^2\) et considérons une configuration heureuse. Il existe une ligne \(R\) dont la tour est dans la case la plus à gauche. Prenons \(\ell\) lignes consécutives dont \(R\). Leur réunion \(U\) contient exactement \(\ell\) tours. Retirons de \(U\) les \(n - \ell^2 \geq 1\) colonnes les plus à gauche (on retire ainsi au moins une tour). La partie restante est un rectangle \(\ell^2 \times \ell\), qui se découpe en \(\ell\) carrés \(\ell \times \ell\), et elle contient au plus \(\ell - 1\) tours. L'un de ces carrés est donc vide.

(ii) Supposons maintenant \(n \leq \ell^2\). On construit d'abord une configuration heureuse sans carré \(\ell \times \ell\) vide dans le cas \(n = \ell^2\), puis on la modifie pour les valeurs plus petites de \(n\).

Numérotons les lignes de bas en haut, et les colonnes de gauche à droite, par \(0, 1, \ldots, \ell^2 - 1\). Chaque case est repérée par le couple \((r, c)\) de ses numéros de ligne et de colonne. Plaçons les tours sur toutes les cases de la forme \((i\ell + j, j\ell + i)\) avec \(i, j = 0, 1, \ldots, \ell - 1\) (la figure représente cette disposition pour \(\ell = 3\)). Comme tout nombre de \(0\) à \(\ell^2 - 1\) s'écrit de manière unique \(i\ell + j\) avec \(0 \leq i, j \leq \ell - 1\), chaque ligne et chaque colonne contient exactement une tour.

Montrons que tout carré \(A\) de taille \(\ell \times \ell\) contient une tour. Considérons \(\ell\) lignes consécutives dont la réunion contient \(A\), et soit \(p\ell + q\) le numéro de la plus basse, avec \(0 \leq p, q \leq \ell - 1\) (on a \(p\ell + q \leq \ell^2 - \ell\)). Les tours de cette réunion sont dans les colonnes \(q\ell + p, (q+1)\ell + p, \ldots, (\ell - 1)\ell + p\), et \(p + 1, \ell + (p + 1), \ldots, (q - 1)\ell + (p + 1)\), soit, dans l'ordre croissant,

\[p + 1, \; \ell + (p + 1), \; \ldots, \; (q - 1)\ell + (p + 1), \; q\ell + p, \; (q + 1)\ell + p, \; \ldots, \; (\ell - 1)\ell + p.\]

On vérifie que le premier nombre de cette liste est au plus \(\ell - 1\) (si \(p = \ell - 1\), alors \(q = 0\) et le premier nombre est \(q\ell + p = \ell - 1\)), que le dernier est au moins \((\ell - 1)\ell\), et que deux nombres consécutifs diffèrent d'au plus \(\ell\). Donc l'une des \(\ell\) colonnes consécutives qui rencontrent \(A\) figure dans la liste, et la tour de cette colonne est dans \(A\). La construction pour \(n = \ell^2\) est établie.

Il reste à construire, pour \(n < \ell^2\), une configuration heureuse sans carré \(\ell \times \ell\) vide. On part de la construction pour l'échiquier \(\ell^2 \times \ell^2\) et l'on retire les \(\ell^2 - n\) lignes du bas et les \(\ell^2 - n\) colonnes de droite. On obtient une disposition sans carré \(\ell \times \ell\) vide, mais certaines lignes et colonnes peuvent être vides. Le nombre de lignes vides est égal au nombre de colonnes vides ; on peut donc les mettre en bijection, et placer une tour à l'intersection de chaque ligne vide et de la colonne vide qui lui correspond. \(\blacksquare\)

Remarque

La partie (i) admet plusieurs preuves. Par exemple, dans le dernier paragraphe, il suffit de traiter le cas \(n = \ell^2 + 1\). Parmi les quatre cases des coins, au moins une est vide ; les tours de sa ligne et de sa colonne sont donc distinctes. En supprimant cette ligne et cette colonne, on obtient un carré \(\ell^2 \times \ell^2\) contenant \(\ell^2 - 1\) tours. Ce carré se découpe en \(\ell^2\) carrés \(\ell \times \ell\), donc l'un d'eux est vide.