Bonjour et sois le bienvenu sur l'

 Cliquez pour afficher

Il me semble que ça coince dès n=2.

f(1,2)f(2,1). On doit avoir f(1,1) différent des deux, et... il n'y a plus de place!A Moins que j'aie tout compris de travers!

En effet ça coince pour n=2. Mais pour 3 c'est OK :

***********
  * 1 2 3 *
***********
1 * 1 2 3 *
2 * 3 1 2 *
2 * 2 3 1 *
***********

On ne peut pas construire f par récurrence ! Tout le problème est là. Le but est de trouver des n pour lesquels ça marche et pour lesquels ça ne marche pas.

Jusqu'ici :
"ça marche" contient {1,3}
"ça marche pas" contient {2}

(une petite erreur dans le tableau, le dernier 2 est un trois dans la première colone)

question : peut-on le faire avec un alphabet de 4 lettres ?

bonjour Tringlarido

 Cliquez pour afficher

c'est facile pour un nombre de lettres impair
ordonner les lettres
attribuer un indice à chaque lettre
la clef sera la lettre ayant pour indice : (indice de la deuxième lettre moins indice de la deuxième lettre plus nombre de lettres si la différence est négative)
si le nombre de lettres est pair, des problèmes apparaissent :
si la différence des indices des deux lettres est la moitié de l'effectif de l'alphabet, les deux permutations auront la même clef
si on crée un saut d'indice pour forcer un effectif impair, la clef pourrait avoir comme indice justement l'indice sauté

Salut,

réponse pour les alphabets impairs (bien joué plumeteore) :

 Cliquez pour afficher

On peut bien sur considérer que notre alphabet est . Dans le cas impair, la proposition la plus simple consiste à prendre pour clé :

1) Les fonctions   et sont bien injectives et on peut détecter les erreurs sur une lettre.

2) Dire que et équivalent à . Comme est inversible dans cette équation est équivalente à . On détecte donc les permutations.

Rq : prendre dans le cas pair permet de détecter les erreurs sur une lettre; mais donc

et on ne peut pas détecter les permutations des n couples (a,a+n/2).

 Cliquez pour afficher

En effet, on a pas d'injectivité : f(1,1) = f(1,2).
Par contre cette méthode détecte les permutations.

bonjour Tringlarido
quand le nombre de lettres est pair, on peut ajouter à la fin de l'alphabet une lettre vide, qui ne fera jamais partie d'un mot
puis calculer la clef de n'importe quel mot de deux lettres en tenant compte de cette lettre vide, donc dans le cadre d'un nombre de lettres impair
par exemple abcd -> abcd?
abcd?abcd
bd : distance de 2; la clef est la deuxième lettre de l'alphabet : b
db : distance de 3, comprenant le ?; la clef est la troisième lettre : c
la somme des ordres des clefs d'une paire de permutations est le nombre de lettres plus un; comme cette somme est impair, les ordres de ces clefs sont toujours différents

Certes c'est une solution de clé. Elle consiste à ajouter une lettre dans l'alphabet (ce qui est le principe pour le code ISBN des livres qui prennent en compte le caractère X pour la clé (X signifie 10)). Elle présente justement l'inconvénient d'ajouter un caractère supplémentaire.

L'exercice ne consiste pas à contourner le problème pour trouver une clé qui marche, mais à savoir si une telle clé existe en restant dans le cadre d'un alphabet fixé ! Cependant, c'est peut-être une bonne méthode de commencer à ajouter une lettre et voir si on peut la supprimer après coup.

bonjour Tringlarido
on peut avoir le même effet sans rajouter une lettre
soient n le nombre de lettres, i(1) l'indice de la première lettre du mot et i(2) l'indice de la deuxième lettre
si i(1) < i(2), la clef a comme indice i(2)-i(1)
si i(1) > i(2), la clef a comme indice i(2)-i(1)+n ou i(2)-i(1)+1 selon que n est impair ou pair
si i(1) = i(2), la clef a comme indice i(1) et i(2)

correction de la ligne : si i(1) > i(2), la clef a comme indice i(2)-i(1)+n ou i(2)-i(1)+1 selon que n est impair ou pair
devient :
si i(1) > i(2), la clef a comme indice i(2)-i(1)+n ou i(2)-i(1)+n+1 selon que n est impair ou pair

Rq : on ne peut pas le faire pour n=2. Donc une approche par une méthode générale est risquée.

Plumeteore : ça ne marche pas :

 Cliquez pour afficher

J'identifie les lettres avec les indices. On peut toujours considérer que l'alphabet est ou .

Prenons le cas n impair. Tu proposes comme clé :

où on considère tout modulo n.

Ca ne marche pas ! On détecte les permutations, mais pas les erreurs en général. Prenons a < n/2 une lettre, alors:

Ainsi les mots (a,2a) et (a,a) ont la même clé ! On ne détecte pas l'erreur sur la deuxième lettre !

salut

si f est injective par rapport à chacune des variables alors f est surjective par rapport à chacune des deux variables donc f est surjective
mais f peut-elle être injective ? (pb de cardinal, non ?)
donc peut-on distinguer et les erreurs sur une lettre et les permutations
comment peut-on distinguer qu'on a fait une erreur sur une lettre et pas sur les deux lettres?....

Non, f ne peut pas être injective évidemment, elle envoit n points (le cardinal de l'alphabet) sur le même point...

Oui, on peut distinguer et les erreurs sur une lettre  et les permutations, comme le montre l'exemple que j'ai donné sur 3 lettres et la généralisation proposé dans le cas impair par plumeteore.
Ceci est du au fait qu'une permutation est une erreur sur deux lettres très particulière.

Par contre il y a des problèmes combinatoires dans le cas où n est pair. La preuve en est qu'il est impossible de le faire pour n=2 !

Ce n'est pas parce que c'est moi qui ai posé le problème que je n'ai pas le droit d'y participer...

mini-théorème : On ne peut le faire avec 4 lettres

 Cliquez pour afficher

*****************
* 1 * 3 * 4 * 2 *
*****************
* 4 * 2 * 1 * 3 *
*****************
* 2 * 4 * 3 * 1 *
*****************
* 3 * 1 * 2 * 4 *
*****************

où le terme de la ligne i et la colonne j correspond à f(i,j)

Dans chaque ligne et chaque colonne apparait chaque terme de l'ensemble <=> à l'injectivité de f sur chaque variable

On a aucune symétrie axiale <=> f(a,b) différent de f(b,a)

On peut aussi le réecrire :

 Cliquez pour afficher

12 34
34 12

43 21
21 43