Shortlist 2007, C6¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Russia
Concepts : Graphes : degrés, chemins, arbres · Invariants et monovariants
Solution officielle : Shortlist officielle 2007 (avec solutions), p. 34 (page 35 du PDF)
Problème 3 de l'OIM 2007
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2007, où il était le problème 3 (jour 1).
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
In a mathematical competition some competitors are friends; friendship is always mutual. Call a group of competitors a clique if each two of them are friends. The number of members in a clique is called its size.
It is known that the largest size of cliques is even. Prove that the competitors can be arranged in two rooms such that the largest size of cliques in one room is the same as the largest size of cliques in the other room.
Indices : les idées clés
- Algorithme : on place une clique maximale \(M\) (\(\lvert M \rvert = 2m\)) dans la salle \(A\), puis on déplace ses membres un à un vers \(B\) tant que \(c(A) > c(B)\) ; à chaque pas, \(c(A)\) baisse de \(1\) et \(c(B)\) monte d'au plus \(1\) (quantité contrôlée).
- Ajustement : si \(c(B) = k + 1\), on renvoie un membre de \(B \cap M\) hors d'une \((k + 1)\)-clique, ou, à défaut, on vide les \((k + 1)\)-cliques de \(B\) de leurs membres hors de \(M\).
- Contrôle de \(c(A)\) : toute clique \(Q\) de la salle \(A\) est amie avec tout \(B \cap M\), donc \(Q \cup (B \cap M)\) est une clique et \(\lvert Q \rvert \leq \lvert A \cap M \rvert = k\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2007 (une solution et une remarque). C'est le problème 3 de l'OIM 2007.
Solution¶
Présentons un algorithme pour répartir les participants. Appelons les deux salles salle \(A\) et salle \(B\). On part d'une répartition initiale, qu'on modifie plusieurs fois en envoyant une personne dans l'autre salle. À chaque étape de l'algorithme, \(A\) et \(B\) désignent les ensembles de participants des deux salles, et \(c(A)\) et \(c(B)\) les plus grandes tailles de cliques dans ces salles.
Étape 1. Soit \(M\) l'une des cliques de taille maximale, \(\lvert M \rvert = 2m\). Envoyer tous les membres de \(M\) dans la salle \(A\) et tous les autres participants dans la salle \(B\).
Comme \(M\) est une clique de taille maximale, on a \(c(A) = \lvert M \rvert \geq c(B)\).
Étape 2. Tant que \(c(A) > c(B)\), envoyer une personne de la salle \(A\) dans la salle \(B\).
Remarquons que \(c(A) > c(B)\) implique que la salle \(A\) n'est pas vide.
À chaque pas, \(c(A)\) diminue de \(1\) et \(c(B)\) augmente d'au plus \(1\). À la fin, on a donc \(c(A) \leq c(B) \leq c(A) + 1\).
On a aussi \(c(A) = \lvert A \rvert \geq m\) à la fin. Sinon, on aurait au moins \(m + 1\) membres de \(M\) dans la salle \(B\) et au plus \(m - 1\) dans la salle \(A\), ce qui impliquerait \(c(B) - c(A) \geq (m + 1) - (m - 1) = 2\).
Étape 3. Soit \(k = c(A)\). Si \(c(B) = k\), alors STOP.
Si l'on a atteint \(c(A) = c(B) = k\), on a trouvé la répartition voulue.
Dans tous les autres cas, \(c(B) = k + 1\).
D'après l'estimation ci-dessus, on sait aussi que \(k = \lvert A \rvert = \lvert A \cap M \rvert \geq m\) et \(\lvert B \cap M \rvert \leq m\).
Étape 4. S'il existe un participant \(x \in B \cap M\) et une clique \(C \subset B\) tels que \(\lvert C \rvert = k + 1\) et \(x \notin C\), alors envoyer \(x\) dans la salle \(A\) et STOP.
Après le retour de \(x\) dans la salle \(A\), on aura \(k + 1\) membres de \(M\) dans la salle \(A\), donc \(c(A) = k + 1\). Comme \(x \notin C\), \(c(B) = \lvert C \rvert\) n'a pas diminué, et après cette étape on a \(c(A) = c(B) = k + 1\).
S'il n'existe pas de tel participant \(x\), alors, dans la salle \(B\), toutes les cliques de taille \(k + 1\) contiennent \(B \cap M\).
Étape 5. Tant que \(c(B) = k + 1\), choisir une clique \(C \subset B\) telle que \(\lvert C \rvert = k + 1\) et envoyer un membre de \(C \setminus M\) dans la salle \(A\).
Remarquons que \(\lvert C \rvert = k + 1 > m \geq \lvert B \cap M \rvert\), donc \(C \setminus M\) ne peut pas être vide.
À chaque fois, on déplace une seule personne de la salle \(B\) vers la salle \(A\), donc \(c(B)\) diminue d'au plus \(1\). À la fin de cette boucle, on a donc \(c(B) = k\).
Dans la salle \(A\), on a la clique \(A \cap M\), de taille \(\lvert A \cap M \rvert = k\), donc \(c(A) \geq k\). Montrons qu'il n'y a pas de clique de taille supérieure. Soit \(Q \subset A\) une clique quelconque ; montrons que \(\lvert Q \rvert \leq k\).
Dans la salle \(A\), et en particulier dans l'ensemble \(Q\), il peut y avoir deux types de participants :
- des membres de \(M\) ; comme \(M\) est une clique, ils sont amis avec tous les membres de \(B \cap M\) ;
- des participants déplacés dans la salle \(A\) à l'étape 5 ; chacun d'eux faisait partie d'une clique contenant \(B \cap M\), donc ils sont aussi amis avec tous les membres de \(B \cap M\).
Ainsi, tous les membres de \(Q\) sont amis avec tous les membres de \(B \cap M\). Les ensembles \(Q\) et \(B \cap M\) sont eux-mêmes des cliques, donc \(Q \cup (B \cap M)\) est aussi une clique. Comme \(M\) est une clique de taille maximale,
donc
Finalement, après l'étape 5, on a \(c(A) = c(B) = k\). \(\blacksquare\)
Remarque¶
L'énoncé est évidemment faux sans l'hypothèse que la plus grande taille de clique est paire.