Değişik bir problem? 4

Question

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?

Answer 1

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..

   

Answer 2

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

Ve burdan da 

Demekki cevap $19804$ mis.

Aslinda WolframAlpha'ya gerek yok.

​

Comments

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.

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..

Answer 3

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.

Comments

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