Forum de mathématiques - Bibm@th.net

dgregory

Membre

Inscription : 03-06-2018

Messages : 9

Géométrie combinatoire

Bonjour,

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

¹ : deux cases son "à côté" signifie que ces cases ont un côté commun.

Dernière modification par yoshi (03-06-2018 17:43:19)

dgregory

Membre

Inscription : 03-06-2018

Messages : 9

Re : Géométrie combinatoire

Voici une solution (pour le deuxième point) qui je pense est correct. On construit itérativement une partition de l'échiquier en sous ensembles disjoints de la façon suivante :
[tex]\bullet[/tex] on prend une case verte ;
[tex]\bullet[/tex] ensuite, on lui associe toutes ses voisines¹ bleues ;
[tex]\bullet[/tex] 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 :
[tex]\bullet[/tex] une case verte seule sans bleues ni rouges ;
[tex]\bullet[/tex] une case verte avec une case bleue et de 0 à 3 rouges ;
[tex]\bullet[/tex] une case verte avec deux bleues (deux configurations possibles) et de 0 à 6 rouges ;
[tex]\bullet[/tex] 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 sous ensemble [tex]k[/tex], on a [tex]r_k \leq b_k + 4v_k[/tex] ([tex]v_k = 1[/tex] c'est la case verte de "départ") en notant [tex]r_k, b_k, v_k[/tex] les nombres de cases rouge(s), bleue(s), verte du sous ensemble [tex]k[/tex]. Donc en sommant sur tous les sous ensembles, on a bien [tex]r \leq b + 4v[/tex].

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