Shortlist 2006, C4¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Taiwan
Concepts : Invariants et monovariants · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2006 (avec solutions), p. 25 (page 26 du PDF)
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
Un gâteau a la forme d'un carré \(n \times n\) formé de \(n^2\) carrés unité. Des fraises sont posées sur certains carrés unité, de sorte que chaque ligne et chaque colonne contienne exactement une fraise ; on appelle cette disposition \(\mathcal{A}\).
Soit \(\mathcal{B}\) une autre disposition de ce type. On suppose que tout rectangle de la grille dont un sommet est le coin supérieur gauche du gâteau contient au moins autant de fraises de la disposition \(\mathcal{B}\) que de la disposition \(\mathcal{A}\). Montrer qu'on peut obtenir la disposition \(\mathcal{B}\) à partir de \(\mathcal{A}\) par une suite d'échanges, définis comme suit :
Un échange consiste à choisir un rectangle de la grille ne contenant que deux fraises, situées à ses coins supérieur droit et inférieur gauche, et à déplacer ces deux fraises vers les deux autres coins de ce rectangle.
Énoncé original (anglais)
A cake has the form of an \(n \times n\) square composed of \(n^2\) unit squares. Strawberries lie on some of the unit squares so that each row or column contains exactly one strawberry; call this arrangement \(\mathcal{A}\).
Let \(\mathcal{B}\) be another such arrangement. Suppose that every grid rectangle with one vertex at the top left corner of the cake contains no fewer strawberries of arrangement \(\mathcal{B}\) than of arrangement \(\mathcal{A}\). Prove that arrangement \(\mathcal{B}\) can be obtained from \(\mathcal{A}\) by performing a number of switches, defined as follows:
A switch consists in selecting a grid rectangle with only two strawberries, situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle.
Indices : les idées clés
- Comptages : \(a(X)\) et \(b(X)\) comptent les fraises et les prunes (cible) dans le rectangle \([OX]\) ; par hypothèse \(a(X) \leq b(X)\).
- Monovariant : on cherche un échange qui donne \(a(X) \leq a'(X) \leq b(X)\) partout et \(\sum a' > \sum a\) ; le processus termine puisque la somme est majorée par \(\sum b\).
- Choix de l'échange : dans la ligne la plus haute où fraise \(S\) et prune \(P\) diffèrent, on prend la plus haute fraise \(V\) sous \([PS]\) ; on a \(a(X) < b(X)\) sur \([PR]\), ce qui autorise l'échange de \(S\), \(V\) vers \(U\), \(W\) (récurrence).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2006 (une solution).
Solution¶
On note les cases unités par des lettres majuscules ; \(O\) est la case du coin supérieur gauche. Pour deux cases \(X\) et \(Y\), soit \([XY]\) le plus petit rectangle de la grille contenant ces deux cases.
Les fraises sont sur certaines cases dans la disposition \(\mathcal{A}\). Posons une prune sur chaque case de la configuration cible \(\mathcal{B}\). Pour une case \(X\), notons \(a(X)\) et \(b(X)\) respectivement le nombre de fraises et le nombre de prunes dans \([OX]\). Par hypothèse, \(a(X) \leq b(X)\) pour tout \(X\), avec inégalité stricte pour un certain \(X\) (sinon les deux dispositions coïncident et il n'y a rien à prouver).
L'idée est de montrer que, par un échange légitime, on peut obtenir une disposition \(\mathcal{A}'\) telle que
(avec \(a'(X)\) défini comme \(a(X)\) ; les sommes portent sur toutes les cases \(X\)). Cela suffira, car le même raisonnement s'applique alors à \(\mathcal{A}'\), donnant une nouvelle disposition \(\mathcal{A}''\), et ainsi de suite (récurrence). Comme \(\sum a(X) < \sum a'(X) < \sum a''(X) < \cdots\) et que toutes ces sommes ne dépassent pas \(\sum b(X)\), on obtient finalement une somme dont tous les termes sont égaux aux \(b(X)\) correspondants ; toutes les fraises rejoindront des prunes.
Considérons la ligne la plus haute dans laquelle la prune et la fraise sont sur des cases différentes \(P\) et \(S\) (respectivement) ; évidemment, \(P\) doit être à gauche de \(S\). Dans la colonne passant par \(P\), soit \(T\) la case du haut et \(B\) celle du bas. La fraise de cette colonne est sous la prune (car il n'y a pas de prune dans cette colonne au-dessus de \(P\), et les positions des fraises et des prunes coïncident partout au-dessus de la ligne de \(P\)). Il y a donc au moins une fraise dans la région \([BS]\) sous \([PS]\). Soit \(V\) la position de la plus haute fraise de cette région.

Notons \(W\) la case à l'intersection de la ligne passant par \(V\) et de la colonne passant par \(S\), et soit \(R\) la case voisine de \(W\) par un sommet, en haut à gauche. Montrons que
C'est le cas car, si \(X \in [PR]\), la partie de \([OX]\) à gauche de la colonne \([TB]\) contient au moins autant de prunes que de fraises (hypothèse du problème) ; dans la partie au-dessus de la ligne passant par \(P\) et \(S\), on a un équilibre parfait ; et dans la partie restante, c'est-à-dire le rectangle \([PX]\), on a une prune sur la case \(P\) et aucune fraise.
On peut maintenant effectuer l'échange voulu. Soit \(U\) la case à l'intersection de la ligne passant par \(P\) et de la colonne passant par \(V\) (certaines des cases \(P\), \(U\), \(R\) peuvent coïncider). Déplaçons les fraises des cases \(S\) et \(V\) vers les cases \(U\) et \(W\). Alors
Et comme le rectangle \([UR]\) est contenu dans \([PR]\), on a encore \(a'(X) \leq b(X)\) pour tout \(X\), vu (2) ; les conditions (1) sont vérifiées et la preuve est complète. \(\blacksquare\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2022 C4 ★★☆☆☆ : \(n\) pièces entre \(n\) enfants en cercle ; un enfant peut donner une pièce à chaque voisin : quelles distributions mènent à une pièce chacun ?
- 2025 N5 ★★★☆☆ : Chaque terme d'un triplet augmente du PGCD des deux autres, \(2025\) fois de suite : quelle valeur minimale pour \(a_{2025}\) ?
- 2024 C6 ★★★★☆ : Faire passer une à une les billes \(1, \ldots, 4n\) d'un plateau à l'autre sans trop déséquilibrer la balance : quel écart \(T\) faut-il tolérer ?
- 2009 C8 ★★★★★ : Une opération sur l'écriture décimale qui duplique un bloc de chiffres finit toujours par atteindre \(1\).