Shortlist 2017, C1

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

Concepts : Coloriages et pavages · Invariants et monovariants

Solution officielle : Shortlist officielle 2017 (avec solutions), p. 34 (page 36 du PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

A rectangle \(\mathcal{R}\) with odd integer side lengths is divided into small rectangles with integer side lengths. Prove that there is at least one among the small rectangles whose distances from the four sides of \(\mathcal{R}\) are either all odd or all even.

Indices : les idées clés

• Coloriage en damier des \(ab\) cases unités : les quatre coins de \(\mathcal{R}\) ont la même couleur.
• Classer les rectangles selon la couleur de leurs coins : un rectangle « mixte » a autant de cases de chaque couleur ; un rectangle « vert » a une case verte de plus.
• Compter les écarts : la différence (verts \(-\) jaunes) vaut \(1\) pour \(\mathcal{R}\) ; elle est additive, donc au moins un petit rectangle est vert, et ses coins verts imposent la parité des quatre distances.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2017 (une solution).

Solution 1

Soient \(a\) et \(b\) la largeur et la hauteur (impaires) de \(\mathcal{R}\). Découpons \(\mathcal{R}\) en \(ab\) carrés unités et faisons un coloriage en damier vert et jaune. Comme \(a\) et \(b\) sont impairs, les quatre cases des coins de \(\mathcal{R}\) ont la même couleur, disons verte.

Appelons un rectangle (que ce soit \(\mathcal{R}\) ou un petit rectangle) vert si les cases de ses quatre coins sont vertes, jaune si elles sont toutes jaunes, et mixte s'il a des coins des deux couleurs. En particulier, \(\mathcal{R}\) est vert. On utilise les observations évidentes suivantes :

• un rectangle mixte (un de ses côtés est pair) contient autant de cases vertes que de cases jaunes ;
• un rectangle vert (côtés impairs) contient une case verte de plus que de cases jaunes ;
• un rectangle jaune contient une case jaune de plus que de cases vertes.

Le rectangle \(\mathcal{R}\) est vert, donc il contient plus de cases vertes que de cases jaunes. En additionnant sur les petits rectangles, l'un au moins d'entre eux est donc vert.

Soit \(S\) un tel petit rectangle vert, et soient \(x, y, u, v\) ses distances aux côtés de \(\mathcal{R}\) (\(x\) à gauche, \(y\) à droite, \(u\) en haut, \(v\) en bas ; voir la figure). La case du coin supérieur gauche de \(\mathcal{R}\) et celle du coin supérieur gauche de \(S\) ont la même couleur si et seulement si \(x + u\) est pair, c'est-à-dire si \(x\) et \(u\) ont la même parité. De même, les trois autres coins verts de \(S\) montrent que \(x\) et \(v\) ont même parité, et que \(y\) et \(u\) ont même parité. Donc \(x, y, u, v\) sont tous impairs ou tous pairs. \(\blacksquare\)