Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

Problème de géométrie combinatoire

Posté par
g0217d
02-06-18 à 19:03

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 suivie d'une case bleue ; chaque case bleue est suivie d'une case verte ; chaque case verte est suivie 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).

Problème de géométrie combinatoire

Posté par
carpediem
re : Problème de géométrie combinatoire 02-06-18 à 19:07

salut

ça veut dire quoi "être suivie de" sur un échiquier ?

Posté par
g0217d
re : Problème de géométrie combinatoire 02-06-18 à 19:09

Salut, ça signifie que les cases sont adjacents.

Posté par
carpediem
re : Problème de géométrie combinatoire 02-06-18 à 19:20

super !!!

ne comprends-tu pas que dans le plan ça ne veut rien dire !!!

peux-tu compléter ta figure pour montrer ce qui se passe sur un échiquier de 16 cases ?

parce que pour moi : (si) la case bleue suit la case rouge (de gauche) alors elle précède la case rouge de droite !!!

quant à la case rouge au dessus ... ben à part dire qu'elle est au-dessus ...

Posté par
g0217d
re : Problème de géométrie combinatoire 02-06-18 à 19:36

Voici un exemple qui devrait être bon.

Problème de géométrie combinatoire

Posté par
mathafou Moderateur
re : Problème de géométrie combinatoire 02-06-18 à 21:18

Bonjour,

cet "exemple" montre surtout que tu ne comprends pas la différence entre
"suivante" qui impose une notion d'ordre (la case "avant" et la cade "après")
et "adjacente" qui n'en contient pas
et qui ne peut pas être utilisée ici du tout, quoi que tu fasses

Problème de géométrie combinatoire

tes cases vertes adjacentes sont en violation totale avec
chaque case verte est "suivie" d'une case rouge.
vu que selon le sens (ordre !!) dans lequel on les parcours, il y a toujours une de ces cases vertes qui est "suivie" d'une case verte et pas rouge.

Posté par
g0217d
re : Problème de géométrie combinatoire 02-06-18 à 22:47

Effectivement le terme de "suivant" n'est pas adapté. En fait l'énoncé original1 parle de "cases à côtés" (donc ça correspond à "adjacent" il me semble). Donc en reformulant la partie de la consigne incriminée ça donne : "[...] 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 [...]".

Du coup, il me semble que dans l'exemple ci-dessus, les trois cases vertes pointées par mathafou sont bien à côté d'une case rouge ; de même, les cases bleus sont à côté d'une case verte et les cases rouges sont à côté d'une case bleue.  

1 : en pièce jointe un autre exemple donné avec l'énoncé original.

Problème de géométrie combinatoire

Posté par
cocolaricotte
re : Problème de géométrie combinatoire 02-06-18 à 22:54

Et au départ on a quel choix ?

On choisit comment la couleur suivante ? Où ? Comment ?

Un énoncé mal résumé et mal raconté = aide inadaptée au problème posé  

Posté par
g0217d
re : Problème de géométrie combinatoire 02-06-18 à 23:35

De base l'énoncé est :

Citation :
Les cases d'un échiquier de dimension n \times n sont peintes en rouge, bleu et vert de manière que, juste à côté d'une case rouge, il y ait une case bleue , juste à côté d'une case bleue soit située une case verte et juste à côté d'une case verte soit placée une case rouge (les cases correspondantes ayant un côté commun). Montrer que pour le nombre r de cases rouges les inégalités suivantes sont vérifiées :

a)\ r \leq \dfrac{2n^2}{3}

b)\ r \geq \dfrac{n^2}{11}.


Mais on déduit facilement a) et b) des inégalités de la consigne que j'ai donnée ici.

Posté par
verdurin
re : Problème de géométrie combinatoire 02-06-18 à 23:42

Bonne nuit g0217d.
L'énoncé exact est plus court que celui que tu postas dans ton premier message.

Je me demande vraiment quel est l'intérêt que tu peux avoir à poster un énoncé erroné.

Posté par
g0217d
re : Problème de géométrie combinatoire 05-06-18 à 21:13

Merci pour vos remarques ; merci cocolaricotte et verdurin pour votre précieuse aide. 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 :
\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 sous ensemble k, on a r_k \leq b_k + 4v_k (v_k = 1 c'est la case verte de "départ") en notant r_k, b_k, v_k les nombres de cases rouge(s), bleue(s), verte du sous ensemble k. 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



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1741 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !