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é¶
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\)