Problème de géométrie combinatoire

dgregory · June 2018

Les cases d'un échiquier $n \times n$ sont coloriées alternativement en rouge, bleu et vert de la façon suivante : chaque case rouge est à côté¹ d'une case bleue ; chaque case bleue est à côté d'une case verte ; chaque case verte est à côté d'une case rouge. En notant $r, b, v$ les nombres de cases rouges, bleues et vertes respectivement, montrer que :

$\bullet\ r \leq 3b, b \leq 3v, v \leq 3r\ ;$

$\bullet\ r \leq b + 4v, b \leq v + 4r, v \leq r + 4b.$

Le premier point est assez facile à prouver. Par exemple, pour la première inégalité, on peut avoir une case bleue au centre et autour d'elle trois cases rouges et une case verte (voir pièce jointe). Donc potentiellement, il peut y avoir trois fois plus de cases rouges que de cases bleues.

Par contre, je ne vois pas comment prouver le second point ($\ r \leq b + 4v, b \leq v + 4r, v \leq r + 4b$).

¹ : par "cases à côté", il faut comprendre que ces cases ont un côté commun. 76596

V@J · June 2018

Bonjour à tous,

Je pense avoir trouvé une solution en procédant comme suit.

On peut voir notre échiquier comme un graphe orienté : entre un sommet $R$ rouge et un sommet $B$ bleu, il y a une arête de $R$ vers $B$ ; pareil entre un sommet $B$ bleu et un sommet $V$ vert, ou entre un sommet $V$ vert et un sommet $R$ rouge.

En particulier, chaque sommet rouge est de degré total 4 et de degré sortant au moins 1, donc de degré entrant au plus 3. Ce faisant, $r$ est majoré par le nombre d'arêtes rouges-bleues, lui-même majoré par $3b$, d'où les premières inégalités (comme mentionné par dgregory).

Soit alors $V_0$ un sommet vert fixé. Il a $b_0$ parents bleus et $r_0$ grands-parents rouges. Si l'on montre que $r_0 \leqslant b_0 + 4$, on aura gagné, en effectuant une somme sur tous les sommets verts, comme précédemment.

Or, on sait déjà que $r_0 \leqslant 3 b_0$, donc que $r_0 \leqslant b_0 + 4$ si $b_0 \leqslant 2$. D'autre part, si $b_0 = 3$, n'oublions pas que $V_0$ a aussi un voisin rouge, disons $R_0$. Les grands-parents rouges de $V_0$ figurent nécessairement parmi les $8$ sommets à distance $2$ de $V_0$ (en distance Manhattan), mais le sommet situé de l'autre côté de $R_0$ ne peut être un grand-parent de $V_0$. Donc $r_0 \leqslant 7 = b_0 + 4$ dans ce cas aussi, ce qui conclut.

dgregory · June 2018

Bonjour à tous,
Merci V@J, ta solution est très jolie et elle me paraît tout à fait juste. Voici une autre approche (pour le deuxième point) qui je pense doit-être correct également. On construit itérativement une partition de l'échiquier en sous ensembles disjoints de la façon suivante :
$\bullet$ on prend une case verte ;
$\bullet$ ensuite, on lui associe toutes ses voisines¹ bleues ;
$\bullet$ enfin, on termine en ajoutant les voisines rouges des cases bleues de l'étape d'avant.
Cet algorithme génère quatre types de sous ensembles :
$\bullet$ une case verte seule sans bleues ni rouges ;
$\bullet$ une case verte avec une case bleue et de 0 à 3 rouges ;
$\bullet$ une case verte avec deux bleues (deux configurations possibles) et de 0 à 6 rouges ;
$\bullet$ une case verte avec trois bleues et de 0 à 7 rouges.
Cette partition est bien disjointe car les règles de coloriage décrites dans l'énoncé garantissent qu'une case bleue est forcément à côté d'une case verte donc elles "tombent" forcément dans un de ces sous ensembles ; de même, une case rouge est forcément à côté d'une case bleue donc elles "tombent" aussi dans un des sous ensembles de ses voisines bleues.
Dans chaque type de sous ensemble, on a $r_0 \leq b_0 + 4v_0$ ($v_0 = 1$ c'est la case verte de "départ") en reprenant les notations de V@J. Donc en sommant sur tous les sous ensembles, on a bien $r \leq b + 4v$.

¹ : c'est-à-dire des cases ayant un côté commun

PierreB · July 2018

Bonjour,

à propos de cet énoncé, il me semble que pour une couleur donnée, la proportion maximale de cases est $\dfrac 2 3$, et la proportion minimale est $\dfrac{1}{11}$, même si c'est super pénible à écrire proprement (pour autant que ce soit vrai).

Peut-on savoir d'où sort cet énoncé? Y a-t-il une référence quelque part?

Merci.

Pierre.