Shortlist 2007, C5¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Romania
Concepts : Coloriages et pavages · Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2007 (avec solutions), p. 32 (page 33 du PDF)
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
In the Cartesian coordinate plane define the strip \(S_n = \{(x, y) \mid n \leq x < n + 1\}\) for every integer \(n\). Assume that each strip \(S_n\) is colored either red or blue, and let \(a\) and \(b\) be two distinct positive integers. Prove that there exists a rectangle with side lengths \(a\) and \(b\) such that its vertices have the same color.
Indices : les idées clés
- Rectangles alignés : sinon \(S_n\) et \(S_{n+a}\), ainsi que \(S_n\) et \(S_{n+b}\), ont des couleurs opposées ; d'où, avec \(d = \gcd(a, b)\) et \(a = a_1d\), \(b = b_1d\), \(a_1\) et \(b_1\) impairs, et une coloration périodique de période \(2d\) (Bézout).
- Rectangle incliné : on place le côté \(AB\) de sorte que sa projection sur l'axe des \(x\) ait longueur \(2d\) ; alors \(A\), \(B\) ont la même couleur, ainsi que \(C\), \(D\).
- Irrationalité : avec \(\varphi = \sqrt{a_1^2 - 4}\) irrationnel, un intervalle de longueur \(w\) (plus longue suite de bandes de même couleur) rencontre \(w + 1\) bandes, ce qui permet d'ajuster \(A\) et \(D\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2007 (une solution et une remarque).
Solution¶
Si \(S_n\) et \(S_{n+a}\) ont la même couleur pour un certain entier \(n\), on peut choisir le rectangle de sommets \((n, 0) \in S_n\), \((n, b) \in S_n\), \((n + a, 0) \in S_{n+a}\) et \((n + a, b) \in S_{n+a}\), et c'est terminé. On peut donc supposer que \(S_n\) et \(S_{n+a}\) ont des couleurs opposées pour tout \(n\).
De même, on peut supposer que \(S_n\) et \(S_{n+b}\) ont des couleurs opposées. Alors, par récurrence sur \(\lvert p \rvert + \lvert q \rvert\), on obtient que, pour des entiers \(p\) et \(q\) quelconques, les bandes \(S_n\) et \(S_{n+pa+qb}\) ont la même couleur si \(p + q\) est pair, et des couleurs opposées si \(p + q\) est impair.
Soient \(d = \gcd(a, b)\), \(a_1 = a/d\) et \(b_1 = b/d\). Appliquons le résultat ci-dessus pour \(p = b_1\) et \(q = -a_1\). Les bandes \(S_0\) et \(S_{0 + b_1a - a_1b}\) sont identiques et ont donc la même couleur. Donc \(a_1 + b_1\) est pair. Par construction, \(a_1\) et \(b_1\) sont premiers entre eux, ce qui n'est possible que s'ils sont tous deux impairs.
Sans perte de généralité, on peut supposer \(a > b\). Alors \(a_1 > b_1 \geq 1\), donc \(a_1 \geq 3\).
Choisissons des entiers \(k\) et \(\ell\) tels que \(ka_1 - \ell b_1 = 1\), de sorte que \(ka - \ell b = d\). Comme \(a_1\) et \(b_1\) sont impairs, \(k + \ell\) l'est aussi. Donc, pour tout entier \(n\), les bandes \(S_n\) et \(S_{n+ka-\ell b} = S_{n+d}\) ont des couleurs opposées. Cela implique aussi que la coloration est périodique de période \(2d\), c'est-à-dire que les bandes \(S_n\) et \(S_{n+2d}\) ont la même couleur pour tout \(n\).
Construisons le rectangle voulu \(ABCD\) avec \(AB = CD = a\) et \(BC = AD = b\), dans une position où le sommet \(A\) est sur l'axe des \(x\) et où la projection du côté \(AB\) sur l'axe des \(x\) est de longueur \(2d\) (voir figure 1). C'est possible puisque \(a = a_1d > 2d\). Les coordonnées des sommets sont de la forme
Posons \(\varphi = \sqrt{a_1^2 - 4}\). Par le théorème de Pythagore,
Par les triangles semblables \(ADD_0\) et \(BAB_0\), on a la contrainte
sur les nombres \(t\) et \(u\). Le calcul de \(y_2\) et \(y_3\) n'est pas nécessaire, puisqu'ils n'ont pas d'effet sur les couleurs.
Remarquons que le nombre \(\varphi\) est irrationnel, car \(\varphi^2\) est entier mais \(\varphi\) ne l'est pas : \(a_1 > \varphi \geq \sqrt{a_1^2 - 2a_1 + 2} > a_1 - 1\).
Par la périodicité, les points \(A\) et \(B\) ont la même couleur ; de même, \(C\) et \(D\) ont la même couleur. De plus, ces couleurs ne dépendent que des valeurs de \(t\) et \(u\). Il suffit donc de choisir \(t\) et \(u\) de sorte que les sommets \(A\) et \(D\) aient la même couleur.
Soit \(w\) le plus grand entier strictement positif tel qu'il existe \(w\) bandes consécutives \(S_{n_0}, S_{n_0+1}, \ldots, S_{n_0+w-1}\) de même couleur, disons rouge. (Comme \(S_{n_0+d}\) doit être bleue, on a \(w \leq d\).) Choisissons \(t\) dans l'intervalle \((n_0, n_0 + w)\).
Considérons l'intervalle \(I = \left(n_0 + \frac{bd}{a}\varphi, n_0 + \frac{bd}{a}\varphi + w\right)\) de l'axe des \(x\) (voir figure 2). Sa longueur est \(w\), et ses extrémités sont irrationnelles. Cet intervalle rencontre donc \(w + 1\) bandes consécutives. Comme au plus \(w\) bandes consécutives peuvent avoir la même couleur, l'intervalle \(I\) doit contenir des points rouges et des points bleus. Choisissons \(u \in I\) tel que la droite \(x = u\) soit rouge, et posons \(t = u - \frac{bd}{a}\varphi\), conformément à la contrainte (1). Alors \(t \in (n_0, n_0 + w)\), et \(A = (t, 0)\) est rouge, de même que \(D = (u, y_3)\).
On peut donc choisir \(u\) et \(t\) de sorte qu'ils donnent un rectangle aux quatre sommets rouges. \(\blacksquare\)
Remarque¶
L'énoncé est faux pour les carrés, c'est-à-dire dans le cas \(a = b\). Si, pour tout entier \(k\), les bandes \(S_{2ka}, S_{2ka+1}, \ldots, S_{(2k+1)a-1}\) sont rouges et les bandes \(S_{(2k+1)a}, S_{(2k+1)a+1}, \ldots, S_{(2k+2)a-1}\) sont bleues, alors chaque carré de côté \(a \times a\) a au moins un sommet rouge et au moins un sommet bleu.