Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
1 beğenilme 0 beğenilmeme
974 kez görüntülendi

Bir böcek ilk hamlesinde 2×100’lük satranç tahtasının bir birim karesine atlıyor. Bundan sonraki her hamlesinde bulunduğu birim kareyle ortak kenar paylaşan başka bir birim kareye atlıyor. Böcek, ilk 200 hamlesini kaç farklı biçimde seçerek satranç tahtasının her birim karesine tam olarak bir kez atlayabilir?

Orta Öğretim Matematik kategorisinde (467 puan) tarafından  | 974 kez görüntülendi

3 Cevaplar

1 beğenilme 0 beğenilmeme
En İyi Cevap

Simdi oncelikle kucuk durumlara bakalim. Bunun icin graf teori ve Hamiltonyan patikasi isimizi gorebilir. Yani bir noktadan diger noktaya giden butun patikalara bakabiliriz. Mesela 1 noktasindan 2 noktasina giden yollar sayisi, 2 noktasindan 1 noktasina giden yollar sayisina esittir. Bundan dolayi buldugumuz sonucu 2 ile carpacagiz tum permutasyonlari bulmak icin..

Bazi kucuk $n$ ler icin sonuclar sunlar..

  image image  image image image

(2.9k puan) tarafından 
tarafından seçilmiş
0 beğenilme 0 beğenilmeme


Tabi $n=100$ icin benim bilgisayarin cigeri yetmedi..

 

$n=1,..,20$ icin sunlari elde ettim.

 

{{1, 2}, {2, 8}, {3, 16}, {4, 28}, {5, 44}, {6, 64}, {7, 88}, {8,  116}, {9, 148}, {10, 184}, {11, 224}, {12, 268}, {13, 316}, {14,  368}, {15, 424}, {16, 484}, {17, 548}, {18, 616}, {19, 688}, {20,  764}}

Ve su degerleri WolframAlpha ya sordum

{2, 8, 16, 28, 44, 64, 88, 116, 148, 184, 224, 268, 316, 368, 424, 484, 548, 616, 688, 764}

ve sunu elde ettim

image

Ve burdan da 


image

Demekki cevap $19804$ mis.


Aslinda WolframAlpha'ya gerek yok.

image


(2.9k puan) tarafından 
tarafından düzenlendi
n = 4;
g = GridGraph[{2, n}, EdgeStyle -> Thick, VertexLabels -> "Name"];
tuple = Subsets[Range[1, 2 n], {2}];
hamiltonianPath =
Table[FindHamiltonianPath[g, tuple[[i, 1]], tuple[[i, 2]]], {i,
Length@tuple}];
cycle = DeleteCases[hamiltonianPath, {}];

toplamPermutasyon = 2 Length@cycle

checkerboard =
ArrayPlot[Table[Mod[j + i, 2], {i, 2}, {j, n}],
ColorRules -> {1 -> RGBColor[0, .55, .77],
0 -> RGBColor[.67, .9, .99]}, Frame -> False,
DataRange -> {{1, n}, {1, 2}}];

Labeled[Multicolumn[
Table[Show[{checkerboard,
HighlightGraph[g, PathGraph[cycle[[i]]],
GraphHighlightStyle -> "DehighlightHide",
EdgeStyle -> Directive[Thick, Red]]}], {i, Length@cycle}],
4], {Style["n=" <> ToString@n, 20],
Style["cevap=" <> ToString@toplamPermutasyon, 20]}, {Top, Bottom}]



Mathematica kodu..

Çok teşekkür ederim ökkeş hocam elinize sağlık bence bu tür sorularda Hamiltonyan patikasi iş görür ona bakmam lazım

Hata duzeltildi..

Euler kazandı..

Mathematica daki görseller çok iyi anlatıyor 

Aslinda biraz sansliymisim. Mathematica'nin $FindHamiltonianPath$ fonksiyonu  bir $A$ noktasindan $B$ noktasina giden EN KISA yolu buluyormus. Yani ayni uzunlukta iki yol olsa bile sadece bir tanesini buluyormus. Bu soru icin $2\times n$ icin sadece bir tane $2 n-1$ uzunlugunda patika var.


Ama mesela $3\times n$ icin veya daha genel haliyle $m\times n$,     $m,n\ge3$ icin  $FindHamiltonianPath$ fonksiyonu kullanilamaz.  Bunun yerine  $FindPath$ fonksiyonu kullanilmali.

Herbir kareye ugranacagi icin toplam patika uzunlugu $m n-1$ olur. Yani yapilmasi gereken $A$ noktasindan $B$ noktasina giden ve toplam uzunlugu  $m n-1$ BUTUN patikalarin bulunmasi gerekir.


$FindPath$ kullanan su kod isi gorur. $3\times 3$ icin bakalim. Bu arada Yesil baslama noktasini Magenta ise bitis noktasini gosteriyor.


image Mesela 1'den baslayip 3'te biten ve toplam uzunlugu (herbir kirmizi cizgiyi 1 birim kabul edersek) $3\times3-1=8$ birim olan iki tane durum var(Siyah dikdortgenin cindeki durum). $FindHamiltonianPath$ yalnizca birini buluyor.(neye gore seciyor bilmiyorum.)


n = 3;
m = 3;
g = GridGraph[{m, n}, EdgeStyle -> Thick, VertexLabels -> "Name"];
tuple = Subsets[Range[1, m n], {2}];
allPath =
Join @@ Table[
FindPath[g, tuple[[i, 1]], tuple[[i, 2]], {m n - 1}, All], {i,
Length@tuple}];
toplamPermutasyon = 2 Length@allPath

checkerboard =
ArrayPlot[Table[Mod[j + i, 2], {i, m}, {j, n}],
ColorRules -> {1 -> RGBColor[0, .55, .77],
0 -> RGBColor[.67, .9, .99]}, Frame -> False,
DataRange -> {{1, n}, {1, m}}];

Labeled[Multicolumn[
Table[Show[{checkerboard,
HighlightGraph[g, PathGraph[allPath[[i]]],
GraphHighlightStyle -> "DehighlightHide",
EdgeStyle -> Directive[Thick, Red]],
Graph[g,
VertexStyle -> {First[allPath[[i]]] -> Darker@Green,
Last[allPath[[i]]] -> Magenta},
VertexSize -> {First[allPath[[i]]] -> Medium,
Last[allPath[[i]]] -> Medium}, EdgeStyle -> Opacity@0,
VertexLabels -> None]}], {i, Length@allPath}],
7], {Style["n=" <> ToString@n, 20],
Style["cevap=" <> ToString@toplamPermutasyon, 20]}, {Top, Bottom}]

Bazi durumlar mumkun olmuyor. Mesela $3\times3$ icin 1'den 2,4,6,8'e herbir kareye ugrayarak gitmek mumkun degil. Ayni sekilde diger baslama noktalari icinde benzer mumkun olmayan durumlar var..

Figure de gorulecegi uzere Yesil nokta (baslama nokyasi) hicbir zaman 2 olmuyor. Yani $3\times3$ icin bocek ilk basta 2'ye atlamissa, herbir kareyi dolasarak hepsine ugrayamaz. Ayni sekilde 4, 6, 8 de ilk atlama noktasi olamaz..
0 beğenilme 0 beğenilmeme

Daha ilginci su olabilirdi. $8\times8$ satranc tahtasinda herhangi bir kareye atlayan bocek, bundan sonraki her hamlesinde bulunduğu birim kareyle ortak kenar paylaşan başka bir birim kareye atlıyor. Böcek, ilk 64 hamlesini kaç farklı biçimde seçerek satranç tahtasının her birim karesine tam olarak bir kez atlayabilir?

$2\times2$, $3\times3$, $4\times4$, $5\times5$, $6\times6$ icin sunlari buldum.

{{2, 8}, {3, 40}, {4, 552}, {5, 8648}, {6, 458696}}


Google'a sordugumda ise, karsimiza su cikyor..


https://oeis.org/A096969


1, 8, 40, 552, 8648, 458696, 27070560, 6046626568, 1490832682992, 1460089659025264, 1573342970540617696, 6905329711608694708440, 33304011435341069362631160, 663618176813467308855850585056, 14527222735920532980525200234503048


Yani $8\times8 $ icin 6,046,626,568 durum var.


(2.9k puan) tarafından 

Peki hangi (numaralandırılmis) birim kareye atladiginin bir önemi var mi?

Hayir yok. Mesela ilk basta sol ust koseye atlamis olsun. Ordan digerlerinin hepsine ugrayarak sag ust koseye gitme sayisi (atiyorum 10 ) olsun. Yine ilk basta sol ust koseye atlamis olsun. Sag alt koseye gitme sayisi 8 olsun. Boyle boyle, ilk atladigi noktadan diger noktalara gitden patikalarin sayisini buluyoruz ve topluyoruz. Sonra ilk atladigi noktayi degistirip ayni islemi uyguluyoruz. Onun icin ikili altkumelere bakmak yeterli. Yani mesela $3\times3$ icin {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}, {2,   3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {2, 8}, {2, 9}, {3, 4}, {3,   5}, {3, 6}, {3, 7}, {3, 8}, {3, 9}, {4, 5}, {4, 6}, {4, 7}, {4,   8}, {4, 9}, {5, 6}, {5, 7}, {5, 8}, {5, 9}, {6, 7}, {6, 8}, {6,   9}, {7, 8}, {7, 9}, {8, 9}} kumseine bakmak yeterli.


{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}}

1'den 2,3,4,...,9'a giden patikalar.

2 den 1'e giden patikaya bakmaya gerek yok.

{{2,   3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {2, 8}, {2, 9}}

2'den 3,4,...,9'a giden patikalar.

{{3, 4}, {3,   5}, {3, 6}, {3, 7}, {3, 8}, {3, 9}}

3'den 4,...,9'a giden patikalar. gibi...


Duzeltme. Aslinda var gibi. Rastgele bir kareye atlayabilir ama o kareden baslayarak herbir kareye ugramasi mumkun olmayabilir.

Teşekkür ederim

20,200 soru
21,726 cevap
73,275 yorum
1,887,797 kullanıcı