Aller au contenu

Shortlist 2023, C1

Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : Thailand

Concepts : Coloriages et pavages · Invariants et monovariants

Solution officielle : Shortlist officielle 2023 (avec solutions), p. 33 (page 35 du PDF)

Énoncé

Let \(m\) and \(n\) be positive integers greater than \(1\). In each unit square of an \(m \times n\) grid lies a coin with its tail-side up. A move consists of the following steps:

  1. select a \(2 \times 2\) square in the grid;
  2. flip the coins in the top-left and bottom-right unit squares;
  3. flip the coin in either the top-right or bottom-left unit square.

Determine all pairs \((m, n)\) for which it is possible that every coin shows head-side up after a finite number of moves.

Indices : les idées clés
  • Construction par blocs \(3 \times 2\) : deux coups bien choisis retournent exactement les six pièces d'un rectangle \(3 \times 2\) ; une colonne restante se traite par trois coups.
  • Coloriages et pavages : on étiquette la case \((i, j)\) par le reste de \(i + j - 2\) modulo \(3\) ; chaque coup retourne exactement une pièce de chaque étiquette.
  • Invariants et monovariants : les parités de \(T(0) - T(1)\) et \(T(1) - T(2)\) ne changent pas, ce qui impose \(3 \mid mn\).
  • Un invariant dans le corps à quatre éléments (remarque 3) : \(\sum \omega^{i+j}\) sur les pièces côté face.
Solutions

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

Réponse : tous les couples \((m, n)\) tels que \(3 \mid mn\).

Solution 1

On note \((i, j)\) la case de la \(i\)-ième ligne et de la \(j\)-ième colonne.

Construction lorsque \(3 \mid mn\). Pour \(1 \leq i \leq m - 1\) et \(1 \leq j \leq n - 1\), notons \(A(i, j)\) le coup qui retourne les pièces des cases \((i, j)\), \((i+1, j+1)\) et \((i, j+1)\), et \(B(i, j)\) celui qui retourne les pièces des cases \((i, j)\), \((i+1, j+1)\) et \((i+1, j)\). Sans perte de généralité, supposons \(3 \mid m\).

Cas 1 : \(n\) pair. On applique les coups

  • \(A(3k-2, 2l-1)\) pour tous \(1 \leq k \leq \frac{m}{3}\) et \(1 \leq l \leq \frac{n}{2}\),
  • \(B(3k-1, 2l-1)\) pour tous \(1 \leq k \leq \frac{m}{3}\) et \(1 \leq l \leq \frac{n}{2}\).

Pour \(k, l\) fixés, ces deux coups retournent exactement une fois chacune des six cases du bloc formé des lignes \(3k-2, 3k-1, 3k\) et des colonnes \(2l-1, 2l\). Chaque pièce est donc retournée exactement une fois, et toutes montrent face à la fin.

Cas 2 : \(n\) impair. On commence par appliquer

  • \(A(3k-2, 2l-1)\) pour tous \(1 \leq k \leq \frac{m}{3}\) et \(1 \leq l \leq \frac{n-1}{2}\),
  • \(B(3k-1, 2l-1)\) pour tous \(1 \leq k \leq \frac{m}{3}\) et \(1 \leq l \leq \frac{n-1}{2}\),

comme dans le cas précédent. À ce stade, les pièces de la dernière colonne montrent pile et toutes les autres montrent face. On applique alors les coups

  • \(A(3k-2, n-1)\), \(A(3k-1, n-1)\) et \(B(3k-2, n-1)\) pour chaque \(1 \leq k \leq \frac{m}{3}\).

Pour chaque \(k\), ces trois coups retournent exactement les pièces des cases \((3k-2, n)\), \((3k-1, n)\) et \((3k, n)\) (les cases \((3k-2, n-1)\) et \((3k-1, n-1)\) sont retournées deux fois, la case \((3k-1, n)\) trois fois). Après ce processus, toutes les pièces montrent face.

La condition \(3 \mid mn\) est nécessaire. On colorie (étiquette) la case \((i, j)\) par le reste de \(i + j - 2\) dans la division par \(3\) :

\[\begin{array}{ccccc} 0 & 1 & 2 & 0 & \cdots \\ 1 & 2 & 0 & 1 & \cdots \\ 2 & 0 & 1 & 2 & \cdots \\ 0 & 1 & 2 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array}\]

Soit \(T(c)\) le nombre de pièces montrant face dans les cases d'étiquette \(c\). L'observation principale est qu'un coup ne change ni la parité de \(T(0) - T(1)\), ni celle de \(T(1) - T(2)\), puisqu'un coup retourne exactement une pièce de chaque étiquette (les étiquettes de \((i, j)\), \((i, j+1)\) ou \((i+1, j)\), et \((i+1, j+1)\) sont \(c\), \(c+1\), \(c+2\) modulo \(3\)). C'est un invariant. Au départ, toutes les pièces montrent pile, donc \(T(0) = T(1) = T(2) = 0\). Toute configuration accessible vérifie donc

\[T(0) \equiv T(1) \equiv T(2) \pmod 2.\]

Calculons les valeurs de \(T\) pour la configuration où toutes les pièces montrent face.

  • Si \(m \equiv n \equiv 1 \pmod 3\) : \(T(0) - 1 = T(1) = T(2) = \frac{mn - 1}{3}\).
  • Si \(m \equiv 1\) et \(n \equiv 2 \pmod 3\), ou \(m \equiv 2\) et \(n \equiv 1 \pmod 3\) : \(T(0) - 1 = T(1) - 1 = T(2) = \frac{mn - 2}{3}\).
  • Si \(m \equiv n \equiv 2 \pmod 3\) : \(T(0) = T(1) - 1 = T(2) = \frac{mn - 1}{3}\).
  • Si \(m \equiv 0\) ou \(n \equiv 0 \pmod 3\) : \(T(0) = T(1) = T(2) = \frac{mn}{3}\).

Ce calcul montre que \(T(0)\), \(T(1)\) et \(T(2)\) ont la même parité seulement lorsque \(3 \mid mn\). \(\blacksquare\)

Remarques

Remarque 1 (partie (b) de la proposition originale). La proposition originale demandait aussi : pour chaque couple \((m, n)\) d'entiers supérieurs à \(1\), combien de configurations peut-on obtenir par un nombre fini de coups ? Une construction explicite montre que la condition « \(T(0)\), \(T(1)\), \(T(2)\) de même parité » est nécessaire et suffisante pour qu'une configuration soit accessible ; la réponse est \(2^{mn-2}\).

Remarque 2 (nombre minimal de coups). Un problème nettement plus difficile : lorsque la tâche est possible (\(3 \mid mn\)), quel est le nombre minimal de coups ? La réponse est \(\frac{mn}{3}\) si \(mn\) est pair, et \(\frac{mn}{3} + 2\) si \(mn\) est impair. On observe qu'il faut au minimum deux coups pour retourner toutes les pièces d'un rectangle \(2 \times 3\) (ou \(3 \times 2\)). De plus, lorsque \(mn\) est impair avec \(3 \mid mn\), il est impossible de paver un tableau \(m \times n\) avec un type de L-tromino et son image par la rotation de \(180^\circ\) (sans autres rotations ni symétries). La seule preuve connue de ce dernier fait est longue et difficile : elle utilise des arguments de théorie des groupes (le « groupe d'homotopie de pavage » de ces deux tuiles), technique développée par J. H. Conway et J. C. Lagarias (Tiling with Polyominoes and Combinatorial Group Theory, Journal of Combinatorial Theory, Series A 53, 183–208, 1990).

Remarque 3 (un invariant élégant). On considère le corps fini \(\mathbb{F}_4 = \{0, 1, \omega, \omega + 1\}\), où \(1 + 1 = \omega^2 + \omega + 1 = 0\). Soit \(H\) l'ensemble des cases \((i, j)\) dont la pièce montre face, et

\[I(H) = \sum_{(i,j) \in H} \omega^{i+j} \in \mathbb{F}_4.\]

Un coup ajoute \(\omega^{c}(1 + \omega + \omega^2) = 0\), donc \(I(H)\) ne change pas ; au départ, \(I(H) = 0\). Lorsque toutes les pièces montrent face,

\[I(H) = \sum_{i=1}^{m} \sum_{j=1}^{n} \omega^{i+j} = \left(\sum_{i=1}^{m} \omega^i\right)\left(\sum_{j=1}^{n} \omega^j\right),\]

qui vaut \(0\) dans \(\mathbb{F}_4\) si et seulement si \(3 \mid mn\).