Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
169 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Problème de géométrie combinatoire

Envoyé par dgregory 
Problème de géométrie combinatoire
l’an passé
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é1 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$).

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



Edité 2 fois. La dernière correction date de l’an passé et a été effectuée par dgregory.


V@J
Re: Problème de géométrie combinatoire
l’an passé
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.
Re: Problème de géométrie combinatoire
l’an passé
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 voisines1 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$.

1 : c'est-à-dire des cases ayant un côté commun
Re: Problème de géométrie combinatoire
l’an passé
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.
Re: Problème de géométrie combinatoire
l’an passé
Bonjour,
Oui c'est exact ; c'est un problème issu des "Mathématiques du COK" (Marc Bachmakov, 1999 aux éditions du Kangourou).
Bonne soirée
Re: Problème de géométrie combinatoire
l’an passé
Oh, je n'avais pas vu ce message... Merci!

Pierre.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 137 378, Messages: 1 329 957, Utilisateurs: 24 418.
Notre dernier utilisateur inscrit Edouardo01.


Ce forum
Discussions: 748, Messages: 6 022.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page