Valeurs différentes pour régions limitrophes

Bonjour Sil et bienvenue.

Le problème relève plutôt d'un mélange entre topologie et théorie des graphes mais ce n'est pas important.

Je ne comprends pas la phrase :

Sil a écrit:

Il ne doit pas y avoir 2 régions adjacentes avec une/plusieurs valeurs identiques.

En fait, je ne comprends pas bien ce que tu veux dire par « valeurs ». Tu auras compris que le nom des couleurs n'a pas d'importance et qu'il n'est pas important que ce soient même des noms de couleurs : des nombres, des lettres ou n'importe quoi d'autre feraient aussi bien l'affaire.

Quand tu parles de « couples de valeurs », je comprends que tu colories la carte avec quatre couleurs qui sont des couples comme $(1,1)$, $(1,2)$, $(2,1)$ et $(2,2)$ et que tu cherches à réduire le nombre de couleurs de quatre à trois.

En général, ce n'est pas possible : par exemple la carte ci-dessous ne peut pas être coloriée avec trois couleurs seulement. Autrement dit, le théorème des quatre couleurs est optimal (il n'y a pas de théorème de trois couleurs).

Cela dit, je ne suis pas sûr d'avoir compris la question...

Si tu avais 12 couleurs ... le théorème des 4 couleurs te garantirait qu'il y a au moins une solution (et même plein de solutions en l'occurence).
Mais tu n'as que 8 couleurs.

Si on prend la forme de patatoïde proposée par Math-Coss, il y a 4 régions, et les 4 régions ont toutes une frontière commune. Donc quand tu as utilisé les couleurs A B C pour la région 1, tu ne peux plus les utiliser pour aucune des 3 autres régions.
Tu utilises les couleurs D E F pour la région 2... et déjà, pour colorier la région n°3, tu est coincé, tu ne peux pas trouver 3 couleurs nouvelles, tu n'as plus que les 2 couleurs G et H qui sont autorisées.

Dans ton pays tu as 31 régions, Sauf miracle, tu as forcément une configuration similaire à celle proposée par Mathcoss.

Et même avec des situations plus simples, tu arrives très vite à un blocage.
Avec 3 régions qui ont des frontières communes 2 à 2 (Bretagne Normandie et Pays de la Loire pour se fixer les idées) ; tu utilises 3 couleurs pour la Bretagne, puis 3 couleurs pour la Normandie, et il ne te reste que 2 couleurs pour les Pays de la Loire. Blocage, dès qu'on a 3 régions limitrophes 2 à 2 !

Si tes frontières forment un beau quadrillage (comme un échiquier), alors, miracle, tu vas pouvoir t'en sortir. tu pourras même t'en sortir en utilisant seulement 6 couleurs. Mais c'est le seul cas où tu pourras trouver un coloriage adéquat.