Un défi par semaine

Juillet 2016, 2e défi

8 juillet 2016  - Ecrit par  Ana Rechtman Voir les commentaires (7)

Nous vous proposons un défi du calendrier mathématique 2016 chaque vendredi et sa solution la semaine suivante.

Semaine 28 :

Chaque sommet d’un pentagone doit être mis en couleur. Nous disposons de $6$ couleurs différentes. Chaque diagonale doit avoir deux couleurs différentes à ses extrémités. Si nous ne prenons pas en compte les coloriages qui s’obtiennent l’un de l’autre par rotation, de combien de manières différentes peut-on colorier les sommets du pentagone ?

Solution du 1er défi de Juillet :

Enoncé

La réponse est $\frac{18}{7}$.

L’égalité

$6=\frac{a+b}{a-b}+\frac{a-b}{a+b}=\frac{(a+b)^2+(a-b)^2}{(a-b)(a+b)}=\frac{2a^2+2b^2}{a^2-b^2}$

implique que $6a^2-6b^2=2a^2+2b^2$ ou $a^2=2b^2$. Nous avons donc $(a^2)^3=a^6=8b^6$, ainsi

$\frac{a^3+b^3}{a^3-b^3}+\frac{a^3-b^3}{a^3+b^3} = \frac{2a^6+2b^6}{a^6-b^6}$

$= \frac{18b^6}{7b^6}$

$ = \frac{18}{7}.$

Post-scriptum :

Calendrier mathématique 2016 - Sous la direction d’Ana Rechtman, Maxime Bourrigan - Textes : Aubin Arroyo, Fabiola Manjarrez et Ana Rechtman.
2015, Presses universitaires de Strasbourg. Tous droits réservés.

Partager cet article

Pour citer cet article :

Ana Rechtman — «Juillet 2016, 2e défi» — Images des Mathématiques, CNRS, 2016

Commentaire sur l'article

  • Juillet 2016, 2e défi

    le 8 juillet à 10:47, par mesmaker

    Serait-ce 6 ! ?

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

      le 8 juillet à 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 à 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 à 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 à 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 à 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 à 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

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM