Mais c'est encore pire si on essaie avec 6 éléments (donc 720 combinaisons) : cette fois, on n'en obtient qu'un douzième.
  1-BCDEFA    2-CEADBF    3-DAECFB    4-ECBDAF    5-FEACDB    6-ABDCFE    7-BDACEF    8-CFEBAD    9-DBCAEF   10-EDABFC
 11-FADBCE   12-ACBFED   13-BEFACD   14-CADFEB   15-DCAFBE   16-EFDACB   17-FBCEAD   18-ADFECB   19-BFDEAC   20-CBAEDF
 21-DEFCAB   22-EACDBF   23-FCADEB   24-AEDCBF   25-BACDEF   26-CDFBAE   27-DFCBEA   28-EBACFD   29-FDEBCA   30-AFCBED
 31-BCFADE   32-CEDAFB   33-DABFCE   34-ECFADB   35-FECABD   36-ABFEDC   37-BDEFAC   38-CFBEDA   39-DBFEAC   40-EDCFBA
 41-FABDEC   42-ACEDBF   43-BECDFA   44-CAFDBE   45-DCEBFA   46-EFBCAD   47-FBECDA   48-ADCBFE   49-BFACDE   50-CBEAFD
 51-DEBACF   52-EAFBDC   53-FCDABE   54-AEBFDC   55-BAEFCD   56-CDBFEA   57-DFAEBC   58-EBDFCA   59-FDBEAC   60-AFEDCB
 61-BCDEFA   62-CEADBF   63-DAECFB   64-ECBDAF   65-FEACDB   66-ABDCFE   67-BDACEF   68-CFEBAD   69-DBCAEF   70-EDABFC
 71-FADBCE   72-ACBFED   73-BEFACD   74-CADFEB   75-DCAFBE   76-EFDACB   77-FBCEAD   78-ADFECB   79-BFDEAC   80-CBAEDF
 81-DEFCAB   82-EACDBF   83-FCADEB   84-AEDCBF   85-BACDEF   86-CDFBAE   87-DFCBEA   88-EBACFD   89-FDEBCA   90-AFCBED
 91-BCFADE   92-CEDAFB   93-DABFCE   94-ECFADB   95-FECABD   96-ABFEDC   97-BDEFAC   98-CFBEDA   99-DBFEAC  100-EDCFBA
101-FABDEC  102-ACEDBF  103-BECDFA  104-CAFDBE  105-DCEBFA  106-EFBCAD  107-FBECDA  108-ADCBFE  109-BFACDE  110-CBEAFD
111-DEBACF  112-EAFBDC  113-FCDABE  114-AEBFDC  115-BAEFCD  116-CDBFEA  117-DFAEBC  118-EBDFCA  119-FDBEAC  120-AFEDCB
121-BCDEFA  122-CEADBF  123-DAECFB  124-ECBDAF  125-FEACDB  126-ABDCFE  127-BDACEF  128-CFEBAD  129-DBCAEF  130-EDABFC
131-FADBCE  132-ACBFED  133-BEFACD  134-CADFEB  135-DCAFBE  136-EFDACB  137-FBCEAD  138-ADFECB  139-BFDEAC  140-CBAEDF
141-DEFCAB  142-EACDBF  143-FCADEB  144-AEDCBF ...
Essayons de comprendre cette périodicité. Nous utilisons une comptine de n syllabes avec p enfants en cercle. Un enfant sera désigné en premier et on dira qu'il se trouve à une distance a < p de celui sur lequel on commence à compter. Mais si notre comptine faisait n + p syllabes, on tomberait sur le même enfant qui est toujours à une distance a. Et ce serait évidemment la même chose pour n + 2*p, n + 3*p, ...
Si on prend 6 enfants, on pourra écrire ceci :
Les lettres majuscules de A à E représentent des nombres entiers (pouvant même être nuls). Le nombre qui les multiplie diminue à chaque ligne puisqu'il représente le nombre d'enfants encore dans le cercle.
Si les valeurs des nombres A, B, ..., E varient cela ne change rien à la permutation finale (le mélange). On aura juste fait des tours dans le vide. Ce que l'on doit trouver, c'est un nombre à ajouter à n sans que cela modifie les valeurs a, b, ..., e.
Si on ajoute 6, par exemple, on obtient ceci : n + 6 = 6*A + a + 6.
C'est-à-dire : n + 6 = 6*(A + 1) + a.
Ca ne change donc rien au premier enfant sélectionné, mais pour le deuxième ce n'est pas pareil :
n + 6 = 5*B + b + 6 = 5*B + 5 + b + 1 = 5*(B + 1) + b + 1.
Une idée serait d'ajouter 6*5 = 30 :
Ça ne fonctionne pas pour le troisième, mais ça nous donne un idée : on pourrait utiliser un nombre qui se divise par 6, 5, 4, 3 et 2. Le plus petit est 60 :
Cela signifie que si n donne une certaine permutation, n + 60 donne exactement la même. Au passage, 60 est le PPCM de l'ensemble (6, 5, 4, 3, 2). Et il se trouve que c'est aussi le PPCM de (5, 4, 3, 2) ce qui explique que la périodicité qu'on a constatée pour 5 enfants dans le cercle soit également de 60.
Pages : 1 2 3 4 5 6
Compresser une permutation
15 mai 2013
Sommaire général