Hamming mesafesinin ucgen esitsizligini sagladi

Question

Soru: Hamming mesafesinin (distance) ucgen esitsizliginin sagladini gosteriniz?

Hammig mesafesi ne diyenler icin:

$n$ basamakli (her basamagi sonlu bir cismin elemani olan) elemanlari iceren bir kod uzayimiz olsun. Buna $C$ diyelim. $x \in C$ elemanini $x=x_1x_2\cdots x_n$  olarak yazalim. 

Diyelim ki $x,y \in C$ olsun. Bu durumda  ikisi arasindaki Hamming mesafesini  $d(x,y)=|\{k \: | \: x_i \ne y_i\}|$ olarak tanimlayacagiz.

Bugun kodlama teorisi dersinde ogrencilerin cozmesi gereken sorulardan biri, burda da paylasayim dedim.

Comments

kod uzayi nedir?

---

Hamming mesafesi ne diyenler için'den sonra başlayan ilk kısım.

---

Sonlu cisimlerin carpimi mi yani?

---

Evet. $\{(a_1,a_2,\cdots,a_n) \; | \: \text{her $1 \leq i \leq n$ icin } $$a_i \in \mathbb F_q\}$.

---

Ogrencilerden biri olsaydim, kac puan almistim?

---

$100$ puanlık cevap, tabi $1$ milyon üzerinden :)

Answer 1

$x, y, z \in C$ olsun. Gostermek istedigimiz $d(x, y) \leq d(x,z) + d(y,z)$ oldugu.

Oncelikle, $i \neq j$ farkli olmak uzere, $i$inci basamaktaki sayi ile $j$inci basamaktaki sayinin arasinda bir iliski olmadigini, bunlarin birbirinden bagimsiz oldugunu gozlemleyelim. 

Simdi, iki durumumuz var. Eger $x_i = y_i$ ise bunun mesafeye bir etkisi olmuyor. Ama eger $x_i \neq y_i$ ise mesafe $1$ artiyor.

Birinci durum: Eger $x_i = y_i$ ise iki alt durum var:

• $x_i = y_i = z_i$: Bu durumda $i$ koordinatinin katkisi $d(x,y), d(x,z), d(y,z)$ mesafelerinin hepsi icin sifir.
  
• $x_i = y_i \neq z_i$: Bu durumda da $i$ koordinatinin katkisi $d(x,y)$ mesafesi icin sifir iken, $d(x,z)$ ve $d(y,z)$ mesafeleri icin bir.
  

Iki durumda da $i$ koordinatinin etkisi azalmiyor.

Ikinci durum: Eger $x_i \neq y_i$ ise uc alt durum var:

• $x_i \neq y_i = z_i$: Bu durumda $i$ koordinatinin katkisi $d(x,y)$ mesafesi icin bir, $d(x, z)$ mesafesi icin bir, $d(y,z)$ mesafesi icin ise sifir.
• $z_i = x_i \neq y_i$: Bu durumda $i$ koordinatinin katkisi $d(x,y)$ mesafesi icin bir, $d(x,z)$ mesafesi icin sifir, $d(y,z)$ mesafesi icin bir.
• $x_i \neq z_i$ ve $y_i \neq z_i$: Bu son durumda ise $i$ koordinatinin katkisi $d(x,y), d(x,z), d(y,z)$ mesafelerinin hepsi icin bir.

Goruldugu gibi uc durumda da $i$ koordinatinin etkisi azalmiyor.

Teker teker her koordinat icin, bu koordinatlarin katkilari azalmiyorsa; koordinatlarin katkisi bagimsiz oldugundan, bu katkilari topladigimizda toplam katki da azalmaz. Bu da ucgen esitligini kanitlamis olur.

Ayrica, bu mesafenin simetrik oldugu - yani $d(x, y) = d(y,x)$ oldugu - bariz. Her $x,y \in C$ icin $d(x, y) \geq 0$ ve $d(x,x) = 0$ oldugu da ayni sekilde bariz.

Comments

Aslinda bi nevi tumevarim. Sadece $n=1$ icin ispatlamak bile yetiyor, ki burda da aslinda $n=1$ icin ispat var.

Ayrica kumelerdeki simetrik farki kullanarak da ispatlanabiliyor. Belki dusunmek isteyenler olur diye yaziyorum. 

$x_i\ne y_i$ ise $z_i$ en cok biri ile ayni olabilir sadece. Aslinda bu ispati bitiren cumle. "Her farka en az bir fark geliyor" diyoruz.

Bunu kumelerdeki simetrik farkini kullanarak ucgen esitsizligini gosterebiliriz. Tabi soyle genis acidan bakinca bu da ayni olaya, mantiga denk geliyor.