Un défi par semaine

Avril 2015, 3e défi

El 17 abril 2015  - Escrito por  Ana Rechtman Ver los comentarios (22)
Leer el artículo en  

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

Semaine 16 :

Jean souhaite faire des briques en forme de parallélépipèdes, toutes différentes et telles que les mesures de leurs arêtes soient des nombres entiers inférieurs ou égaux à $7$. Combien de briques pourra faire Jean?

Solution du 2ème défi d’Avril :

Enoncé

La réponse est $p=29$.

Comme $p^3+7p^2=p^2(p+7)$, il suffit de déterminer le plus petit nombre premier $p>2$ tel que $p+7$ soit un carré. C’est-à-dire, tel que $p+7=n^2$ pour un entier positif $n$. Puisque $n^2-7$ doit être un nombre premier supérieur à $2$, $n$ doit être supérieur à $3$. Si $n=4$, on obtient $4^2-7=9$ et $9$ n’est pas premier. Si $n=5$, on obtient $5^2-7=18$ et $18$ n’est pas premier. Si $n=6$, on obtient $6^2-7=29$ et $29$ est un nombre premier. Ainsi, le nombre premier recherché est $p=29$.

Post-scriptum :

Calendrier mathématique 2015 - Sous la direction d’Ana Rechtman Bulajich, Anne Alberro Semerena, Radmilla Bulajich Manfrino - Textes : Ian Stewart.
2014, Presses universitaires de Strasbourg. Tous droits réservés.

Article édité par Ana Rechtman

Comparte este artículo

Para citar este artículo:

Ana Rechtman — «Avril 2015, 3e défi» — Images des Mathématiques, CNRS, 2015

Créditos de las imágenes:

Imagen de portada - Daniela Kunze / Flora Press / BIOSPHOTO

Comentario sobre el artículo

Voir tous les messages - Retourner à l'article

  • Avril 2015, 3ème défi

    le 18 de abril de 2015 à 22:45, par Idéophage

    Pour les formules mathématiques, le site utilise MathJax, donc on peut en profiter en mettant du code latex entre des symboles ’dollar’ (que je n’arrive pas à échapper). Vous pouvez voir le code des autres formules pour vous inspirer en faisant sur une formule «clic droit» → «show maths as» → «TeX command».

    Je trouve moi aussi 210. Par contre, je ne comprends pas votre formule. Je n’ai pas la même et elle ne me donne pas les résultats que vous dites. Est-ce bien \[\sum_{k=0}^n \left[ \binom{n}{k} \binom{p}{k} \right] \text{ ?}\]

    Pour généraliser (automatiser) la méthode en passant par le lemme de Burnside, il faut compter le nombre de permutations à 1, …, n cycles disjoints. Les permutations « directes » (qui ne changent pas le sens du repère) sont celles qui comportent un nombre pair de cycles de longueur paire, soit celles dont le nombre de cycles est congru à $n$ modulo $2$. Notons $P_n(p)$ le polynôme donnant le nombre de boites différentes avec $p$ tailles et $n$ dimensions. Lorsqu’on l’écrit en base canonique, les coefficients sont donnés par le nombre de permutations à 1, …, n cycles. Par exemple, on a \[P_4(p) = \frac{p^4 + 6p^3 + 11p^2 + 6p}{24} \text{ .}\]

    Cela veut dire qu’il y a :

    * $1$ permutation (directe) comportant $4$ cycles,

    * $6$ permutations (indirectes) comportant $3$ cycles,

    * $11$ permutations (directes) comportant $2$ cycles et

    * $6$ permutations (indirectes) comportant $1$ cycle.

    Je ne vois pas comment trouver ces coefficients de manière simple (sans tout passer en revue). Par contre, il est plus simple de trouver de manière automatique les coefficients de la méthode de Daniate. Du coup, on peut trouver ces coefficients en effectuant un changement de base.

    De plus, on voit que si l’on ne considère que les permutations directes, cela revient à enlever dans notre groupe toutes les permutations indirectes (et donc aussi à diviser sa taille par $2$). On enlève donc dans $P_n(p)$ tous les coefficients qui n’ont pas la même parité que $n$, puis on multiplie par $2$ (cela correspond à diviser la taille du groupe par $2$ dans la formule de Burnside). Par exemple, pour $n=4$, on se retrouve avec $\frac{p^4 + 11p^2}{12}$.

    Dans la formule en « base binomiale » (celle de Daniate), il faut pour avoir les coefficients compter, pour chaque nombre de tailles différentes utilisées, le nombre de manières qu’il y a de les répartir sur les axes (modulo une permutation de ces axes). Chaque taille doit être affectée au moins une fois. Si on utilise $k$ tailles différentes, c’est comme si on avait $n$ billes alignées et que l’on devait en colorier un certain nombre non nul d’une première couleur, puis un certain nombre d’une deuxième couleur, etc. jusqu’à une $k$ème couleur. On peut identifier cela au choix de $k-1$ billes parmi $n-1$ : il s’agit de sélectionner les billes après lesquelles on change de couleur (la dernière n’est pas sélectionnable, donc $n-1$).

    Ça, c’est pour quand on n’oriente pas les axes (permutations quelconques). Regardons ce qui se passe si l’on oriente les axes. Prenons $n=3$, le nombre de dimensions. Tant que l’on a deux axes de même taille (ou couleur), cela revient au même d’avoir le groupe symétrique ou sa moitié directe puisque l’échange de deux axes qui ont même couleur se confond avec l’identité. Ainsi, c’est seulement lorsque $k=n$ que quelque chose va changer. Lorsque $k=n$, le nombre de manières différentes d’affecter les couleurs modulo une permutation quelconque est $1$. Si on ne considère que la moitié directe de ces permutations, ce nombre passe à $2$. Dans notre polynôme $P_n(p)$, il s’agit du coefficient de $\binom{p}{n}$ qui passe de $1$ à $2$.

    On a \[P_n(p) = \sum_{k = 1}^n \left[ \binom{n-1}{k-1} \binom{p}{k} \right] \text{ .}\]

    Ainsi, on a une deuxième manière d’obtenir le polynôme pour les permutations directes : il s’agit de $P_n(p) + \binom{p}{n}$. On retrouve bien pour $n=4$ ce que l’on avait avant : $\frac{p^4 + 11p^2}{12}$. Du coup, notons $\alpha_1, \dots, \alpha_n$ les coefficients de $P_n(p)$ au-dessus de la barre de fraction (il y a $n!$ en-dessous). Nous avons \[\frac{\alpha_np^n + \cdots + \alpha_1p^1}{n!} + \binom{p}{n} = \frac{\alpha_np^n + \alpha_{n-2}p^{n-2} + \cdots}{n!/2} \text{ .}\]

    Nous en déduisons que \[\frac{\alpha_np^n - \alpha_{n-1}p^{n-1} + \alpha_{n-2}p^{n-2} - \cdots \pm \alpha_1p^1}{n!} = \binom{p}{n} \text{ .}\]

    Je ne comprends plus rien à ce qui se passe, mais il est probable que le résultat qui en découle s’interprête et donnera une solution beaucoup plus simple que ce que nous avions. On a ainsi $P_n(p) = \frac{p(p+1)\cdots(p-1+n)}{n!} = \binom{p-1+n}{n} = C(p-1,n)$. Il s’agit du nombre de manières de répartir $n$ billes noires et $p-1$ billes blanches sur une ligne. Enfin bon, tout ceci ressemble à un tour de magie pour moi… Par exemple, nous avons du coup $84 = \frac{7 \times 8 \times 9}{3!}$ et $210 = \frac{7 \times 8 \times 9 \times 10}{4!}$.

    Bon… Après coup, il est vrai que ce que nous avons fait n’était pas le plus direct. Je me demande comment on a fait pour passer à côté de ça : on veut simplement répartir des couleurs sur des axes, modulo une permutation des axes. Cela revient donc à prendre $n$ billes, à en colorier un certain nombre (possiblement nul) d’une première couleur, puis un certain nombre d’une deuxième, etc. jusqu’à une $p$ème couleur. Ainsi, on peut à la place considérer $n$ billes blanches, $p-1$ billes noires, et compter le nombre de manières de les placer en ligne. Chaque placement correspondra à colorier les premières billes blanches de la première couleur jusqu’à tomber sur une bille noire, puis passer à la deuxième couleur, etc. Nous avons donc $C(n,p-1)$ possibilités. Ce que nous avions fait est de séparer les cas selon le nombre de couleurs utilisées…

    Du coup, cela interprète la formule de combinatoire \[\sum_{k = 1}^n \left[ \binom{n-1}{k-1} \binom{p}{k} \right] = C(p-1,n) \text{ .}\]

    On peut aussi utiliser le lemme de Burnside différemment. À la place de compter pour chaque élément du groupe combien il y a de points fixes, on peut compter pour chaque point combien d’éléments du groupe le fixe. Je ne sais pas à quoi ça mène.

    Pour le lemme de Burnside, pour avoir les coefficients, on peut également séparer les permutations en classes isomorphes (c’est plus pratique pour compter à la main). Deux permutations sont isomorphes si elles sont les mêmes modulo un renommage des éléments. Par exemple, pour $n=4$, pour les permutations à deux cycles, il y a la classe dont les permutations ont deux cycles de longueur $2$ et il y a la classe dont les permutations ont un cycle de longueur $1$ et un cycle de longueur $3$. Cela a un lien avec le nombre de manières de partitionner l’entier $4$ en somme d’entiers naturels non-nuls. Par exemple, $4 = 2 + 2 = 1 + 3$. Ensuite, on peut compter automatiquement le nombre de permutations dans chaque classe.

    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.