← Toutes les ressources

combinatoire prépa recueilchapitre 7invariantscoloriages

Les quatre coins d'un rectangle

Recueil COMIMa — Techniques de résolution de problèmes · 2026 · Madagascar ·

Énoncé

Une grille rectangulaire comporte $m$ lignes et $n$ colonnes. Toutes les cases sont initialement blanches.

Une opération consiste à choisir deux lignes et deux colonnes, puis à changer la couleur des quatre cases situées à leurs intersections.

  1. Montrer que, dans chaque ligne, la parité du nombre de cases noires est invariante.
  2. Montrer de même que, dans chaque colonne, cette parité est invariante.
  3. En déduire que toute configuration accessible possède un nombre pair de cases noires dans chaque ligne et dans chaque colonne.
  4. Réciproquement, considérer une configuration possédant cette propriété. Pour chaque case noire $(i, j)$, avec $i < m$ et $j < n$, effectuer l'opération sur les lignes $i, m$ et les colonnes $j, n$.
  5. Montrer que cette procédure permet d'effacer toutes les cases noires.
  6. Conclure qu'une configuration est accessible si et seulement si chaque ligne et chaque colonne contient un nombre pair de cases noires.

Aperçu rendu par KaTeX — la mise en page exacte est celle du PDF compilé.

Source & crédits

Origine : Recueil COMIMa — Techniques de résolution de problèmes · 2026 · Madagascar

Reproduit à des fins pédagogiques non commerciales. Les droits sur l’énoncé original appartiennent à ses auteurs / à l’organisateur du concours.

Téléchargements

Les PDF sont générés par le pipeline GitHub Actions : ils peuvent être absents en développement local.

+ Ajouter au sujet