Commentaire sur l'article

• Juillet 2016, 2e défi

  le 8 juillet 2016 à 10:47, par mesmaker

  Serait-ce 6 ! ?

  Répondre à ce message
• Juillet 2016, 2e défi

  le 8 juillet 2016 à 15:24, par Daniate

  J’en ai compté 624 avec une méthode douloureuse et sans vérification, Burnside peut-il venir à notre aide ?

  Répondre à ce message
• Juillet 2016, 2e défi

  le 9 juillet 2016 à 00:44, par skilveg

  Je trouve le même résultat de la façon suivante : l’ensemble des sommets est partitionné par les couleurs, ce qui fournit une partition de l’entier 5. On peut commencer par filtrer selon le type de cette partition :
  * type (1,1,1,1,1) : tous les sommets sont de couleurs différentes, et le nombre de possibilités est $A_5^6$ (choix des couleurs) / $5$ (quotient par les rotations) ;
  * type (2,1,1,1) : tous les sommets sont de couleurs distinctes sauf 2, qui sont sur une même arête du pentagone. Cette arête fixe la position du pentagone. Il y a $A_4^6$ possibilités, puisque quatre groupes de couleurs différentes ;
  * type (2,2,1) : deux arêtes dont les sommets sont de la même couleur, et un cinquième sommet d’une couleur différente. La position est fixe, il y a trois groupes de couleurs différentes, d’où $A_3^6$ possibilités.
  * types (3,...) : impossible car parmi trois sommets, deux au moins sont sur une même diagonale.

  Au final cela donne $6\cdot 4\cdot 3\cdot 2 + 6\cdot 5\cdot 4\cdot 3 + 6\cdot 5\cdot 4 = 624$ configurations.

  Répondre à ce message

• Juillet 2016, 2e défi

  le 8 juillet 2016 à 19:07, par mesmaker

  Voilà la raison de ma réponse 6 ! qui est fausse mais qui aide à chercher la solution.

  J’ai cru que l’on ne pouvait utiliser que 5 couleurs alors que l’on peut colorier les sommets avec seulement trois ou quatre couleurs.

  Cependant, si je me limite à 5 couleurs, alors je dois les choisir parmi les six ce qui me donne 6 choix possibles. Un fois les cinq couleurs choisies, j’ai 5 ! façons de les placer sur les 5 sommets. Sauf qu’il faut diviser cela par cinq car pour chaque cas il y a cinq permutations possibles. Ce qui donne en fait 6*4 ! = 144 (et non 6 !).

  Il faut maintenant calculer quand il y a moins de 5 couleurs. Une couleur est évidemment impossible (trivial), deux de même car le sommet de couleur différente serait relié par deux diagonales à deux sommets ayant la même couleur.

  Trois couleurs est possible avec le cas B, B, R, R, V (B=bleu, R=rouge, V=vert) ou B, V, V, R, B. Il y en a d’autres combinaisons et bien sûr on peut choisir trois autres couleurs parmi les 6 possibles. Il faut aussi traiter les cas avec 4 couleurs.

  Bref beaucoup de cas et sous-cas. Par fainéantise, j’aurai tendance à faire confiance à Daniate pour sa réponse de 624.

  Répondre à ce message
• Juillet 2016, 2e défi

  le 8 juillet 2016 à 20:25, par Daniate

  Bonsoir, je ne reviens pas sur 5 couleurs, mais on peut raccourcir pour 3 et 4. On remarque qu’une couleur ne peut se répéter qu’une fois et sur un sommet adjacent. Avec 3 couleurs on a 2 sommets de couleur 1, 2 sommets couleur 2 et un sommet couleur 3 , ce sommet nous sert de balise empêchant les rotations. Il y a donc 6*5*4=120 possibilités. Pour 4 couleurs on aura 2 sommets adjacents de couleur 1 qui servent de balises et les autres de couleurs 2,3 et 4 soit 6*5*4*3=360 possibilités avec en tout 144+120+360=624 et bonnes vacances aux paresseux et aux autres.

  Répondre à ce message
• Juillet 2016, 2e défi

  le 9 juillet 2016 à 00:26, par Idéophage

  @Daniate : En effet, Burnside est ce qui permet de dire que l’on doit diviser par 5 le nombre de coloriages sans compter les rotations comme l’identité.

  Si on considère le graphe formé par les sommets du pentagone et ses diagonales, ça fait encore un pentagone.

  Notons $P_n(k)$ le nombre de manières qu’il y a de colorier un $k$-gone avec $n$ couleurs sans qu’il y ait deux sommets adjacents de la même couleur. Pour faire un coloriage d’un $k+2$-gone, on commence par colorier $k+1$ sommets. Deux possibilités se présentent pour le sommet restant : soit les deux sommets qui lui sont adjacents sont de la même couleur, auquel cas $n-1$ possibilités, soit non, auquel cas $n-2$ possibilités. On a $P_n(k)$ coloriages en faisant en sorte que les deux sommets soient de la même couleur (on les « fusionne ») et $P_n(k+1)$ coloriages en faisant en sorte qu’ils soient de couleurs différentes (on les joint par une arête).

  On obtient alors la récurrence $P_n(k+2) = (n-2)P_n(k+1) + (n-1)P_n(k)$, avec $P_n(2) = k(k-1)$ et $P_n(3) = k(k-1)(k-2)$. Ici, ça nous donne $P_6(5) = 3120$.

  C’est intéressant, ce problème de trouver le nombre de coloriages d’un graphe, avec n couleurs, sans deux sommets adjacents de la même couleur. Pour un graphe complet, on trouve les coefficients binomiaux. Pour les arbres, ça ne dépend que du nombre de nœuds. On peut regarder avec le principe d’inclusion-exclusion dans le cas général…

  Répondre à ce message
• Juillet 2016, 2e défi

  le 9 juillet 2016 à 00:29, par Idéophage

  Oups, j’ai mis $k$ au lieu de $n$ dans les premières valeurs de la récurrence…

  Répondre à ce message