Shortlist 2023, C4¶

Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : U.S.A.

Concepts : Graphes : degrés, chemins, arbres · Invariants et monovariants · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2023 (avec solutions), p. 42 (page 44 du PDF)

Énoncé¶

Let \(n \geq 2\) be a positive integer. Paul has a \(1 \times n^2\) rectangular strip consisting of \(n^2\) unit squares, where the \(i\)-th square is labelled with \(i\) for all \(1 \leq i \leq n^2\). He wishes to cut the strip into several pieces, where each piece consists of a number of consecutive unit squares, and then translate (without rotating or flipping) the pieces to obtain an \(n \times n\) square satisfying the following property: if the unit square in the \(i\)-th row and \(j\)-th column is labelled with \(a_{ij}\), then \(a_{ij} - (i + j - 1)\) is divisible by \(n\).

Determine the smallest number of pieces Paul needs to make in order to accomplish this.

Indices : les idées clés

Travailler modulo \(n\) et à l'envers : les étiquettes ne comptent que modulo \(n\) ; la ligne \(k\) du carré se lit \(k, k+1, \ldots, k+n-1\), et l'on cherche à reconstituer la bande à partir de ces \(n\) lignes.
Graphes (solution 1) : un morceau \(a, a+1, \ldots, b-1\) devient une arête \(a\)–\(b\) ; le graphe obtenu a un cycle eulérien, donc est connexe, et reste connexe après suppression d'une arête dans chacun des \(n\) cycles disjoints : il a au moins \((n-1) + n\) arêtes.
Invariants et monovariants (solution 2) : avec des bandes circulaires, chaque suppression de « couture » modifie le nombre de bandes d'au plus \(1\).
Récurrence sur \(n\) (solution 3) : on démontre plus fort, « \(k\) bandes circulaires demandent au moins \(2n - k\) coupes », en fusionnant les cases \(m\) et \(m+1\) lorsque la frontière \(m \mid m+1\) n'est coupée qu'une fois.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2023 (trois solutions).

Réponse. Le nombre minimal de morceaux est \(2n - 1\).

Solution 1¶

Dans toute la solution, on considère les étiquettes comme des éléments de \(\mathbb{Z}/n\mathbb{Z}\), car seules leurs valeurs modulo \(n\) comptent.

Constructions avec \(2n - 1\) morceaux.

Découper en morceaux de tailles \(n, 1, n, 1, \ldots, n, 1, 1\), et recoller les morceaux de taille \(1\) pour former la dernière ligne.
Découper en morceaux de tailles \(n, 1, n-1, 2, n-2, \ldots, n-1, 1\), et échanger les paires de bandes consécutives dont les tailles ont pour somme \(n\).

Optimalité. Il est plus commode de penser au processus inverse : on part de \(n\) morceaux de taille \(1 \times n\), le \(k\)-ième portant les étiquettes \(k, k+1, \ldots, k+n-1\) (c'est la ligne \(k\) du carré), et l'on veut reconstituer la bande \(1 \times n^2\) d'origine.

Après découpage, chaque morceau est de la forme \(a, a+1, \ldots, b-1\). On construit un graphe \(\Gamma\) (non orienté, pas forcément simple) de sommets \(1, \ldots, n\), où un morceau \(a, a+1, \ldots, b-1\) correspond à une arête entre \(a\) et \(b\). On observe que :

les morceaux issus du \(k\)-ième morceau initial \(k, k+1, \ldots, k+n-1\) forment un cycle \(\gamma_k\) (éventuellement de longueur \(1\)) passant par le sommet \(k\) ;
comme on peut réarranger les morceaux en une seule bande \(1 \times n^2\), le graphe \(\Gamma\) possède un cycle eulérien ;
le nombre d'arêtes de \(\Gamma\) est égal au nombre total de morceaux.

Il s'agit de montrer que \(\Gamma\) a au moins \(2n - 1\) arêtes. Ayant un cycle eulérien, \(\Gamma\) est connexe. Pour chaque \(1 \leq k \leq n\), choisissons une arête de \(\gamma_k\) et supprimons-la ; on obtient un graphe \(\Gamma'\). Comme deux cycles \(\gamma_i\) et \(\gamma_j\) n'ont pas d'arête commune, retirer une arête de chaque cycle ne détruit pas la connexité : \(\Gamma'\) est encore connexe. Un graphe connexe à \(n\) sommets a au moins \(n - 1\) arêtes, donc \(\Gamma'\) a au moins \(n - 1\) arêtes et \(\Gamma\) en a au moins \(2n - 1\). \(\blacksquare\)

Solution 2¶

On donne une autre preuve de la minoration. Au lieu d'une bande linéaire, on travaille avec plusieurs bandes circulaires, chacune de longueur multiple de \(n\) et étiquetée

\[1, 2, \ldots, n, 1, 2, \ldots, n, \ldots, 1, 2, \ldots, n,\]

avec \(n^2\) cases au total. Le but reste de former le carré \(n \times n\) par découpage et translation (on imagine que chaque case porte un nombre écrit, qui doit apparaître droit et non retourné dans le carré final). Le nombre de coupes est égal au nombre de morceaux, car \(l \geq 1\) coupes sur une bande circulaire donnent \(l\) morceaux. (La bande linéaire \(1 \times n^2\) correspond à une bande circulaire dans laquelle la frontière entre \(n^2\) et \(1\) est coupée.)

Considérons une « couture » à l'intérieur du carré final, entre deux cases \(S\) et \(T\) appartenant à deux morceaux différents. On cherche à la supprimer.

Si \(S\) et \(T\) proviennent de la même bande circulaire et y sont adjacentes, la coupe était inutile : on supprime la couture, ce qui économise une coupe. Les bandes circulaires ne changent pas.
Sinon, \(S\) et \(T\) sont chacune voisine d'une coupe (sur la même bande circulaire ou sur deux bandes différentes) ; notons ces coupes \((S|Y)\) et \((X|T)\). On effectue ces deux coupes, puis on recolle selon \((S|T)\) et \((X|Y)\). Cette opération coupe une bande circulaire en deux ou en fusionne deux en une : le nombre de bandes circulaires varie d'au plus \(1\). On peut alors supprimer la coupe \((S|T)\), devenue inutile, ce qui supprime la couture correspondante dans le carré final.

En itérant, on aboutit à une situation où le carré \(n \times n\) n'a plus aucune couture intérieure. Comme on ne peut pas recoller deux lignes du carré en respectant la numérotation consécutive, il y a alors exactement \(n\) bandes circulaires de longueur \(n\), et il faut au moins \(n\) coupes pour former le carré. Chaque suppression de couture a modifié le nombre de bandes circulaires d'au plus \(1\) (monovariant) ; en partant d'une seule bande circulaire, on a donc supprimé au moins \(n - 1\) coutures, chacune économisant une coupe. Au total, il faut au moins \(n + (n - 1) = 2n - 1\) coupes pour transformer une bande circulaire en le carré, donc au moins \(2n - 1\) morceaux. \(\blacksquare\)

Solution 3¶

Comme dans la solution 2, on travaille avec des bandes circulaires : on part de \(k\) bandes circulaires, chacune de longueur multiple de \(n\) et étiquetée \(1, 2, \ldots, n, 1, 2, \ldots, n, \ldots\), avec \(n^2\) cases au total.

Affirmation. Construire le carré \(n \times n\) demande au moins \(2n - k\) coupes (ou, ce qui revient au même, \(2n - k\) morceaux).

Preuve. Par récurrence sur \(n\). Le cas \(n = 1\) est clair : on a forcément \(k = 1\), et la seule façon d'obtenir un carré \(1 \times 1\) à partir d'une bande circulaire \(1 \times 1\) est de faire une coupe. Supposons \(n \geq 2\) et l'énoncé vrai pour \(n - 1\).

Chaque coupe sépare une case d'étiquette \(i\) (à gauche) d'une case d'étiquette \(i + 1\) (à droite), pour un unique \(1 \leq i \leq n\). Soit \(a_i\) le nombre de telles coupes ; le nombre total de coupes est \(a_1 + \cdots + a_n\). Comme tous les bords gauches et droits du carré final doivent être coupés, \(a_i \geq 1\) pour tout \(i\). Si \(a_i \geq 2\) pour tout \(i\), alors \(a_1 + \cdots + a_n \geq 2n > 2n - k\) et il n'y a rien à montrer. On suppose donc qu'il existe \(1 \leq m \leq n\) avec \(a_m = 1\). Cette unique coupe forme les deux extrémités de la ligne

\[m + 1, m + 2, \ldots, m - 1 + n, m + n\]

du carré final. Deux cas se présentent.

Cas 1 : cette ligne est d'un seul morceau. Elle provient alors d'une bande circulaire de longueur exactement \(n\), que l'on retire du processus. Par définition de \(m\), aucune frontière entre une case \(m\) et une case \(m + 1\) n'est coupée ailleurs ; on peut donc considérer chaque paire de cases adjacentes \(m\), \(m + 1\) comme une seule case. L'hypothèse de récurrence (avec \(n - 1\) et \(k - 1\) bandes) donne

\[a_1 + \cdots + a_{m-1} + a_{m+1} + \cdots + a_n \geq 2(n-1) - (k-1),\]

et en rajoutant \(a_m = 1\) :

\[a_1 + \cdots + a_n \geq 2(n-1) - (k-1) + 1 = 2n - k.\]

Cas 2 : cette ligne est formée de \(l \geq 2\) morceaux \(C_1, \ldots, C_l\). Si l'on coupe les bandes circulaires initiales aux deux extrémités de chacun des morceaux \(C_1, \ldots, C_l\) puis qu'on retire ces morceaux, il reste au plus \(k + l - 2\) morceaux connexes (certains circulaires, d'autres linéaires). En effet, \(C_l\) et \(C_1\) forment un bloc de cases consécutives d'une bande circulaire (la ligne n'est coupée qu'à la frontière \(m \mid m + 1\)), et retirer \(l - 1\) blocs de cases consécutives de \(k\) bandes circulaires laisse au plus \(k + (l - 1) - 1\) morceaux connexes. On recolle ces morceaux à leurs extrémités pour reformer des bandes circulaires ; soit \(k'\) leur nombre, de sorte que \(k' \leq k + l - 2\). Là encore, pour passer de ces bandes aux \(n - 1\) lignes restantes de taille \(1 \times n\), on ne coupe jamais à une frontière entre \(m\) et \(m + 1\) ; l'hypothèse de récurrence s'applique, et le nombre total de morceaux est au moins

\[l + \big(2(n-1) - k'\big) \geq l + 2(n-1) - (k + l - 2) = 2n - k.\]

Ceci achève la récurrence. \(\square\)

Avec \(k = 1\), il faut au moins \(2n - 1\) morceaux pour former le carré \(n \times n\) à partir d'une bande circulaire \(1 \times n^2\) ; donc former le carré à partir de la bande linéaire \(1 \times n^2\) demande aussi au moins \(2n - 1\) morceaux. \(\blacksquare\)