[MD-sorular] guvercin yuvasi ilkesi ve kod sorusu

[Ali Ilik]

   SORU: C bir binary (n, M, d)-kod olsun. d>2n/3 ise M<=2 oldugu  
nasil kanitlanir?

   Basit bir soru ama matematiksel kaniti nasil yapilir? Ana fikir  
acik: guvercinyuvasi ilkesi. Kod binary oldugundan, M>2 olsa, mesela  
ilk sutunda en az iki hane ayni olacak. Ayni dusunce diger kolonlara  
da uygulanirsa cikacak ama cikmiyor iste... Cikamadi bir turlu.

   Sorudaki onerme binary olmayan kodlar icin gecerli degil galiba....  
O yuzden ucgen esitsizligini kullanmak tehlikeli olabilir. Galiba  
stronger bir ucgen esitsizligi yardimci olabilir. Ifadesi nasildir  
acaba? Ama tum bunlari bir turlu matematiksel forma dokemedi bu  
satirlarin yazari. O yuzden ici elvermiyor ileriki ceptirlari  
calismaya. Ayip yahu, bir guvercin yuvasi ilkesi ama bu kombinatorik  
bu kadar kilmiyidi yavu? Uyuz etti. Guvercin yuvadan cikmiyor.

   TANIM. Bir /binary/ikilik (n, M, d)-kod,/ n harften (harfler 0 ya  
da 1 olabilir) ve kelimeler arasindaki minumum uzaklik d olan ve M  
kelimeden olusan bir kumedir.

   Ornegin bir (3, 2, 3)-kod {000, 111} kumesidir.
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20081224/f3211965/attachment.htm