Gönderen Konu: Daire Diliminin Boyanması {çözüldü}  (Okunma sayısı 112 defa)

Çevrimdışı scarface

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3012
  • Karma: +21/-0
  • İstanbul
Daire Diliminin Boyanması {çözüldü}
« : Haziran 18, 2020, 03:36:57 öö »
Problem: $k$ farklı renkte boyaya sahibiz. Bir daire $n$ dilime ayrılmış olsun. Ardışık dilimler farklı renkte olacak biçimde $n$ dilim kaç farklı yolla boyanır? (Burada, döndürmeler sonucu bir boyama diğerinden elde edilebilir. Yani $abc$, $bca$, $cab$ gibi dairesel durumlar farklı olarak ele alınacaktır.)
« Son Düzenleme: Haziran 24, 2020, 05:47:51 ös Gönderen: scarface »
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

Çevrimdışı scarface

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3012
  • Karma: +21/-0
  • İstanbul
Ynt: Daire Diliminin Boyanması
« Yanıtla #1 : Haziran 24, 2020, 05:47:22 ös »
Problem, indirgemeli diziler için iyi bir uygulamadır.

$n$ tane dilim $k$ tane renk ile istenen özellikte $a_n$ farklı yolla boyanabiliyor olsun. $n=1,2,3$ durumlarını incelemek kolaydır: $a_1=k$, $a_2=k(k-1)$, $a_3=k(k-1)(k-2)$ olur.

$n\geq 4$ durumunu inceleyelim. $i=1,2,\dots, n-1$ olmak üzere $i$-inci dilim ile $i+1$-inci dilim farklı renkte olacak şekilde tüm boyamaların sayısı $k\cdot (k-1)^{n-1}$ dir. Bu tüm durumların içinde $n$-inci dilim ile $1$-inci dilimin aynı renkte olduğu istenmeyen durumlar da vardır.


Bu istenmeyen durumları hesaplayalım: $n-1$-inci dilim ile $n$-inci dilim farklı renkte ve $n$-inci dilim ile $1$-inci aynı renkte olduğundan $n-1$-inci dilim ile $1$-inci dilim farklı renktedir. O halde bu ilk $n-1$ dilimde, ardışık dilimler farklı renkte olacak biçimde boyanma sayısı $a_{n-1}$ olur.

İstenen durumların sayısı ile istenmeyen durumların sayısı toplanıp tüm durumların sayısına eşitlenirse $n \geq 4$ için

$$ a_n + a_{n-1} = k(k-1)^{n-1} \tag{1}$$

indirgeme bağıntısı elde edilir. Homojen doğrusal indirgemeli dizinin karakteristik denklemi $r+1=0$ olup bir kök $r_1=-1$ dir. Ayrıca $(1)$ deki homojen olmayan bağıntı, homojen hale getirilmek istenirse karakteristik denklem için bir kök de $r_2=k-1$ olacaktır. İndirgemeli dizilerin çözüm teorisinden bunu biliyoruz. Fakat bilmesek bile $(1)$ de $n$ yerine $n+1$ yazıldıktan sonra ikinci mertebeden homojen denklem elde etmek zor değildir. Dolayısıyla $(1)$ bağıntısını $n\geq 4$ için

$$ a_n=C_1r_1^n + C_2r_2^n = C_1(-1)^n + C_2(k-1)^n \tag{2} $$

biçiminde açık halde ifade edebiliriz. $C_1$, $C_2$ sabitlerini belirlemek gerekiyor.

$n=4$ için $a_4 + a_3 = k\cdot (k-1)^3$ olup $a_4= k\cdot (k-1)^3 - k\cdot (k-1)\cdot (k-2)$

$n=5$ için $a_5 + a_4 = k\cdot (k-1)^4$ olup $a_5= k\cdot (k-1)^4 - k\cdot (k-1)^3 + k\cdot (k-1)\cdot (k-2)$

yazılır. $(2)$ de $n=4$ ve $n=5$ yazılarak $C_1$, $C_2$ değerleri çözülürse $C_1 = k-1$, $C_2=1$ elde edilir. Dolayısıyla $n\geq 4$ için

$$ a_n = (k-1)(-1)^n + (k-1)^n \tag{3}$$

formülü elde edilir.
« Son Düzenleme: Temmuz 02, 2020, 04:04:34 öö Gönderen: scarface »
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 
SimplePortal 2.3.3 © 2008-2010, SimplePortal