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 : 1533

les couleues de 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


Annonces sponsorisées :

 
Réponse :
  • |
  • Répondre

#0 Pub

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

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

Les couleurs dde la France

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

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

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 494

Les coulerus 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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 494

les couleirs 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 : 1533

Les coulurs 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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 494

Les couleurs dde 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 : 1533

Les couleurs dee 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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 494

les couleurd 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 : 3228

Les coueurs 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 : 1533

Les couleuurs de la France

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 : 2844
Lieu: Luxembourg

Le scouleurs de la 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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 494

Les couleurss 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 : 1533

Les colueurs de la France

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 : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
P2T
Tour de France par Vasimolo
04-07-2016 Enigmes Mathématiques
P2T
L'organisation du mariage par rhaarezadejapris
15-06-2008 Enigmes Mathématiques
29-09-2011 Enigmes Mathématiques
P2T
04-09-2008 Enigmes Mathématiques
P2T
Fog N°1 par Vasimolo
18-12-2009 Enigmes Mathématiques
P2T
Gâteau 97 par Vasimolo
01-05-2015 Enigmes Mathématiques
20-11-2015 Enigmes Mathématiques
P2T
Enigme mathematique par nana973
29-01-2014 Enigmes Mathématiques
P2T
05-01-2012 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