Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

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

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

Les couleurs d la France

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

 
Réponse :
  • |
  • Répondre

#0 Pub

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

zobizob
Amateur de Prise2Tete
Enigmes résolues : 1
Messages : 8

les coyleurs de la france

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

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

leq couleurs de la france

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.

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

les couleyrs de la france

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.

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

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

Les couuleurs de la France

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 smile
Vu la réputation que j'ai eu ici par le passé...

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

led couleurs de la france

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.

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

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

Les couleusr de la France

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)

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Les couleur de la France

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.

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

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

les coulrurs de la france

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.

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

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

les couleurs de la frznce

As-tu au moins compris pourquoi 20736 marche ? big_smile

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é

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

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3220
Lieu: Luxembourg

Les couleurs de lla France

@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".

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

led couleurs de la france

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à.

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

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

les couleurs de la feance

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

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
P2T
Tour de France par Vasimolo
04-07-2016 Enigmes Mathématiques
07-03-2015 Enigmes Mathématiques
P2T
Cadeaux par minifat
29-08-2007 Enigmes Mathématiques
P2T
Ca eut payé par Vasimolo
30-10-2009 Enigmes Mathématiques
P2T
11-07-2011 Enigmes Mathématiques
26-02-2014 Enigmes Mathématiques
07-10-2010 Enigmes Mathématiques
P2T
Suite logique par lerusse67
14-09-2013 Enigmes Mathématiques
P2T
12-10-2007 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete