Demontrer distance de Hamming ????

[Anonyme]

J'ai un probleme pour démontrer que la distance de Hamming est bien une
distance. Je ne vois pas comment montrer l'inégalité triangulaire.

Voila la définition que j'ai de la distance de hamming:

Soient deux elements X=(x1, ..., xn) et Y=(y1, ... yn) de F^n avec F un
ensemble fini.
La distance de Hamming d(X,Y) est le nombre d'indices i tels que xi est
différent de yi.

Savez vous comment on demontre l'inegalité triangulaire
d(X,Z)<=d(X,Y)+d(Y,Z) ?

Merci

[Anonyme]

Le 22/09/04 14:07 , barbadchov a exprimé son opinion en les termes suivants:

> J'ai un probleme pour démontrer que la distance de Hamming est bien une
> distance. Je ne vois pas comment montrer l'inégalité triangulaire.
>
> Voila la définition que j'ai de la distance de hamming:
>
> Soient deux elements X=(x1, ..., xn) et Y=(y1, ... yn) de F^n avec F un
> ensemble fini.
> La distance de Hamming d(X,Y) est le nombre d'indices i tels que xi est
> différent de yi.
>
> Savez vous comment on demontre l'inegalité triangulaire
> d(X,Z)<=d(X,Y)+d(Y,Z) ?

Soit X, Y et Z quelconques.
Je note d=d(X,Z), r=d(X,Y) et s=d(Y,Z).

Suposons connus les indices i_1,...,i_r tels que x_k != y_k si et
seulement si k != x_m pour tout m.
Supposons connus de même les indices j_1,...,j_s pour Y et Z.

Alors si k n'appartient pas à {i_m, m=1...r} union {j_m,m=1...s}, on a
x_k=y_k=z_k.

Par suite d<= card de l'union considérée donc d< r+s!

Je crois que ça marche.

Cordialement,

--
Denis

Pour me joindre, enlever les _ !

Vieillir est un luxe de jeune et une manie de vieux.

[Anonyme]

Denis wrote:
> Le 22/09/04 14:07 , barbadchov a exprimé son opinion en les termes
> suivants:
>[color=green]
>> J'ai un probleme pour démontrer que la distance de Hamming est bien
>> une distance. Je ne vois pas comment montrer l'inégalité triangulaire.
>>
>> Voila la définition que j'ai de la distance de hamming:
>>
>> Soient deux elements X=(x1, ..., xn) et Y=(y1, ... yn) de F^n avec F
>> un ensemble fini.
>> La distance de Hamming d(X,Y) est le nombre d'indices i tels que xi
>> est différent de yi.
>>
>> Savez vous comment on demontre l'inegalité triangulaire
>> d(X,Z)
>
> Soit X, Y et Z quelconques.
> Je note d=d(X,Z), r=d(X,Y) et s=d(Y,Z).
>
> Suposons connus les indices i_1,...,i_r tels que x_k != y_k si et
> seulement si k != x_m pour tout m.
> Supposons connus de même les indices j_1,...,j_s pour Y et Z.
>
> Alors si k n'appartient pas à {i_m, m=1...r} union {j_m,m=1...s}, on a
> x_k=y_k=z_k.
>
> Par suite d
> Je crois que ça marche.
>
> Cordialement,
>
Ok merci beaucoup.