Un défi par semaine

Juillet 2016, 2e défi

El 8 julio 2016  - Escrito por  Ana Rechtman Ver los comentarios (7)
Leer el artículo en  

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.

Comparte este artículo

Para citar este artículo:

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

Comentario sobre el artículo

  • Juillet 2016, 2e défi

    le 8 de julio de 2016 à 10:47, par mesmaker

    Serait-ce 6! ?

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

      le 8 de julio de 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 de julio de 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 de julio de 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 de julio de 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 de julio de 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 de julio de 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

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexióninscribirse¿contraseña olvidada?

La traducción del sitio del francés al castellano se realiza gracias al apoyo de diversas instituciones de matemáticas de América Latina.