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é

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\).

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\)