Aller au contenu

Shortlist 2011, C5

Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : non indiqué

Concepts : Invariants et monovariants · Bijections et dénombrement

Solution officielle : Shortlist officielle 2011 (avec solutions), p. 35 (page 36 du PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

Soit \(m\) un entier strictement positif, et considérons un damier de \(m\) sur \(m\) cases unité. Au centre de certaines de ces cases se trouve une fourmi. À l'instant \(0\), chaque fourmi se met en mouvement à la vitesse \(1\), parallèlement à l'un des bords du damier. Quand deux fourmis allant en sens opposés se rencontrent, elles tournent toutes deux de \(90^\circ\) dans le sens des aiguilles d'une montre et continuent à la vitesse \(1\). Quand plus de deux fourmis se rencontrent, ou quand deux fourmis allant dans des directions perpendiculaires se rencontrent, les fourmis continuent dans la même direction qu'avant leur rencontre. Quand une fourmi atteint l'un des bords du damier, elle tombe et ne réapparaît plus.

En considérant toutes les positions de départ possibles, déterminer le dernier instant possible où la dernière fourmi tombe du damier, ou montrer qu'un tel instant n'existe pas forcément.

Énoncé original (anglais)

Let \(m\) be a positive integer and consider a checkerboard consisting of \(m\) by \(m\) unit squares. At the midpoints of some of these unit squares there is an ant. At time \(0\), each ant starts moving with speed \(1\) parallel to some edge of the checkerboard. When two ants moving in opposite directions meet, they both turn \(90^\circ\) clockwise and continue moving with speed \(1\). When more than two ants meet, or when two ants moving in perpendicular directions meet, the ants continue moving in the same direction as before they met. When an ant reaches one of the edges of the checkerboard, it falls off and will not re-appear.

Considering all possible starting positions, determine the latest possible moment at which the last ant falls off the checkerboard or prove that such a moment does not necessarily exist.

Indices : les idées clés
  • Exemple : deux fourmis aux coins sud-ouest et sud-est, face à face ; après leur collision, celle qui part vers le nord reste encore \(m - 1\) unités de temps, soit \(\frac{3m}{2} - 1\) au total.
  • Changer la règle sans rien changer (bijection) : faire tourner deux fourmis dans le sens inverse revient à échanger leurs rôles ; on peut donc supposer que les fourmis ne vont que vers le nord-est ou le sud-ouest (puis nord-ouest ou sud-est).
  • Région de collision (monovariant) : une collision au temps \(t\) a lieu dans \(B(t) = \{t + 1 \leq x + y \leq 2m - t - 1, \; \lvert x - y \rvert \leq m - t - 1\}\), d'où \(\min\{x, y\} \geq t + 1 - \frac{m}{2}\) après la dernière collision.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2011 (une solution).

Réponse : le dernier instant possible est \(\frac{3m}{2} - 1\).

Solution

Pour \(m = 1\), la réponse est clairement correcte ; supposons donc \(m > 1\). Dans la suite, le mot collision désigne la rencontre d'exactement deux fourmis se déplaçant en sens opposés.

Si au départ on place une fourmi sur la case du coin sud-ouest, tournée vers l'est, et une fourmi sur la case du coin sud-est, tournée vers l'ouest, elles se rencontrent au milieu de la rangée du bas au temps \(\frac{m - 1}{2}\). Après la collision, la fourmi qui part vers le nord reste sur le plateau encore \(m - \frac{1}{2}\) unités de temps ; on obtient ainsi un exemple où la dernière fourmi tombe au temps \(\frac{m - 1}{2} + m - \frac{1}{2} = \frac{3m}{2} - 1\). Il reste à prouver que c'est le dernier instant possible.

Considérons une collision de deux fourmis \(a\) et \(a'\). Changeons la règle pour cette collision, en forçant ces deux fourmis à tourner dans le sens inverse des aiguilles d'une montre. La suite du comportement de toutes les fourmis ne change pas ; la seule différence est que \(a\) et \(a'\) échangent leurs positions. Cet argument s'applique à chaque collision séparément ; on peut donc supposer qu'à chaque collision, les deux fourmis tournent toutes deux dans le sens des aiguilles d'une montre ou toutes deux dans le sens inverse, à notre choix.

Par exemple, on peut supposer qu'il n'y a que deux types de fourmis selon leur direction initiale : les fourmis NE, qui ne vont que vers le nord ou l'est, et les fourmis SO, qui ne vont que vers le sud ou l'ouest. On obtient immédiatement que toutes les fourmis sont tombées après \(2m - 1\) unités de temps. On obtient cependant une meilleure borne en considérant le dernier instant où une fourmi donnée entre en collision avec une autre.

Choisissons un repère tel que les coins du plateau soient \((0, 0)\), \((m, 0)\), \((m, m)\) et \((0, m)\). Au temps \(t\), il n'y a aucune fourmi NE dans la région \(\{(x, y) : x + y < t + 1\}\) et aucune fourmi SO dans la région \(\{(x, y) : x + y > 2m - t - 1\}\). Donc, si deux fourmis entrent en collision en \((x, y)\) au temps \(t\), on a

\[t + 1 \leq x + y \leq 2m - t - 1. \tag{1}\]

De même, on peut changer les règles pour que chaque fourmi se déplace alternativement vers le nord et l'ouest, ou alternativement vers le sud et l'est. On obtient ainsi, en plus de (1), \(\lvert x - y \rvert \leq m - t - 1\) pour toute collision au point \((x, y)\) au temps \(t\).

Pour visualiser cela, posons

\[B(t) = \big\{(x, y) \in [0, m]^2 : t + 1 \leq x + y \leq 2m - t - 1 \text{ et } \lvert x - y \rvert \leq m - t - 1\big\}.\]

Une fourmi ne peut entrer en collision avec une autre au temps \(t\) que si elle est dans la région \(B(t)\). La figure représente \(B(t)\) pour \(t = \frac{1}{2}\) et \(t = \frac{7}{2}\) dans le cas \(m = 6\).

Figure (solution)

Supposons maintenant qu'une fourmi NE ait sa dernière collision au temps \(t\), au point \((x, y)\) (si la fourmi n'entre jamais en collision, elle tombe en moins de \(m - \frac{1}{2} < \frac{3m}{2} - 1\) unités de temps, et l'on peut ignorer ce cas). Alors \((x, y) \in B(t)\), donc \(x + y \geq t + 1\) et \(x - y \geq -(m - t - 1)\). On obtient

\[x \geq \frac{(t + 1) - (m - t - 1)}{2} = t + 1 - \frac{m}{2}.\]

Par symétrie, \(y \geq t + 1 - \frac{m}{2}\) aussi, donc \(\min\{x, y\} \geq t + 1 - \frac{m}{2}\). Après cette collision, la fourmi va directement vers un bord, ce qui prend au plus \(m - \min\{x, y\}\) unités de temps. Au total, la fourmi reste sur le plateau au plus

\[t + \big(m - \min\{x, y\}\big) \leq t + m - \left(t + 1 - \frac{m}{2}\right) = \frac{3m}{2} - 1.\]

Par symétrie, la même borne vaut pour les fourmis SO. \(\blacksquare\)

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2025 N5 ★★★☆☆ : Chaque terme d'un triplet augmente du PGCD des deux autres, \(2025\) fois de suite : quelle valeur minimale pour \(a_{2025}\) ?
  • 2011 C3 ★★★☆☆ · OIM P2 : Une droite tourne autour d'un point et change de pivot à chaque point rencontré : bien lancée, elle passe une infinité de fois par chaque point.
  • 2007 C4 ★★★☆☆ : On ajoute \(\pm 1\) selon la partition la plus équilibrée, encore et encore : un terme finit par atteindre \(n/2\) en valeur absolue.
  • 2006 C4 ★★★☆☆ : Deux placements de fraises, une par ligne et par colonne, comparés par rectangles de coin : on passe de l'un à l'autre par des échanges élémentaires.