Shortlist 2012, C7¶
Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : non indiqué
Concepts : Graphes : degrés, chemins, arbres · Principe des tiroirs · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2012 (avec solutions), p. 28 (page 28 du PDF)
Énoncé¶
On se donne \(2^{500}\) points sur un cercle, numérotés \(1, 2, \ldots, 2^{500}\) dans un certain ordre. Montrer qu'on peut choisir \(100\) cordes deux à deux disjointes joignant certains de ces points, de sorte que les \(100\) sommes des numéros des extrémités des cordes choisies soient égales.
Énoncé original (anglais)
There are given \(2^{500}\) points on a circle labeled \(1, 2, \ldots, 2^{500}\) in some order. Prove that one can choose \(100\) pairwise disjoint chords joining some of these points so that the \(100\) sums of the pairs of numbers at the endpoints of the chosen chords are equal.
Indices : les idées clés
- Lemme de Caro-Wei : tout graphe contient un ensemble indépendant de taille au moins \(\sum_v \frac{1}{d_v + 1}\) (récurrence en retirant un sommet de degré minimal et ses voisins).
- Un graphe par couleur : on colorie chaque corde par la somme de ses extrémités ; pour la couleur \(c\), le graphe \(G_c\) relie les cordes qui se coupent. Une corde qui laisse \(i\) points d'un côté a un degré au plus \(i\).
- Moyenne : \(\sum_c f(G_c) \geq 2n \sum_{i=1}^{n-1} \frac{1}{i}\) sur \(4n - 3\) couleurs, et la série harmonique jusqu'à \(2^{400}\) dépasse \(200\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2012 (une solution).
Solution¶
La preuve repose sur le fait général suivant.
Lemme. Dans un graphe \(G\), chaque sommet \(v\) a un degré \(d_v\). Alors \(G\) contient un ensemble indépendant \(S\) de sommets tel que \(\lvert S \rvert \geq f(G)\), où
Preuve. Par récurrence sur \(n = \lvert G \rvert\). Le cas \(n = 1\) est clair. Pour l'hérédité, choisissons un sommet \(v_0\) de \(G\) de degré minimal \(d\). Supprimons \(v_0\) et tous ses voisins \(v_1, \ldots, v_d\), ainsi que toutes les arêtes ayant une extrémité parmi \(v_0, v_1, \ldots, v_d\). On obtient un nouveau graphe \(G'\). Par hypothèse de récurrence, \(G'\) contient un ensemble indépendant \(S'\) tel que \(\lvert S' \rvert \geq f(G')\). Comme aucun sommet de \(S'\) n'est voisin de \(v_0\) dans \(G\), l'ensemble \(S = S' \cup \{v_0\}\) est indépendant dans \(G\).
Soit \(d'_v\) le degré d'un sommet \(v\) dans \(G'\). Clairement \(d'_v \leq d_v\) pour tout sommet \(v\) de \(G'\), et \(d_{v_i} \geq d\) pour tout \(i = 0, 1, \ldots, d\) par le choix minimal de \(v_0\). Donc
Ainsi \(\lvert S \rvert = \lvert S' \rvert + 1 \geq f(G') + 1 \geq f(G)\), ce qui achève la récurrence. \(\square\)
Passons au problème. Pour plus de clarté, posons \(n = 2^{499}\), et traçons toutes les cordes déterminées par les \(2n\) points donnés. Colorions chaque corde avec l'une des couleurs \(3, 4, \ldots, 4n - 1\) selon la somme des nombres à ses extrémités. Deux cordes ayant une extrémité commune ont des couleurs différentes. Pour chaque couleur \(c\), considérons le graphe \(G_c\) suivant : ses sommets sont les cordes de couleur \(c\), et deux cordes sont voisines dans \(G_c\) si elles se coupent. On définit \(f(G_c)\) comme dans le lemme.
Chaque corde \(\ell\) découpe le cercle en deux arcs, dont l'un contient \(m(\ell) \leq n - 1\) points donnés (en particulier \(m(\ell) = 0\) si \(\ell\) relie deux points consécutifs). Pour chaque \(i = 0, 1, \ldots, n - 2\), il y a \(2n\) cordes \(\ell\) avec \(m(\ell) = i\). Une telle corde a un degré au plus \(i\) dans le graphe correspondant. En effet, soient \(A_1, \ldots, A_i\) tous les points de l'arc déterminé par une corde \(\ell\) avec \(m(\ell) = i\) et de couleur \(c\). Chaque \(A_j\) est l'extrémité d'au plus une corde de couleur \(c\), pour \(j = 1, \ldots, i\). Donc au plus \(i\) cordes de couleur \(c\) coupent \(\ell\).
Il s'ensuit que, pour chaque \(i = 0, 1, \ldots, n - 2\), les \(2n\) cordes \(\ell\) avec \(m(\ell) = i\) contribuent pour au moins \(\frac{2n}{i + 1}\) à la somme \(\sum_c f(G_c)\). En sommant sur \(i = 0, 1, \ldots, n - 2\), on obtient
Comme il y a \(4n - 3\) couleurs en tout, une moyenne donne une couleur \(c\) telle que
Par le lemme, il existe au moins \(\frac{1}{2} \sum_{i=1}^{n-1} \frac{1}{i}\) cordes deux à deux disjointes de couleur \(c\), c'est-à-dire ayant la même somme \(c\) des nombres à leurs extrémités. Il reste à montrer que \(\frac{1}{2} \sum_{i=1}^{n-1} \frac{1}{i} \geq 100\) pour \(n = 2^{499}\). En effet,
Cela achève la solution. \(\blacksquare\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2023 C4 ★★★☆☆ : Découper une bande \(1 \times n^2\) et translater les morceaux pour former un carré avec une condition sur les numéros : combien de morceaux ?
- 2013 C6 ★★★★☆ : Si chaque ville a au plus \(100\) villes à distance \(3\), aucune n'en a plus de \(2550\) à distance \(4\).
- 2015 C7 ★★★★★ : Une compagnie avec au plus \(2015\) cycles impairs d'ennemis se répartit en \(11\) groupes sans ennemis.
- 2010 C7 ★★★★★ : Des progressions arithmétiques recouvrant \(\mathbb{Z}\), chacune indispensable : il en faut au moins \(1 + \sum \alpha_i(p_i - 1)\).