Shortlist 2010, C7¶
Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : Germany
Concepts : Graphes : degrés, chemins, arbres · Théorème des restes chinois · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2010 (avec solutions), p. 38 (page 39 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(P_1, \ldots, P_s\) be arithmetic progressions of integers, the following conditions being satisfied:
(i) each integer belongs to at least one of them;
(ii) each progression contains a number which does not belong to other progressions.
Denote by \(n\) the least common multiple of steps of these progressions; let \(n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}\) be its prime factorization. Prove that
Indices : les idées clés
- Grille : en écrivant le reste de \(m\) modulo chaque \(p_i^{\alpha_i}\) en base \(p_i\), on obtient une bijection (restes chinois) de \(\{0, \ldots, n - 1\}\) sur une grille \(p_1 \times \cdots \times p_1 \times \cdots \times p_k \times \cdots \times p_k\), où chaque progression devient une sous-grille.
- Lemme de recouvrement : si des sous-grilles recouvrent une grille \(n_1 \times \cdots \times n_k\), chacune ayant un point propre, et si chaque axe a une sous-grille orthogonale, alors \(s \geq 1 + \sum (n_i - 1)\) ; preuve par le lemme de Hall sur un graphe biparti.
- Solution 2 : un énoncé plus général, prouvé par un contre-exemple minimal (récurrence sur \(n\) puis sur \(\sum d_i\)), en remplaçant une progression de pas composé \(d_1\) par une progression de pas \(d_1/p_1\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2010 (deux solutions et deux remarques).
Solution 1¶
On prouve d'abord le lemme clé, puis on montre comment l'appliquer pour terminer la solution.
Soient \(n_1, \ldots, n_k\) des entiers strictement positifs. On appelle grille \(n_1 \times n_2 \times \cdots \times n_k\) l'ensemble \(N = \{(a_1, \ldots, a_k) : a_i \in \mathbb{Z}, \ 0 \leq a_i \leq n_i - 1\}\) ; ses éléments sont appelés points. Dans cette grille, on appelle sous-grille une partie de la forme
où \(I = \{i_1, \ldots, i_t\}\) est un ensemble d'indices non vide quelconque, et \(x_{i_j} \in [0, n_{i_j} - 1]\) (\(1 \leq j \leq t\)) sont des entiers fixés. On dit qu'une sous-grille (1) est orthogonale au \(i\)-ième axe de coordonnées si \(i \in I\), et parallèle au \(i\)-ième axe sinon.
Lemme. Supposons que la grille \(N\) soit recouverte par des sous-grilles \(L_1, L_2, \ldots, L_s\) (c'est-à-dire \(N = \bigcup_{i=1}^{s} L_i\)) de sorte que
(ii') chaque sous-grille contient un point qui n'est recouvert par aucune autre sous-grille ;
(iii) pour chaque axe de coordonnées, il existe une sous-grille \(L_i\) orthogonale à cet axe.
Alors
Preuve. Supposons au contraire que \(s \leq \sum_i (n_i - 1) = s'\). Notre but est de trouver un point non recouvert par \(L_1, \ldots, L_s\).
L'idée de la preuve est la suivante. Imaginons qu'on agrandisse chaque sous-grille en une sous-grille maximale, de sorte que, pour le \(i\)-ième axe, il y ait au plus \(n_i - 1\) sous-grilles maximales orthogonales à cet axe. On trouve alors facilement le point voulu : sa \(i\)-ième coordonnée doit être une valeur non recouverte par les sous-grilles maximales orthogonales au \(i\)-ième axe. Bien sûr, les conditions d'existence d'un tel agrandissement sont données par le lemme de Hall sur les couplages. Nous suivrons donc cette direction, bien que nous appliquions le lemme de Hall à un sous-graphe plutôt qu'au graphe entier.
Construisons un graphe biparti \(G = (V \cup V', E)\) ainsi. Soient \(V = \{L_1, \ldots, L_s\}\) et \(V' = \{v_{ij} : 1 \leq i \leq s, \ 1 \leq j \leq n_i - 1\}\) un ensemble de \(s'\) éléments. L'arête \((L_m, v_{ij})\) est présente si et seulement si \(L_m\) est orthogonale au \(i\)-ième axe.
Pour toute partie \(W \subset V\), posons
Remarquons que \(f(V) = V'\) d'après (iii).
Considérons maintenant l'ensemble \(W \subset V\) ayant le plus grand nombre d'éléments tel que \(\lvert W \rvert > \lvert f(W) \rvert\) ; s'il n'existe pas de tel ensemble, on pose \(W = \varnothing\). Posons \(W' = f(W)\), \(U = V \setminus W\), \(U' = V' \setminus W'\). D'après notre hypothèse et la condition du lemme, \(\lvert f(V) \rvert = \lvert V' \rvert \geq \lvert V \rvert\), donc \(W \neq V\) et \(U \neq \varnothing\). Quitte à permuter les coordonnées, on peut supposer que \(U' = \{v_{ij} : 1 \leq i \leq \ell\}\) et \(W' = \{v_{ij} : \ell + 1 \leq i \leq k\}\).
Considérons le sous-graphe induit \(G'\) de \(G\) sur les sommets \(U \cup U'\). Montrons que, pour toute partie \(X \subset U\), on a \(\lvert f(X) \cap U' \rvert \geq \lvert X \rvert\) (donc \(G'\) vérifie les conditions du lemme de Hall). En effet, on a \(\lvert W \rvert \geq \lvert f(W) \rvert\) ; donc, si \(\lvert X \rvert > \lvert f(X) \cap U' \rvert\) pour une certaine partie \(X \subset U\), alors
Cela contredit la maximalité de \(\lvert W \rvert\).
Ainsi, d'après le lemme de Hall, on peut associer à chaque \(L \in U\) un sommet \(v_{ij} \in U'\), de sorte qu'à des éléments distincts de \(U\) soient associés des sommets distincts de \(U'\). Dans ce cas, on dit que \(L \in U\) correspond au \(i\)-ième axe, et l'on écrit \(g(L) = i\). Comme il y a \(n_i - 1\) sommets de la forme \(v_{ij}\), on obtient que, pour tout \(1 \leq i \leq \ell\), au plus \(n_i - 1\) sous-grilles correspondent au \(i\)-ième axe.
Nous sommes enfin prêts à exhiber le point voulu. Comme \(W \neq V\), il existe un point \(b = (b_1, b_2, \ldots, b_k) \in N \setminus \big(\bigcup_{L \in W} L\big)\). D'autre part, pour tout \(1 \leq i \leq \ell\), considérons une sous-grille \(L \in U\) avec \(g(L) = i\). Cela signifie exactement que \(L\) est orthogonale au \(i\)-ième axe, et donc que tous ses éléments ont la même \(i\)-ième coordonnée \(c_L\). Comme il y a au plus \(n_i - 1\) telles sous-grilles, il existe un nombre \(0 \leq a_i \leq n_i - 1\) qui n'appartient pas à l'ensemble \(\{c_L : g(L) = i\}\). Choisissons un tel nombre pour chaque \(1 \leq i \leq \ell\). Montrons que le point \(a = (a_1, \ldots, a_\ell, b_{\ell+1}, \ldots, b_k)\) n'est pas recouvert, ce qui contredit la condition du lemme.
Le point \(a\) ne peut certainement pas appartenir à un \(L \in U\), puisque tous les points de \(L\) ont une \(g(L)\)-ième coordonnée \(c_L \neq a_{g(L)}\). D'autre part, supposons \(a \in L\) pour un certain \(L \in W\) ; rappelons que \(b \notin L\). Mais les points \(a\) et \(b\) ne diffèrent que par les \(\ell\) premières coordonnées ; \(L\) doit donc être orthogonale à l'un au moins des \(\ell\) premiers axes, et notre graphe contient alors une arête \((L, v_{ij})\) avec \(i \leq \ell\). Cela contredit la définition de \(W'\). Le lemme est démontré. \(\square\)
Revenons au problème. Soit \(d_j\) le pas de la progression \(P_j\). Comme \(n = \operatorname{ppcm}(d_1, \ldots, d_s)\), pour tout \(1 \leq i \leq k\) il existe un indice \(j(i)\) tel que \(p_i^{\alpha_i} \mid d_{j(i)}\). On suppose \(n > 1\) ; sinon l'énoncé est trivial.
Pour \(0 \leq m \leq n - 1\) et \(1 \leq i \leq k\), soit \(m_i\) le reste de \(m\) modulo \(p_i^{\alpha_i}\), et soit \(m_i = \overline{r_{i\alpha_i} \ldots r_{i1}}\) l'écriture de \(m_i\) en base \(p_i\) (éventuellement avec des zéros en tête). Associons à \(m\) la suite \(r(m) = (r_{11}, \ldots, r_{1\alpha_1}, r_{21}, \ldots, r_{k\alpha_k})\). Alors \(r(m)\) appartient à une grille \(N\) de format \(\underbrace{p_1 \times \cdots \times p_1}_{\alpha_1 \text{ fois}} \times \cdots \times \underbrace{p_k \times \cdots \times p_k}_{\alpha_k \text{ fois}}\).
Bien sûr, si \(r(m) = r(m')\), alors \(p_i^{\alpha_i} \mid m_i - m'_i\), ce qui donne \(p_i^{\alpha_i} \mid m - m'\) pour tout \(1 \leq i \leq k\) ; par conséquent, \(n \mid m - m'\). Donc, quand \(m\) parcourt l'ensemble \(\{0, \ldots, n - 1\}\), les suites \(r(m)\) ne se répètent pas ; comme \(\lvert N \rvert = n\), cela signifie que \(r\) est une bijection entre \(\{0, \ldots, n - 1\}\) et \(N\). Montrons maintenant que, pour tout \(1 \leq i \leq s\), l'ensemble \(L_i = \{r(m) : m \in P_i\}\) est une sous-grille, et que pour chaque axe il existe une sous-grille orthogonale à cet axe. Évidemment, ces sous-grilles recouvrent \(N\), et la condition (ii') découle directement de (ii). Le lemme fournit alors exactement l'estimation voulue.
Considérons un \(1 \leq j \leq s\) et écrivons \(d_j = p_1^{\gamma_1} \cdots p_k^{\gamma_k}\). Prenons un \(q \in P_j\) et posons \(r(q) = (r_{11}, \ldots, r_{k\alpha_k})\). Alors, pour un \(q'\) quelconque, en posant \(r(q') = (r'_{11}, \ldots, r'_{k\alpha_k})\), on a
Donc \(L_j = \{(r'_{11}, \ldots, r'_{k\alpha_k}) \in N : r_{i,t} = r'_{i,t} \text{ pour tout } t \leq \gamma_i\}\), ce qui signifie que \(L_j\) est une sous-grille contenant \(r(q)\). De plus, dans \(L_{j(i)}\), toutes les coordonnées correspondant à \(p_i\) sont fixées, donc cette sous-grille est orthogonale à tous les axes correspondants, comme voulu. \(\blacksquare\)
Remarque 1. L'estimation du problème est optimale pour tout \(n\). Voici l'un des exemples possibles. Pour chaque \(1 \leq i \leq k\), \(0 \leq j \leq \alpha_i - 1\), \(1 \leq k' \leq p_i - 1\), posons
et ajoutons la progression \(P_0 = n\mathbb{Z}\). On vérifie facilement que cet ensemble vérifie toutes les conditions du problème. Il existe aussi d'autres exemples.
D'autre part, on peut préciser l'estimation dans le sens suivant. Pour tout \(1 \leq i \leq k\), soient \(0 = \alpha_{i0}, \alpha_{i1}, \ldots, \alpha_{ih_i}\) tous les nombres de la forme \(\operatorname{ord}_{p_i}(d_j)\) rangés par ordre croissant (on supprime les répétitions, et l'on ajoute le nombre \(0 = \alpha_{i0}\) s'il n'apparaît pas). En reprenant les arguments de la solution, on obtient alors
Remarquons que \(p^\alpha - 1 \geq \alpha(p - 1)\), avec égalité seulement pour \(\alpha = 1\). Pour atteindre le nombre minimal de progressions, il faut donc avoir \(\alpha_{i,j} = j\) pour tous \(i\), \(j\). Autrement dit, pour tout \(1 \leq j \leq \alpha_i\), il doit exister un indice \(t\) tel que \(\operatorname{ord}_{p_i}(d_t) = j\).
Solution 2¶
Commençons par quelques notations. Pour un entier \(r > 0\), on note \([r] = \{1, 2, \ldots, r\}\). On dit qu'un ensemble de progressions \(\mathcal{P} = \{P_1, \ldots, P_s\}\) recouvre \(\mathbb{Z}\) si tout entier appartient à l'une d'elles ; ce recouvrement est minimal si aucune partie stricte de \(\mathcal{P}\) ne recouvre \(\mathbb{Z}\). Évidemment, tout recouvrement contient un sous-recouvrement minimal.
Ensuite, pour un recouvrement minimal \(\{P_1, \ldots, P_s\}\) et pour tout \(1 \leq i \leq s\), soit \(d_i\) le pas de la progression \(P_i\), et \(h_i\) un nombre contenu dans \(P_i\) mais dans aucune autre progression. On suppose \(n > 1\), sinon le problème est trivial. Cela implique \(d_i > 1\), sinon la progression \(P_i\) recouvrirait tous les nombres, et \(n = 1\).
Nous allons prouver un énoncé plus général, à savoir le suivant.
Affirmation. Supposons que les progressions \(P_1, \ldots, P_s\) et le nombre \(n = p_1^{\alpha_1} \cdots p_k^{\alpha_k} > 1\) soient choisis comme dans l'énoncé. Choisissons de plus un ensemble d'indices non vide \(I = \{i_1, \ldots, i_t\} \subseteq [k]\) et un entier \(\beta_i \leq \alpha_i\) strictement positif pour chaque \(i \in I\). Considérons l'ensemble d'indices
Alors
Remarquons que l'affirmation pour \(I = [k]\) et \(\beta_i = \alpha_i\) implique l'énoncé du problème, puisque le membre de gauche de (2) ne dépasse pas \(s\). Il suffit donc de prouver l'affirmation.
- Prouvons d'abord l'affirmation en supposant que tous les \(d_j\) sont des nombres premiers. Si, pour un certain \(1 \leq i \leq k\), on a au moins \(p_i\) progressions de pas \(p_i\), alors elles ne se coupent pas et recouvrent donc tous les entiers ; cela signifie qu'il n'y a pas d'autre progression, et \(n = p_i\) ; l'affirmation est triviale dans ce cas.
Supposons maintenant que, pour tout \(1 \leq i \leq k\), il y ait au plus \(p_i - 1\) progressions de pas \(p_i\) ; chacune de ces progressions recouvre les nombres d'un résidu fixé modulo \(p_i\), donc il existe un résidu \(q_i \bmod p_i\) qui n'est touché par aucune de ces progressions. Par le théorème chinois, il existe un nombre \(q\) tel que \(q \equiv q_i \pmod{p_i}\) pour tout \(1 \leq i \leq k\) ; ce nombre ne peut être recouvert par aucune progression de pas \(p_i\), donc il n'est pas recouvert du tout. Contradiction.
-
Supposons maintenant que l'affirmation générale soit fausse ; considérons un contre-exemple \(\{P_1, \ldots, P_s\}\) à l'affirmation, choisi minimal au sens suivant :
-
le nombre \(n\) est le plus petit possible parmi tous les contre-exemples ;
- la somme \(\sum_i d_i\) est la plus petite possible parmi tous les contre-exemples ayant cette valeur de \(n\).
Comme on l'a vu, les \(d_i\) ne sont pas tous premiers ; on peut donc supposer que \(d_1\) est composé, disons \(p_1 \mid d_1\) et \(d'_1 = \frac{d_1}{p_1} > 1\). Considérons une progression \(P'_1\) de pas \(d'_1\) contenant \(P_1\). Nous allons nous intéresser à deux recouvrements construits ainsi.
(i) Bien sûr, les progressions \(P'_1, P_2, \ldots, P_s\) recouvrent \(\mathbb{Z}\), mais ce recouvrement n'est pas nécessairement minimal. Choisissons donc un sous-recouvrement minimal \(\mathcal{P}'\) ; sûrement \(P'_1 \in \mathcal{P}'\) puisque \(h_1\) n'est pas recouvert par \(P_2, \ldots, P_s\), donc on peut supposer que \(\mathcal{P}' = \{P'_1, P_2, \ldots, P_{s'}\}\) pour un certain \(s' \leq s\). De plus, la période du recouvrement \(\mathcal{P}'\) peut être plus petite que \(n\) ; on note donc cette période
Remarquons que, pour tout \(P_j \notin \mathcal{P}'\), on a \(h_j \in P'_1\), sinon \(h_j\) ne serait pas recouvert par \(\mathcal{P}'\).
(ii) D'autre part, tout ensemble non vide de la forme \(R_i = P_i \cap P'_1\) (\(1 \leq i \leq s\)) est aussi une progression, de pas \(r_i = \operatorname{ppcm}(d_i, d'_1)\), et ces progressions recouvrent \(P'_1\). En appliquant à ces progressions une homothétie de rapport \(1/d'_1\), on obtient des progressions \(Q_i\) de pas \(q_i = r_i/d'_1\) qui recouvrent \(\mathbb{Z}\). Choisissons un sous-recouvrement minimal \(\mathcal{Q}\) de ce recouvrement ; là encore, on doit avoir \(Q_1 \in \mathcal{Q}\) pour la même raison liée à \(h_1\). Notons la période de \(\mathcal{Q}\)
Remarquons que si \(h_j \in P'_1\), alors l'image de \(h_j\) par l'homothétie ne peut être recouverte que par \(Q_j\) ; dans ce cas, on a donc \(Q_j \in \mathcal{Q}\).
Notre but est de trouver le nombre voulu de progressions dans les recouvrements \(\mathcal{P}\) et \(\mathcal{Q}\). D'abord, \(n \geq n'\), et la somme des pas dans \(\mathcal{P}'\) est plus petite que dans \(\mathcal{P}\) ; l'affirmation est donc vraie pour \(\mathcal{P}'\). Appliquons-la à l'ensemble d'indices \(I' = \{i \in I : \beta_i > \sigma_i\}\) et aux exposants \(\beta'_i = \beta_i - \sigma_i\) ; l'ensemble considéré est alors
et l'on obtient
où \((x)_+ = \max\{x, 0\}\) ; la dernière égalité vient de ce que \(\beta_i \leq \sigma_i\) pour \(i \notin I'\).
Remarquons que \(x = (x - y)_+ + \min\{x, y\}\) pour tous \(x\), \(y\). Donc, si l'on trouve au moins
indices dans \(T \cap \{s' + 1, \ldots, s\}\), on aura
ce qui contredira le choix de \(\mathcal{P}\). Nous allons trouver ces indices parmi les indices des progressions de \(\mathcal{Q}\).
- Posons \(I'' = \{i \in I : \sigma_i > 0\}\) et considérons un \(i \in I''\) ; alors \(p_i^{\alpha_i} \nmid n'\). D'autre part, il existe un indice \(j(i)\) tel que \(p_i^{\alpha_i} \mid d_{j(i)}\) ; cela signifie que \(d_{j(i)} \nmid n'\) et donc que \(P_{j(i)}\) ne peut pas appartenir à \(\mathcal{P}'\), de sorte que \(j(i) > s'\). De plus, on a vu que dans ce cas \(h_{j(i)} \in P'_1\), donc \(Q_{j(i)} \in \mathcal{Q}\). Cela signifie que \(q_{j(i)} \mid n''\), donc \(\gamma_i = \alpha_i\) pour tout \(i \in I''\) (rappelons ici que \(q_i = r_i/d'_1\) et donc \(d_{j(i)} \mid r_{j(i)} \mid d'_1 n''\)).
Posons \(d'_1 = p_1^{\tau_1} \cdots p_k^{\tau_k}\). Alors \(n'' = p_1^{\gamma_1 - \tau_1} \cdots p_k^{\gamma_k - \tau_k}\). Si \(i \in I''\), alors, pour tout \(\beta\), la condition \(p_i^{(\gamma_i - \tau_i) - \beta + 1} \mid q_j\) équivaut à \(p_i^{\alpha_i - \beta + 1} \mid r_j\).
Remarquons que \(n'' \leq n/d'_1 < n\), donc on peut appliquer l'affirmation au recouvrement \(\mathcal{Q}\). On le fait avec l'ensemble d'indices \(I''\) et les exposants \(\beta''_i = \min\{\beta_i, \sigma_i\} > 0\). L'ensemble considéré est alors
et l'on obtient \(\lvert T'' \rvert \geq 1 + G\). Enfin, montrons que \(T'' \subseteq T \cap \big(\{1\} \cup \{s' + 1, \ldots, s\}\big)\) ; on obtiendra alors \(\lvert T \cap \{s' + 1, \ldots, s\} \rvert \geq G\), ce qui est exactement ce qu'il faut.
Pour le prouver, considérons un \(j \in T''\) quelconque. Remarquons que \(\alpha_i - \min\{\beta_i, \sigma_i\} + 1 > \alpha_i - \sigma_i \geq \tau_i\) ; donc, de \(p_i^{\alpha_i - \min\{\beta_i, \sigma_i\} + 1} \mid r_j = \operatorname{ppcm}(d'_1, d_j)\), on tire \(p_i^{\alpha_i - \min\{\beta_i, \sigma_i\} + 1} \mid d_j\), ce qui signifie que \(j \in T\). Ensuite, l'exposant de \(p_i\) dans \(d_j\) est plus grand que dans \(n'\), ce qui signifie que \(P_j \notin \mathcal{P}'\). Cela ne peut se produire que si \(j = 1\) ou \(j > s'\), comme voulu. La preuve est complète. \(\blacksquare\)
Remarque 2. Il existe aussi un analogue de l'affirmation pour les grilles. Il s'énonce ainsi.
Affirmation. Supposons que la grille \(N\) soit recouverte par des sous-grilles \(L_1, L_2, \ldots, L_s\) de sorte que
(ii') chaque sous-grille contient un point qui n'est recouvert par aucune autre sous-grille ;
(iii) pour chaque axe de coordonnées, il existe une sous-grille \(L_i\) orthogonale à cet axe.
Choisissons un ensemble d'indices \(I = \{i_1, \ldots, i_t\} \subset [k]\), et considérons l'ensemble d'indices
Alors
Cette affirmation se prouve presque de la même façon que dans la solution 1.