Commentaire sur l'article

• Avril 2015, 3ème défi

  le 17 avril 2015 à 11:44, par Bernard Hanquez

  Jean peut faire (7 !/(7-3) !)/3 ! = 35 briques distinctes.

  Répondre à ce message

• Avril 2015, 3ème défi

  le 17 avril 2015 à 17:47, par Daniate

  J’en compte 84 : 7 cubes, 42 parallélépipèdes à section carrées (non cubes) et 3 combinaisons parmi 7 soit 35 à dimensions différentes.

  Répondre à ce message

• Avril 2015, 3ème défi

  le 17 avril 2015 à 23:28, par Idéophage

  Bonjour,

  J’ai encore une réponse différente qui est 119.

  On peut encore utiliser le lemme de Burnside comme pour le 2ème défi de Mars (encore avec Jean) : $\frac{7^3 + 7 + 7}{3} = 119$. On peut aussi faire comme Daniate mais par contre il faut compter en double quand les trois côtés ont trois tailles différentes car on peut tourner dans deux sens différents lors de l’affectation des tailles. Cela donne $\binom{7}{1} + 2 \times \binom{7}{2} + 2 \times \binom{7}{3} = 119$.

  On peut généraliser les deux méthodes à plus de dimensions, mais je ne sais pas si ça intéresse quelqu’un.

  On peut retrouver les coefficients de la méthode de Daniate avec la méthode avec le lemme de Burnside (et inversement, il s’agit d’écrire un polynôme dans deux bases différentes), peut-être que ça s’interprète ou mène à quelque chose…

  Répondre à ce message
• Avril 2015, 3ème défi

  le 18 avril 2015 à 07:19, par Daniate

  Bonjour,

  Je crains de ne pas m’être trompé, il n’y a que 35 briques dont les tailles des côtés sont différentes. Il me semble que pour utiliser le lemme de Burnside il faut un groupe agissant sur un ensemble. Pourriez vous préciser l’un et l’autre ?

  Répondre à ce message
• Avril 2015, 3ème défi

  le 18 avril 2015 à 14:46, par Idéophage

  Je crois que l’on n’a pas compris l’énoncé de la même manière…

  On veut des briques « toutes différentes ». Ce n’est pas précis, mais j’imagine que ça veut dire que l’on considère que deux briques sont identiques si on peut passer de l’une à l’autre avec une rotation.

  On a trois axes auxquels il faut affecter des tailles : x, y et z. Prenons 3 tailles différentes à la place de 7. Si toutes les tailles affectées sont différentes, on peut faire (x,y,z) ← (1,2,3) ou (1,3,2) ou (2,1,3) ou (2,3,1) ou (3,1,2) ou (3,2,1). Mais on peut tourner les briques et transformer la brique (a,b,c) en (c,a,b) ou (b,c,a) avec une rotation autour de l’axe passant par l’origine et (1,1,1). On se retrouve alors avec deux formes différentes, (1,2,3) et (1,3,2) et non une seule (cela correspond à tourner dans un sens direct ou un sens indirect). Chaque sélection de trois tailles différentes va produire deux briques possibles.

  On se restreint aux briques orientées selon les axes, donc on restreint nos transformations permises à celles qui envoient chaque axe sur un autre axe et dans le même sens. Il y a trois transformations qui conviennent : soit on ne fait rien, soit on fait un tiers de tour dans un sens autour de l’axe passant par l’origine et (1,1,1), soit on fait un tiers de tour dans l’autre sens.

  Répondre à ce message

• Avril 2015, 3ème défi

  le 18 avril 2015 à 07:36, par Daniate

  Je viens d’utiliser le groupe des substitutions dans l’ensemble des triplets à valeurs de 1 à 7.

  on a : l’identité avec 343 triplets fixes

  3 permutations 2 à 2 avec chacune 49 triplets fixes

  2 cycles avec 7 triplets fixes

  (343+3*49+2*7)/6 = 84

  Répondre à ce message
• Avril 2015, 3ème défi

  le 18 avril 2015 à 14:50, par Idéophage

  Ah, mais alors vous considérez qu’une brique est identique à elle-même vue dans un miroir ?

  Répondre à ce message
• Avril 2015, 3ème défi

  le 18 avril 2015 à 16:05, par Daniate

  Oui, considérez les 3 rotations de PI autour des axes passant par les centres des faces opposées. Vous verrez que chacun des 3 cotés peut coïncider avec n’importe quel axe que vous avez défini.

  Vous pouvez aussi remarquer que si un sommet est l’origine de 3 axes avec a,b et c sur chacun alors le sommet contigu aura b,a et c sur ses axes ... (ou a,c,b ou c,b,a).

  A moins que vous aimiez dessiner sur une brique pour lui faire perdre sa symétrie.

  Répondre à ce message
• Avril 2015, 3ème défi

  le 18 avril 2015 à 17:12, par Idéophage

  Ah oui, vous avez raison, je me suis trompé. Je n’avais pas vu que l’on pouvait translater la brique si un axe se retrouvait du mauvais côté.

  Répondre à ce message
• Avril 2015, 3ème défi

  le 18 avril 2015 à 17:16, par Idéophage

  Du coup, il s’agit du groupe symétrique et non plus de sa moitié « directe », comme vous avez dit.

  Répondre à ce message
• Avril 2015, 3ème défi

  le 18 avril 2015 à 17:56, par Daniate

  Désolé pour l’imprécision de mon langage, l’enseignement des groupes a disparu depuis fort longtemps au lycée, niveau où j’enseignait. Il y a donc plus de trente ans que je ne manipule pas les groupes.

  Répondre à ce message
• Avril 2015, 3ème défi

  le 18 avril 2015 à 23:00, par Idéophage

  C’était clair, je voulais dire dans mon message précédent que j’avais considéré le mauvais groupe.

  Répondre à ce message

• Avril 2015, 3ème défi

  le 18 avril 2015 à 19:31, par Daniate

  La même méthode appliquée aux quadruplets donne 210 quadruplets différents en considérant qu’ils sont équivalents s’ils sont formés des mêmes nombres mais à des places différentes. Ce pourrait être la solution du problème à 4 dimensions. Mais je ne suis pas certain que 2 quadruplets équivalents donne forcément la même brique à 4 dimensions. Malgré tout il apparaît une ébauche de formule pour calculer le nombres de n-uplets à valeurs entre 1 et p (elle m’est soufflée par Idéophage ) :

  sigma de k=0 à n de (n n-k)*(p k)

  elle est valable pour n=1,2,3 et 4.

  Faute de maîtriser l’écriture scientifique que je vois dans certains message, je précise (n n-k) est le nombre de combinaisons a n-k éléments choisis parmi p

  Répondre à ce message
• Avril 2015, 3ème défi

  le 18 avril 2015 à 19:34, par Daniate

  Errata : .... à n-k éléments choisis parmi n

  Répondre à ce message
• Avril 2015, 3ème défi

  le 18 avril 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

• Avril 2015, 3ème défi

  le 18 avril 2015 à 22:55, par Idéophage

  Oui, vous avez raison, deux quadruplets différents donnent bien la même « brique » en 4d. On peut se dire que si l’on considère un sous-espace, on peut effectuer des rotations quelconques dedans en laissant invariant le sous-espace qui lui est orthogonal.

  Répondre à ce message
• Avril 2015, 3ème défi

  le 18 avril 2015 à 22:56, par Idéophage

  Je voulais dire « deux quadruplets équivalents ».

  Répondre à ce message

• Avril 2015, 3ème défi

  le 18 avril 2015 à 11:03, par Creux

  Il me semble que l’énoncé comporte une faille : on y parle de briques en forme de parallélépipèdes, mais on ne précise pas que ces parallélépipèdes doivent être rectangles.

  Sans cette précision, on peut en concevoir avec toutes sortes d’angles et il y a donc une infinité de briques différentes.

  Répondre à ce message
• Avril 2015, 3ème défi

  le 18 avril 2015 à 17:49, par ROUX

  En fait, il ne fallait pas préciser « en forme de parallélépipèdes » car une brique est par définition un parallélépipède rectangle ;-).

  Répondre à ce message
• Avril 2015, 3ème défi

  le 18 avril 2015 à 18:02, par Daniate

  Un peu d’imagination, collègue ! Pourquoi ne pas construire un mur avec des briques en forme de losange non carré ? Nos chers architectes sont bien capables d’innover.

  Répondre à ce message

• Avril 2015, 3ème défi

  le 20 avril 2015 à 20:05, par arnaudpi2

  Après avoir résolu le problème comme Daniate, je l’ai posé à mon fils Matthieu, ex disciple d’Animath, qui m’a très vite répondu que le résultat est le nombre de combinaisons de 3 éléments parmi 7 - 1 + 3...

  C’est le même problème que celui du nombre de glaces à 3 boules parmi 7 parfums.

  On écrit les (7 - 1) dimensions 1 2 3 4 5 6, on insère 3 séparateurs dans la liste, et on choisit pour valeurs des cotés du parallélépipède le nombre immédiatement à droite de chaque séparateur.

  Par exemple : 1 2 || 3 4 5 6 | (7) génère le parallélépipède 3 x 3 x 7

  D’où la solution : nombre de combinaisons de 3 éléments parmi (7 - 1) + 3.

  Répondre à ce message

• Avril 2015, 3ème défi

  le 21 avril 2015 à 01:03, par Idéophage

  Voici un lien concernant cette idée : <http://www.artofproblemsolving.com/...> .

  Répondre à ce message