Aller au contenu

Shortlist 2017, C8

Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : Bulgaria

Concepts : Invariants et monovariants · Géométrie combinatoire : enveloppe convexe, points du réseau

Solution officielle : Shortlist officielle 2017 (avec solutions), p. 51 (page 53 du PDF)

Pas encore relu

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

Énoncé

Let \(n\) be a given positive integer. In the Cartesian plane, each lattice point with nonnegative coordinates initially contains a butterfly, and there are no other butterflies. The neighborhood of a lattice point \(c\) consists of all lattice points within the axis-aligned \((2n+1) \times (2n+1)\) square centered at \(c\), apart from \(c\) itself. We call a butterfly lonely, crowded, or comfortable, depending on whether the number of butterflies in its neighborhood \(N\) is respectively less than, greater than, or equal to half of the number of lattice points in \(N\).

Every minute, all lonely butterflies fly away simultaneously. This process goes on for as long as there are any lonely butterflies. Assuming that the process eventually stops, determine the number of comfortable butterflies at the final state.

Indices : les idées clés
  • Invariants : l'ensemble des papillons reste « fermé vers le haut et la droite » à chaque étape.
  • L'état final est le plus grand ensemble stable : un ensemble sans point solitaire ne perd jamais de papillon, donc il suffit de décrire le plus grand ensemble stable.
  • Enveloppe convexe et points du réseau : le bord de l'ensemble final est une ligne brisée construite à partir des rayons issus de l'origine qui passent par les points du carré \(\mathcal{K}_n = \{1, \ldots, n\} \times \{-n, \ldots, -1\}\).
  • Droite d'appui : un point d'un ensemble stable situé sur une droite d'appui doit avoir au moins la moitié des points de son voisinage sur cette droite dans l'ensemble.
  • Compter les points du réseau sur la ligne brisée : ils sont en bijection avec les points de \(\mathcal{K}_n\), plus un, d'où \(n^2 + 1\).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2017 (une solution et deux remarques).

Réponse : \(n^2 + 1\).

Solution

On identifie toujours un papillon au point du réseau où il se trouve. Pour deux points \(p\) et \(q\), on écrit \(p \geq q\) si chaque coordonnée de \(p\) est au moins égale à la coordonnée correspondante de \(q\). Soit \(O\) l'origine et soit \(\mathcal{Q}\) l'ensemble des points initialement occupés, c'est-à-dire de tous les points du réseau à coordonnées positives ou nulles. Soient \(\mathcal{R}_H = \{(x, 0) : x \geq 0\}\) et \(\mathcal{R}_V = \{(0, y) : y \geq 0\}\) les points du réseau des deux demi-droites qui bordent \(\mathcal{Q}\). On note \(N(a)\) le voisinage d'un point \(a\). (Le livret contient plusieurs figures auxquelles on renvoie ci-dessous : voir la figure du livret officiel.)

1. Premières observations. Un ensemble de points du réseau est dit fermé vers le haut-droite s'il est stable par translation de tout vecteur \((i, j)\) avec \(i, j \geq 0\). Si les papillons forment un tel ensemble \(\mathcal{S}\), alors \(|N(p) \cap \mathcal{S}| \geq |N(q) \cap \mathcal{S}|\) pour tous \(p, q \in \mathcal{S}\) avec \(p \geq q\) (le translaté de \(N(q) \cap \mathcal{S}\) par \(\overrightarrow{qp}\) est dans \(N(p) \cap \mathcal{S}\)). Donc si \(p\) s'envole, tout \(q \leq p\) s'envole aussi : comme \(\mathcal{Q}\) est fermé vers le haut-droite, l'ensemble des papillons conserve cette propriété à chaque instant (c'est un invariant). Dans toute la suite, les ensembles de points considérés sont supposés fermés vers le haut-droite.

Pour un ensemble \(\mathcal{S}\) de points, on dit que ses points sont solitaires, confortables ou serrés relativement à \(\mathcal{S}\) (comme si les papillons occupaient exactement \(\mathcal{S}\)). Un ensemble \(\mathcal{S} \subset \mathcal{Q}\) est stable s'il ne contient aucun point solitaire. On ne s'intéresse qu'aux ensembles stables de complémentaire fini dans \(\mathcal{Q}\), car on voit facilement que seul un nombre fini de papillons peut s'envoler à chaque minute.

Si \(\mathcal{Q}\) contient un ensemble stable \(\mathcal{S}\), aucun papillon de \(\mathcal{S}\) ne s'envole jamais (tant que l'ensemble courant contient \(\mathcal{S}\), chaque point de \(\mathcal{S}\) y a au moins autant de voisins que dans \(\mathcal{S}\)). D'autre part, l'ensemble \(\mathcal{F}\) des papillons à la fin du processus est stable. Donc \(\mathcal{F}\) est le plus grand (pour l'inclusion) ensemble stable contenu dans \(\mathcal{Q}\), et nous allons le décrire.

2. Description de l'ensemble final. Soit \(\mathcal{U} = \{\vec u_1, \ldots, \vec u_d\}\) un ensemble de \(d\) vecteurs du réseau deux à deux non colinéaires, chacun d'abscisse positive et d'ordonnée négative, numérotés par pente croissante. On appelle \(\mathcal{U}\)-courbe la ligne brisée \(p_0p_1\ldots p_d\) telle que \(p_0 \in \mathcal{R}_V\), \(p_d \in \mathcal{R}_H\) et \(\overrightarrow{p_{i-1}p_i} = \vec u_i\) pour \(i = 1, \ldots, d\).

Soit \(\mathcal{K}_n = \{(i, j) : 1 \leq i \leq n,\ -n \leq j \leq -1\}\). Considérons toutes les demi-droites issues de \(O\) passant par un point de \(\mathcal{K}_n\) ; numérotons-les \(r_1, \ldots, r_m\) par pente croissante. Soit \(A_i\) le point du réseau de \(r_i \cap \mathcal{K}_n\) le plus éloigné de \(O\), soit \(k_i = |r_i \cap \mathcal{K}_n|\), soit \(\vec v_i = \overrightarrow{OA_i}\), et enfin \(\mathcal{V} = \{\vec v_i : 1 \leq i \leq m\}\). On s'intéresse à la \(\mathcal{V}\)-courbe \(d_0d_1\ldots d_m\) ; soit \(\mathcal{D}\) l'ensemble des points du réseau \(p\) tels que \(p \geq p'\) pour un point \(p'\) (pas forcément du réseau) de la \(\mathcal{V}\)-courbe. Nous allons montrer que \(\mathcal{D} = \mathcal{F}\).

La \(\mathcal{V}\)-courbe est clairement symétrique par rapport à la droite \(y = x\). Notons \(D\) l'enveloppe convexe de \(\mathcal{D}\).

3. \(\mathcal{D}\) contient tous les ensembles stables. Soit \(\mathcal{S} \subset \mathcal{Q}\) un ensemble stable (fermé vers le haut-droite, de complémentaire fini dans \(\mathcal{Q}\)), et \(S\) son enveloppe convexe ; les sommets de \(S\) sont des points du réseau. Le bord de \(S\) est formé de deux demi-droites (horizontale et verticale) et d'une \(\mathcal{V}_*\)-courbe pour un certain ensemble de vecteurs \(\mathcal{V}_*\).

Affirmation 1. Pour tout \(\vec v_i \in \mathcal{V}\), il existe \(\vec v_i^{\,*} \in \mathcal{V}_*\) de même direction et de même sens que \(\vec v_i\), avec \(|\vec v_i^{\,*}| \geq |\vec v_i|\).

Preuve. Soit \(\ell\) la droite d'appui de \(S\) parallèle à \(\vec v_i\) (\(\ell\) contient un point de \(\mathcal{S}\) et \(\mathcal{S}\) est d'un seul côté de \(\ell\)). Prenons \(b \in \ell \cap \mathcal{S}\) et considérons \(N(b)\). La droite \(\ell\) partage \(N(b) \setminus \ell\) en deux parties isométriques, dont l'une ne rencontre pas \(\mathcal{S}\). Pour que \(b\) ne soit pas solitaire, il faut donc qu'au moins la moitié de \(\ell \cap N(b)\) (qui contient \(2k_i\) points) soit dans \(\mathcal{S}\). Ainsi le bord de \(S\) contient un segment \(\ell \cap S\) portant au moins \(k_i + 1\) points du réseau (dont \(b\)) ; ce segment correspond au vecteur cherché \(\vec v_i^{\,*} \in \mathcal{V}_*\). \(\square\)

Affirmation 2. Tout ensemble stable \(\mathcal{S} \subseteq \mathcal{Q}\) est contenu dans \(\mathcal{D}\).

Preuve. Il suffit de montrer que la \(\mathcal{V}_*\)-courbe est dans \(D\), c'est-à-dire que tous ses sommets y sont. Soit \(p'\) un sommet de la \(\mathcal{V}_*\)-courbe ; il la coupe en deux parties, \(\mathcal{X}\) (en bas à droite de \(p'\)) et \(\mathcal{Y}\) (en haut à gauche de \(p'\)). On partage \(\mathcal{V}\) en \(\mathcal{V}_\mathcal{X}\), formé des \(\vec v_i\) dont le \(\vec v_i^{\,*}\) correspond à un segment de \(\mathcal{X}\), et \(\mathcal{V}_\mathcal{Y}\) défini de même. Par ordre des pentes, la \(\mathcal{V}\)-courbe est formée des segments correspondant à \(\mathcal{V}_\mathcal{Y}\), suivis de ceux correspondant à \(\mathcal{V}_\mathcal{X}\) (le livret les énumère dans l'ordre inverse, ce qui ne change rien à l'argument). Il y a donc un sommet \(p\) de la \(\mathcal{V}\)-courbe qui sépare \(\mathcal{V}_\mathcal{Y}\) de \(\mathcal{V}_\mathcal{X}\). L'affirmation 1 donne alors \(p' \geq p\) (précision ajoutée : l'abscisse de \(p'\) est au moins la somme des abscisses des \(\vec v_i^{\,*}\) pour \(\vec v_i \in \mathcal{V}_\mathcal{Y}\), qui majore celle des \(\vec v_i\), c'est-à-dire l'abscisse de \(p\) ; de même pour les ordonnées en partant de l'extrémité sur \(\mathcal{R}_H\)), donc \(p' \in D\). \(\square\)

L'affirmation 2 entraîne que l'ensemble final \(\mathcal{F}\) est contenu dans \(\mathcal{D}\).

4. \(\mathcal{D}\) est stable, et l'on connaît ses points confortables. Soit \(r'_i\) la demi-droite opposée à \(r_i\). Par définition, \(N(O)\) ne contient aucun point strictement entre les demi-droites \(r_i\) et \(r_{i+1}\), ni entre \(r'_i\) et \(r'_{i+1}\).

Affirmation 3. Dans l'ensemble \(\mathcal{D}\), tous les points du réseau de la \(\mathcal{V}\)-courbe sont confortables.

Preuve. Soit \(p\) un point du réseau de la \(\mathcal{V}\)-courbe, situé sur un segment \(d_id_{i+1}\), et soit \(\ell\) la droite qui le porte. Alors \(\ell \cap \mathcal{D}\) contient exactement \(k_i + 1\) points du réseau (ceux du segment), qui sont tous dans \(N(p)\) sauf \(p\). Ainsi exactement la moitié des points de \(N(p) \cap \ell\) sont dans \(\mathcal{D}\). Il reste à montrer que tous les points de \(N(p)\) au-dessus de \(\ell\) sont dans \(\mathcal{D}\) (ceux au-dessous n'y sont pas).

Chaque vecteur de \(\mathcal{V}\) a une coordonnée de valeur absolue supérieure à \(n/2\) (sinon le double de \(\vec v_i\) serait encore dans \(\mathcal{K}_n\), contredisant le choix de \(A_i\)) ; donc le voisinage de \(p\) rencontre au plus deux des segments de la \(\mathcal{V}\)-courbe qui suivent \(d_id_{i+1}\), et au plus deux de ceux qui le précèdent. Les angles formés par ces segments consécutifs s'obtiennent par translation de ceux formés par \(r_j\) et \(r'_{j-1}\) (\(i - 1 \leq j \leq i + 2\)). Tous les points de \(N(p)\) au-dessus de \(\ell\) qui pourraient être hors de \(\mathcal{D}\) sont dans des translatés d'angles entre \(r_j\) et \(r_{j+1}\), ou entre \(r'_j\) et \(r'_{j-1}\). Mais ces angles, restreints à \(N(p)\), ne contiennent aucun point du réseau d'après la remarque ci-dessus. \(\square\)

Affirmation 4. Tous les points de \(\mathcal{D}\) qui ne sont pas sur le bord de \(D\) sont serrés.

Preuve. Soit \(p \in \mathcal{D}\) un tel point. S'il est en haut à droite d'un point \(p'\) de la courbe, c'est facile : le translaté de \(N(p') \cap \mathcal{D}\) par \(\overrightarrow{p'p}\) est encore dans \(\mathcal{D}\), et \(N(p)\) contient au moins un point de plus de \(\mathcal{D}\) (au-dessous ou à gauche de \(p\)). On peut donc supposer que \(p\) est dans un triangle rectangle construit sur une hypoténuse \(d_id_{i+1}\). Remarquons que \(d_i, d_{i+1} \in N(p)\).

Traçons la droite \(\ell\) parallèle à \(d_id_{i+1}\) passant par \(p\), et la droite verticale \(h\) passant par \(d_i\). Soient \(\mathcal{D}_L\) et \(\mathcal{D}_R\) les parties de \(\mathcal{D}\) à gauche et à droite de \(h\) (les points de \(\mathcal{D} \cap h\) sont dans les deux).

Les vecteurs \(\overrightarrow{d_ip}\), \(\overrightarrow{d_{i+1}d_{i+2}}\), \(\overrightarrow{d_id_{i+1}}\), \(\overrightarrow{d_{i-1}d_i}\) et \(\overrightarrow{pd_{i+1}}\) sont rangés par pente décroissante (au sens large). Donc \(\mathcal{D}_L\) translaté par \(\overrightarrow{d_ip}\) est encore dans \(\mathcal{D}\), ainsi que \(\mathcal{D}_R\) translaté par \(\overrightarrow{d_{i+1}p}\). Comme dans la preuve de l'affirmation 3, ces deux translatés recouvrent tous les points de \(N(p)\) au-dessus de \(\ell\), ainsi que ceux de \(\ell\) à gauche de \(p\) : cela fait déjà la moitié de \(N(p)\). Comme \(N(p)\) contient en plus \(d_i\) et \(d_{i+1}\), le point \(p\) est serré. \(\square\)

Les affirmations 3 et 4 montrent que \(\mathcal{D}\) (contenu dans \(\mathcal{Q}\)) est stable, donc \(\mathcal{D} \subseteq \mathcal{F}\) ; avec l'affirmation 2, \(\mathcal{D} = \mathcal{F}\). De plus, les points confortables de \(\mathcal{D}\) sont exactement les points du réseau de la \(\mathcal{V}\)-courbe. Il reste à les compter.

Rappelons la définition de \(\mathcal{K}_n\). Le segment correspondant à \(\vec v_i\) contient \(k_i\) points du réseau autres que son origine. Sur l'ensemble des segments, ces points épuisent tous les points du réseau de la \(\mathcal{V}\)-courbe, sauf \(d_0\) (le livret écrit \(d_1\) ; il faut lire \(d_0\), premier sommet de la courbe). Le nombre de points du réseau sur la \(\mathcal{V}\)-courbe est donc \(1 + \sum_{i=1}^m k_i\). Or \(\sum_{i=1}^m k_i\) est exactement le nombre de points de \(\mathcal{K}_n\), soit \(n^2\). La réponse est donc \(n^2 + 1\). \(\blacksquare\)

Remarques

Remarque 1. L'hypothèse que le processus s'arrête est inutile : il s'arrête pour tout \(n \geq 1\). En effet, les preuves des affirmations 3 et 4 n'utilisent pas vraiment cette hypothèse, et elles montrent ensemble que \(\mathcal{D}\) est stable. Seuls les papillons hors de \(\mathcal{D}\) (en nombre fini) peuvent donc s'envoler, ce qui ne prend qu'un temps fini. L'hypothèse a été ajoutée à l'énoncé pour éviter des détails techniques de finitude ; elle peut aussi simplifier d'autres arguments.

Remarque 2. La description de l'ensemble final \(\mathcal{F} = \mathcal{D}\) semble indispensable : le comité de sélection ne connaît aucune solution qui l'évite complètement. En revanche, une fois \(\mathcal{D}\) défini, la suite peut se faire de plusieurs façons. Par exemple, pour montrer que tous les papillons hors de \(\mathcal{D}\) s'envolent (en utilisant cette fois l'hypothèse que le processus s'arrête) :

  • On modifie le processus : à chaque minute, exactement un des papillons solitaires s'envole, jusqu'à ce qu'il n'y en ait plus. Le processus modifié s'arrête dans le même état final que l'original, car le plus grand ensemble stable (unique) reste l'ensemble final. Il suffit donc d'indiquer un ordre d'envol qui épuise \(\mathcal{Q} \setminus \mathcal{D}\).
  • Soit \(\mathcal{C}_0 = d_0d_1\ldots d_m\) la \(\mathcal{V}\)-courbe. On en prend une copie \(\mathcal{C}\) qu'on translate vers le bas jusqu'à ce que \(d_0\) soit sous l'origine, puis on la remonte continûment jusqu'à sa position initiale \(\mathcal{C}_0\). Chaque fois que \(\mathcal{C}\) rencontre des points du réseau, on fait s'envoler les papillons de ces points dans un certain ordre.
  • Soit \(\mathcal{C}' = d'_0d'_1\ldots d'_m\) une position où \(\mathcal{C}\) rencontre des papillons ; tous ceux situés sous \(\mathcal{C}'\) se sont déjà envolés. Soit \(b\) le plus bas papillon sur \(\mathcal{C}'\), et \(d'_id'_{i+1}\) un segment qui le contient, avec \(b \neq d'_{i+1}\) (possible car \(\mathcal{C}\) n'a pas encore atteint \(\mathcal{C}_0\)). Soit \(\ell\) la droite qui porte ce segment. Tous les papillons de \(N(b)\) sont sur \(\ell\) ou au-dessus, et ceux de \(\ell\) sont sur le segment \(d'_id'_{i+1}\) (le livret écrit \(d_id_{i+1}\) ; il s'agit du segment translaté). Ce segment contient au plus \(k_i\) papillons (dont \(b\)), sinon un papillon occuperait \(d'_{i+1}\), ce qui est impossible par le choix de \(b\). Donc \(b\) est solitaire et peut s'envoler. On passe ensuite au plus bas des papillons restants sur \(\mathcal{C}'\), et ainsi de suite.

Les affirmations 3 et 4 admettent aussi d'autres preuves, non présentées ici.