La solution est à chercher du côté de nos jeux d'enfants et notamment des petites comptines qui nous servaient à désigner le loup. Pour cela, les enfants qui voulaient jouer formaient une ronde et on entonnait une comptine en désignant à chaque syllabe l'enfant suivant.
Prenons un exemple.
enfants (que nous appellerons très poétiquement A, B, C, D, E, F, G et H) utilisent la comptine de 5 syllabes suivante : "Tu n'es pas le loup.". Si on commence la comptine sur A, elle s'arrête sur E qui est bien content de ne pas être le loup. Ensuite, ce sera au tour de B d'être exempté, puis ce sera H, etc. Finalement, les enfants auront été désignés dans cet ordre-ci : E B H G A D F C.
On se rend alors compte que le nombre 5 permet de décrire un et un seul mélange possible de 8 éléments. On se pose alors tout se suite la questions suivante : peut-on décrire tous les mélanges possibles avec ce système. Pour 8 éléments, on sait qu'on a 8! = 40320 mélanges possibles. Il serait intéressant de tester les nombres de 1 à 40320 pour voir s'ils donnent tous des mélanges différents. Mais on va commencer par restreindre le nombre d'éléments à 5 pour n'avoir que 120 combinaisons à examiner.
  1-BCDEA    2-CEBAD    3-DBACE    4-EDACB    5-ABDEC    6-BDCAE    7-CABDE    8-DCAEB    9-EADBC   10-ACDBE
 11-BECDA   12-CBAED   13-DEABC   14-EBDCA   15-ADCEB   16-BACED   17-CDABE   18-DAECB   19-ECDAB   20-AECBD
 21-BCADE   22-CEADB   23-DBEAC   24-EDCBA   25-ABCDE   26-BDAEC   27-CAEBD   28-DCEBA   29-EACDB   30-ACBED
 31-BEACD   32-CBEDA   33-DECAB   34-EBCAD   35-ADBCE   36-BAEDC   37-CDEAB   38-DACBE   39-ECBDA   40-AEBDC
 41-BCEAD   42-CEDBA   43-DBCEA   44-EDBAC   45-ABECD   46-BDECA   47-CADEB   48-DCBAE   49-EABCD   50-ACEDB
 51-BEDAC   52-CBDAE   53-DEBCA   54-EBADC   55-ADEBC   56-BADCE   57-CDBEA   58-DABEC   59-ECABD   60-AEDCB
 61-BCDEA   62-CEBAD   63-DBACE   64-EDACB   65-ABDEC   66-BDCAE   67-CABDE   68-DCAEB   69-EADBC   70-ACDBE
 71-BECDA   72-CBAED   73-DEABC   74-EBDCA   75-ADCEB   76-BACED   77-CDABE   78-DAECB   79-ECDAB   80-AECBD
 81-BCADE   82-CEADB   83-DBEAC   84-EDCBA   85-ABCDE   86-BDAEC   87-CAEBD   88-DCEBA   89-EACDB   90-ACBED
 91-BEACD   92-CBEDA   93-DECAB   94-EBCAD   95-ADBCE   96-BAEDC   97-CDEAB   98-DACBE   99-ECBDA  100-AEBDC
101-BCEAD  102-CEDBA  103-DBCEA  104-EDBAC  105-ABECD  106-BDECA  107-CADEB  108-DCBAE  109-EABCD  110-ACEDB
111-BEDAC  112-CBDAE  113-DEBCA  114-EBADC  115-ADEBC  116-BADCE  117-CDBEA  118-DABEC  119-ECABD  120-AEDCB
Voilà qui porte un bon coup à notre espoir de décrire tous les mélanges avec un seul nombre. En effet, on a marqué en rouge les mélanges qui sont des doublons. Et on remarque que (en notant f la fonction qui à un nombre associe un mélange) pour tout nombre n allant de 1 à 60, on a toujours f(n + 60) = f(n).
Si cette égalité vaut pour n'importe quelle valeur de n, alors notre espoir est carrément mort. Regardons, à tout hasard, ce qu'il se passe avec seulement 4 éléments. Il n'y a que 24 combinaisons à tester.
  1-BCDA    2-CADB    3-DCAB    4-ABDC    5-BDAC    6-CBAD
  7-DABC    8-ACBD    9-BACD   10-CDBA   11-DBCA   12-ADCB
 13-BCDA   14-CADB   15-DCAB   16-ABDC   17-BDAC   18-CBAD
 19-DABC   20-ACBD   21-BACD   22-CDBA   23-DBCA   24-ADCB
On constate exactement le même phénomène : on atteint la moitié seulement des mélanges possibles.
Pages : 1 2 3 4 5 6
Compresser une permutation
15 mai 2013
Sommaire général