Enigme Les couleurs de la France @ Prise2Tete

scarta · #1

Il existe un "théorème" en théorie des graphes, appelé
théorème des 4 couleurs.
Les guillemets sont là pour indiquer une particularité intéressante : ce théorème a été démontré, plusieurs fois, mais à chaque fois en utilisant un ordinateur pour cela. En conséquence, le résultat est vrai, mais la méthode utilisée reste un problème.

Enfin, bon, ce théorème affirme la chose suivante : pour colorier une carte en utilisant des couleurs différentes pour des régions adjacentes, 4 couleurs suffisent, résultat bien connu je pense de beaucoup de P2T-iens qui ont eu un jour une carte à colorier en cours de géographie.
D'ailleurs, en parlant de cours de géographie, quand je repense à toutes ces heures passées à apprendre les différentes régions de France alors que tout à changé ensuite...
Mais au fait ! Il y a maintenant 13 "nouvelles régions". Le tableau ci-dessous indique celles qui sont adjacentes.
Question: 4 couleurs suffisent, mais combien de coloriages distincts peut-on réaliser sur une carte de France avec seulement 4 couleurs ?

Note: inutile de les compter toutes une par une, il y en a vraiment beaucoup
Cependant, le but de P2T étant entre autres d'apprendre de nouvelles choses, il existe un moyen de calculer ça à la main (enfin disons, sans utiliser un programme, et avec au plus une calculatrice de collège)

Code:

                                       Auvergne-Rhône-Alpes            Bourgogne-Franche-Comté                   Bretagne                    Centre-Val de Loire                      Corse                           Grand Est                      Hauts-de-France                    Île-de-France                       Normandie                     Nouvelle-Aquitaine                    Occitanie                      Pays de la Loire             Provence-Alpes-Côte d'Azur  
     Auvergne-Rhône-Alpes                                                         X                                                                   X                                                                                                                                                                                                           X                                 X                                                                   X               
   Bourgogne-Franche-Comté                      X                                                                                                     X                                                                   X                                                                   X                                                                                                                                                                                         
           Bretagne                                                                                                                                                                                                                                                                                                             X                                                                                                     X                                                 
     Centre-Val de Loire                        X                                 X                                                                                                                                                                                                           X                                 X                                 X                                                                   X                                                 
            Corse                                                                                                                                                                                                                                                                                                                                                                                                                                                                       
          Grand Est                                                               X                                                                                                                                                                         X                                 X                                                                                                                                                                                         
       Hauts-de-France                                                                                                                                                                                                    X                                                                   X                                 X                                                                                                                                                       
        Île-de-France                                                             X                                                                   X                                                                   X                                 X                                                                   X                                                                                                                                                       
          Normandie                                                                                                 X                                 X                                                                                                     X                                 X                                                                                                                                       X                                                 
      Nouvelle-Aquitaine                        X                                                                                                     X                                                                                                                                                                                                                                             X                                 X                                                 
          Occitanie                             X                                                                                                                                                                                                                                                                                                                 X                                                                                                     X               
       Pays de la Loire                                                                                             X                                 X                                                                                                                                                                         X                                 X                                                                                                                     
  Provence-Alpes-Côte d'Azur                    X                                                                                                                                                                                                                                                                                                                                                   X

zobizob · #2

20736=4!*4*2^3*(2*6+3*5)

Ebichu · #3

Salut Scarta,

on trouve 20736.

Si on colorie toutes les régions sauf la Bretagne, comme elle est reliée à deux régions voisines, il reste deux couleurs possibles pour elle. Elle va donc contribuer par un facteur 2 au décompte total. De même pour la région PACA, puis pour l'Occitanie. Les Corses, eux, c'est un facteur 4. On peut ainsi déjà enlever ces 4 régions qui contribueront pour un facteur 32 au total.

Il reste à compter le nombre de coloriages possibles pour une configuration formée d'une région de degré 5 (Ile-de-France) touchant une région de degré 6 (Centre), ainsi que leur anneau. Je colorie d'abord le triangle Ile-de-France/Centre/Bourgogne, qui utilise forcément 3 couleurs (de 24 façons possibles). Ou bien la région Normandie a la même couleur que Bourgogne, et on peut terminer de 2*6 façons (2 façons pour les deux régions restant au nord et 6 façons pour les 3 régions restant au sud), ou bien non, et on peut terminer de 3*5 façons.

Finalement cela fait 32*24*(2*6+3*5)=20736.

Ebichu · #4

Par ailleurs, c'est original et intéressant de proposer une énigme de ce type, j'apprécie beaucoup. Néanmoins je voudrais rebondir sur :

ce théorème a été démontré, plusieurs fois, mais à chaque fois en utilisant un ordinateur pour cela. En conséquence, le résultat est vrai, mais la méthode utilisée reste un problème.

Pourquoi dis-tu que c'est un problème ? Le recours à un ordinateur n'est selon moi pas un problème quand il s'agit de faire un grand nombre de calculs simples et répétitifs.

Quand il s'agit d'un programme comportant des milliers de lignes de code, je veux bien que l'on se méfie. Mais dans le cas de la preuve originale de Appel et Haken, l'ordinateur était là pour mener des calculs idiots (pour plusieurs centaines de configurations, à chaque fois, tester tous les coloriages possibles de leur anneau, à savoir, parfois plusieurs millions, pour voir si on peut les prolonger à l'intérieur de la configuration). Le principal problème de la preuve de Appel et Haken était la partie manuelle, à savoir le problème de l'inévitabilité, qui était tellement compliquée que lorsque Robertson et al ont essayé de refaire la preuve de Appel et Haken pour la vérifier, ils ont trouvé plus simple d'en recommencer une de zéro...

Pour prendre une métaphore, regarde ce problème (désolé pour l'auto-promotion) :

http://www.prise2tete.fr/forum/viewtopic.php?id=12850

Sans ordinateur, il est impossible de mener à bien cet exercice qui nécessite des centaines de milliers d'opérations. Pourtant, la partie programmation est tellement simple qu'on ne peut qu'être sûr du résultat obtenu.

scarta · #5

C'est vrai. Mais
1) la probabilité d'un bitflip quelconque est non nulle. Très faible, mais bon non nulle quand même. Un ordinateur te montrera que le résultat est valide avec une probabilité epsilonesque de se tromper. Mais ça n'est pas une preuve formelle.
2) Erdös et d'autres prétendent qu'un problème aussi élémentaire devrait avoir une solution élégante et "manuelle". J'ai tendance à penser pareil, y compris dans le cas général, même si les mathématiques d'aujourd'hui ne sont peut-être pas assez avancées pour y répondre.
Et j'aime beaucoup ta méthode pour répondre, elle est très proche d'une méthode générique que j'ai utilisée pour calculer le résultat.

NB : c'est certainement pas moi qui reprocherais à qui que ce soit l'usage d'un ordinateur
Vu la réputation que j'ai eu ici par le passé...

Ebichu · #6

La probabilité epsilonesque d'erreur de la machine (avec epsilon arbitrairement petit, il suffit de demander à la machine de refaire le calcul pour abaisser epsilon !) est totalement négligeable au regard de la probabilité de bitflip cérébral... Ce qui fait qu'on peut avoir bien plus confiance en le théorème des 4 couleurs que, par exemple, la classification des groupes simples finis.

Après, je suis d'accord qu'une preuve du théorème des 4 couleurs sans machine et d'une taille raisonnable serait intéressante, si elle existait. Mais serait-elle plus poétique ? J'aime l'idée que pour démontrer un résultat aussi élémentaire, il faille avoir recours à l'étude d'un très grand nombre de cas.

scarta · #7

Bonne réponse de ceux qui ont répondu.
Ebichu détaille la méthode, mais elle se généralise encore plus que ça.

Le "polynôme chromatique" est un polynôme, calculé pour un graphe donné, qui à N le nombre de couleurs utilisées fait correspondre le nombre de coloriage possible. Ce problème revenait donc à trouver ce polynôme et à regarder sa valeur pour N=4.

On peut montrer que ce polynôme est de degré S, nombre de sommets du graphe en question.
On peut aussi montrer que :
- pour S noeuds isolés, il vaut N^S
- pour un graphe complet (tous les sommets reliés 2 à 2), il vaut N(N-1)(N-2)...(N-S+1), soit (S parmi N).S!

Pour un graphe quelconque, soit f la fonction qui à un graphe G fait correspondre son polynôme P.
Considérons 2 sommets reliés de G. On note Gd le graphe G dans lequel la liaison en question est supprimée, et Gc le graphe G dans lequel les deux sommets en question sont fusionnés. On a alors
f(G) = f(Gd) - f(Gc)
On peut alors, au choix :
- utiliser cette méthode pour arriver, au final, à des graphes sans aucune liaisons (donc une somme de monômes)
- inversement, utiliser la même méthode à l'envers pour ajouter des liaisons et atteindre un graphe complet.
La méthode retenue dépendra bien entendu du graphe, afin de finir la récurrence plus rapidement. A noter que si G est composé de G', G'´, ... un ensemble de graphes disjoints, alors f(G) est le produit des f(G').f(G'´)... La méthode retenue peut donc varier d'un sous graphe a un autre.

Au final, on arrive à quelques cas particuliers intéressants (identifiés par Ebichu) : quand un sommet n'est connecté au graphe que par une seule liaison, on peut supprimer ce sommet en ajoutant un facteur (N-1). Si 3 noeuds sont tous interconnectés, et qu'un des 3 est isolé (en dehors des 2 autres) alors pareil avec un facteur (N-2), et plus généralement, si un sommet a k voisins, tous connectés 2 à 2, on peut le supprimer moyennant un facteur (N-k)

Ebichu · #8

Je suis surpris que ce problème ait eu aussi peu de succès, c'était en tout cas très sympa de proposer une énigme originale comme celle-ci.

nodgim · #9

Perso, j'ai essayé, mais échoué.
Je voyais bien que dans le cas simple, triangulaire, on avait un multiple de 2 (la corse mise à part) mais je n'ai pas su géré les 2 cas complexes. Je n'ai pas compris pourquoi 20352 ne marchait pas.

scarta · #10

As-tu au moins compris pourquoi 20736 marche ?

En appliquant la méthode, on trouve le polynôme suivant
(x-3)(x-2)^4(x-1)x^2(x^2-5x+7)(x^3-6x^2+13x-11)

Ca peut se faire à la main, à condition de choisir les bonnes régions à chaque fois (commencer par la Corse, puis éliminer PACA et Bretagne, etc...)

Et pour x=4, on retrouve bien le résultat annoncé

Franky1103 · #11

@Ebichu: Le succès ne se mesure pas au nombre de réponses. Comme nodgim et probablement beaucoup d'autres, j'ai séché ici et donc rien posté. Merci à scarta pour ce petit "casse-tête".

Ebichu · #12

Ben c'est exactement ce que je voulais dire : je suis surpris que tant de personnes aient séché, car je trouvais ce problème bien plus facile que d'autres qui ont pléthore de réponses. Mais il est toujours compliqué d'anticiper ces choses-là.

scarta · #13

Si j'avais voulu faire inutilement compliqué, j'aurais pris l'Europe et pas la France

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 06-11-2017 14:35:41

Les coueurs de la France

Code:

#0 Pub

#2 - 06-11-2017 18:02:17

Les cuoleurs de la France

#3 - 06-11-2017 18:52:07

Les couleurs de la rFance

#4 - 06-11-2017 19:00:58

Les oculeurs de la France

#5 - 06-11-2017 20:44:35

Les couleurs de la Frane

#6 - 06-11-2017 21:07:17

Les coulers de la France

#7 - 13-11-2017 09:15:42

les cpuleurs de la france

#8 - 13-11-2017 16:20:55

les couleurs se la france

#9 - 13-11-2017 16:57:56

Les coulerus de la France

#10 - 13-11-2017 18:28:33

Les couleurs de laa France

#11 - 13-11-2017 21:51:20

Les coueurs de la France

#12 - 13-11-2017 23:44:20

Les couleurs de la Franec

#13 - 14-11-2017 09:57:58

Les couleusr de la France

Réponse rapide

Sujets similaires

Pied de page des forums