Un défi par semaine

Juillet 2016, 2e défi

Le 8 juillet 2016  - Ecrit par  Ana Rechtman Voir les commentaires (7)
Lire l'article 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.

Partager cet article

Pour citer cet article :

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

Commentaire sur l'article

Voir tous les messages - Retourner à l'article

  • 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

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é ?