Aller au contenu

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)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

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ù

\[f(G) = \sum_{v \in G} \frac{1}{d_v + 1}.\]

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

\[f(G') = \sum_{v \in G'} \frac{1}{d'_v + 1} \geq \sum_{v \in G'} \frac{1}{d_v + 1} = f(G) - \sum_{i=0}^{d} \frac{1}{d_{v_i} + 1} \geq f(G) - \frac{d + 1}{d + 1} = f(G) - 1.\]

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

\[\sum_c f(G_c) \geq 2n \sum_{i=1}^{n-1} \frac{1}{i}.\]

Comme il y a \(4n - 3\) couleurs en tout, une moyenne donne une couleur \(c\) telle que

\[f(G_c) \geq \frac{2n}{4n - 3} \sum_{i=1}^{n-1} \frac{1}{i} > \frac{1}{2} \sum_{i=1}^{n-1} \frac{1}{i}.\]

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,

\[\sum_{i=1}^{n-1} \frac{1}{i} > \sum_{i=1}^{2^{400}} \frac{1}{i} = 1 + \sum_{k=1}^{400} \sum_{i = 2^{k-1} + 1}^{2^k} \frac{1}{i} > 1 + \sum_{k=1}^{400} \frac{2^{k-1}}{2^k} = 201 > 200.\]

Cela achève la solution. \(\blacksquare\)