Dama

Değişik bir dama oyununda hamleler sadece kenar komşusu olan karedeki taşın üzerinde atlayıp üzerinden atlanılan taşı yeme şeklinde yapılabilmektedir.
Sınırsız büyüklükteki bir oyun tahtasında tüm taşlarımız belli bir yatay çizginin altındayken yatay çizginin 1 sıra üzerine taş çıkarabilmek için gerekli minimum taş sayısı 2 dir ve bu işlem 1 hamle ile yapılabilir. Benzer şekilde yatayın 2 sıra üzerine taş çıkarabilmek için gerekli minimum taş sayısı 4 , hamle sayısı da 3 tür.

https://img191.imageshack.us/img191/...atcheckers.jpg


soru: yatay sınır çizgisinin 5 sıra yukarısına taş çıkarabilmek için gerekli minimum taş ve hamle sayısı nedir? ya da daha düzgün soralım, bu mümkün müdür?



not: çok eski ve ünlü bir sorudur.

inekle otla uğraşırken bu güzel soru güme gitmesin :)

Doğrudan çekildim üstad meydandan... :)

soruyu anlamadım bile, biraz daha açıklama yapabilirmisiniz?

çizginin 2 üstüne çıkarken yaptığınız son hamlede, yenilmiş yani hayali bir taşı oynatıyormuşsunuz gibi geldi bana, çünkü bir önceki hamlade o taş yendi ve yerinde yok. ve bu taş kendisini yiyen taşın üzerinden atlatılıyor.
Yani bu örnekle iki üste çıkma olmuyor.

üzerinde 1 yazan taş üstündekini yedi ve köşesinde 3 yazan kareye geldi (yediği taş oyundan çıktı)şimdi 2 nolu taş sağındaki taşı yedi ve 1 nolu taşın tam altında son durumdada 2 nolu taş 1 noluyu yiyerek çizginin 2 sıra üstünde
yani şekilde bir problem yok

Haklısınız öğretmenim ben ilk hamleyi 2 nolu taşa yaptırdım o yüzden oldu.

paradoks12'den alıntı:

soruyu anlamadım bile, biraz daha açıklama yapabilirmisiniz?

hocam bir miktar taşı hepsi kalın çizginin altında olacak şekilde sınırsız büyklükteki bir satranç tahtasına yerleştiriyosunuz. sadece komşu karedeki taşın üzerinden bir ilerdeki kareye atlayıp üzerinden atladığınız taşı da yemek suretiyle 5. sıraya taş çıkarabilir misiniz diye soruluyor. çıkarabilirseniz bunu en az kaç taşla ve kaç hamleyle yaparsınız diyor, çıkarılmayacağını düşünüyosanız da doğal olarak ispatlanması lazım :)

MatematikciFM'den alıntı:

Haklısınız öğretmenim ben ilk hamleyi 2 nolu taşa yaptırdım o yüzden oldu.

hocam şekli ben çizdim biraz garip olmuş. o sayıları okların yani hamlelerin numarası olarak düşünmüştüm ama taşların ve karelerin numarası gibi algılanıyor.

Benim aklım farklı dama oyunu ibaresine takıldı. Bildiğimiz dama oyunu değil mi bu?

anladığım kadarıyla burda rakip taşlar benim taşlarım diye bir olay yok; bir elde kullandığın taşı bir sonraki elde yeme durumu oluşmuş. yada şekilden ben onu çıkardım, yanlış mı anlamışım?

en iyisi ben ne anladığımı açıklamaya çalışayım siz yanlış anladığım yerleri düzeltin daha kolay olacak:)

ilk durumda yatay çizginin altına istediğin gibi istediğimiz şekilde taşları dizip, bir şekilde yukarı doğru gitmeye çalışıyoruz, bütün taşarı kullanıyoruz, ortada rakip falan yok amaç sadece istenilen yere bir şekilde ulaşmak

Farklılığı rakip olmamasıymış, anlaşıldı. Kendin çal, kendin oyna misali.

paradoks12'den alıntı:

ilk durumda yatay çizginin altına istediğin gibi istediğimiz şekilde taşları dizip, bir şekilde yukarı doğru gitmeye çalışıyoruz, bütün taşarı kullanıyoruz, ortada rakip falan yok amaç sadece istenilen yere bir şekilde ulaşmak

tam anlamıyla olay budur, tabi yenilen taş oyuna geri dönemiyor.

8 taş 7 hamle ile çizgiyi 3 adım geçtim:) şimdilik

24 taş 23 hamle ve 4 ilerleme, az kaldı sanırım ulaşmak üzereyim, yada belki daha fazla gidilemeyebilirde

20 taşla da 4. sıraya çıkalabilyor olması lazım ya da 21 olabilir

23 taş ile 22 hamle yaparak 4. sıraya çıkabildim. 21 taş ve 20 hamle mümkün durmuyor gibi. (tabi şu anda bir acı kahvem ve yanına bir sigaram olsa işler değişebilir)
esasında iş 5. sıraya çıkmak olduğu için şunu belirtmek gerekir ki, bunu yapabilmek için kahvemin oldukça taze ve güney amerika işi, sigaramın ise o taraflardan meşhur yaprak sarma işi olması gerek.:) şaka bir yana, bana 5. sıraya çıkmak pratik olarak mümkün gibi durmuyor. ama teorik olarak bakarsak sanki bir mümkün yolu var. sorunun karışıklığı biraz buradan kaynaklanıyor.

4. sıraya çıkmak için 21 taş dedim ama sayıyı yanlış hatırlıyor da olabilirim buna takılmayalım.

gereksizyorumcu'den alıntı:

4. sıraya çıkmak için 21 taş dedim ama sayıyı yanlış hatırlıyor da olabilirim buna takılmayalım.

bu soruyu çözelim, daha sonra bu konuya dönelim. acaba 23 taştan daha az taş ve 22 hamleden daha az hamle yapılarak 4. sıraya gidilebilirmi? soru içinden soru çıkaralım yani.

matera'den alıntı:

bu soruyu çözelim, daha sonra bu konuya dönelim. acaba 23 taştan daha az taş ve 22 hamleden daha az hamle yapılarak 4. sıraya gidilebilirmi? soru içinden soru çıkaralım yani.

peki ben de buna uğraşayım ama belirteyim benim işim sizinkinden kat kat kolay :)

gereksizyorumcu'den alıntı:

peki ben de buna uğraşayım ama belirteyim benim işim sizinkinden kat kat kolay :)

orası kesin. balon fıkrasında denildiği gibi: tam matematikçi işi. :)
5. sıraya gelinip gelinemeyeceği konusunda epey yol kat ettim. bugün olmasa da yarın sonuçları açıklarım.

20 tane ile 4 yukarı çıkabildim ama şekil eklemek biraz zor olacak

gereksizyorumcu'den alıntı:

20 tane ile 4 yukarı çıkabildim ama şekil eklemek biraz zor olacak

20 taş ile 4 yukarı çıktıysanız gerçekten, çözümü görmek isterdim

21 taş ve 20 hamleden aşağısını bulamadım ben. ilkin 23 taş 22 hamle hesaplamıştım ancak 21 taş ve 20 hamleyide sonradan (kahve+sigaradan sonra :) ) bulabildim..
siz muhtemelen 20 hamle kast ettiniz o halde.

gereksizyorumcu'den alıntı:

resim neden oynamıyo anlamadım o kadar da uğraşıp 20 tane resimi peş peşe ekledim :)

21 taş altı için bir çözüm bulamadım. çiziminizde 20 taş görülüyor. bir de hareket etseler ne iyi olurdu :)

https://img3.imageshack.us/img3/1128/mat120hamle.jpg

hareketli olmadı ama tüm hamlelri yanyana dizdim her türlü engeli aştım :)

https://www.matematiktutkusu.com/uploads/21.gif

ben bir hamle hatası görmedim, yani çözüm doğru. taşları en başta uygun şekilde dizmekte bitiyor iş. ve hamleleri doğru yapmakta.

soruya bir ipucu ile hareket kazandıralım

5 sıra yukarıya sonlu sayıda taş ve hamleyle çıkmak mümkün değildir. bunu ispatlayabilir misiniz?

haftasonu geldi bu soruya uğraşan yok mu?

ben bazı şeyler paylaşıcam soruyla ilgili olarak
5. seviyeye sonlu sayıda taş kullanılarak çıkılamayacağını göstermek bana biraz zor bir çözümmüş gibi geliyor. pek bişey düşündürtmüyor soru ben sadece şunu görebildim. taşların iki farklı hareketi var.
1.si bir taş diğerinin üzerinden atlayıp iki seviye yukarı çıkıyor
2.si bir taş diğerinin üzerinden atlayıp aynı seviyesinde kalıyor
1. durum sanki pozitif bir durum istenilen birşey 2. durum ise nötr bir durum
çizginin üzerine taş çıkarmak için ne kadar pozitif hareket ne kadar nötr hareket yapmamız gerekir sanki bunların bir fonksiyonu kuralı yazılıpta bu seviye çıkışı için bu fonksiyonların alması gereken minimum bir değer olmalı ilk 4 seviye içinde bu değere ulaşılıcak fakat daha yüksek seviyelere çıkmak için bu değere ulaşılamıyacak gibi bişeyler gösterilerek ispat yapılabilirmi çünkü bu tarz sorularda benim gördüğüm ispat olaylarında genel yaklaşım tarzı hep bu oluyor diye düşündüm ama bunları matematiğe dökmek :)
ilk 4 seviyenin geçilişinde bunlara baktım fakat pek bir şey yakalayamadım

Sınır hattının gerisinde belli bir düzen ile yerleşik 20 taş ile 19 hamlede 4. seviyeye çıkıldığına şahit olmuştuk. (gereksizyorumcu'nun animasyonu)
Bir kabul yapalım ve sonuçlarına bir göz atalım.
Şimdi; k sayıda (k, sonlu bir sayı olmak üzere k>20 ) taş ve kaçınılmaz olarak k-1 hamle ile teorik olarak 5'nci seviyeye çıkabileceğimizi düşünelim. Bu düşüncenin kaçınılmaz sonucu olarak (k-1) taş ile maksimum 4. seviyeye ulaşmış olmamız lazım gelir. Bu seviyeye erişen taş sayısı ise n₁ olsun. (k-2) adet taş için takdir edersiniz ki, maksimum değer aynı şekilde 4. seviye olmalıdır. ( gerekçemiz oldukça basit: k=20 için 4. seviye erişilebilirdir.) (k-2) taş için 4. seviyeye getirilebilen taş sayısı n₂ olsun. O halde şunu artık rahatlıkla söyleyebilirizki;
Hipotez1: k≥20 ve k∈Z olmak üzere A:{20,21,22,23,24,...............(k-2),(k-1),k.} için her durumda 4. seviye ulaşılabilir olup bu seviyeye çıkabilen taş sayıları;
k sayıda taş için n₁
(k-1) sayıda taş için n₂
(k-2) sayıda taş için n₃
.
.
.
.
k=20 sayıda taş için n_p=1 olacaktır. (bkz: gereksizyorumcu'nun sayfa3 teki animasyonu.)
Hipotez2: n₁≥n₂≥n₃≥.........n_r........>n_p=1 ilişkisi var olmalıdır. (Dikkat edilirse n_p değerinden "büyük olmak zorunda olan" bir n_r değeri vardır. Bu değer tahmin edeceğiniz gibi 2 olmalıdır. Örneğin çok basit bir şekilde animasyondaki k=20 taşlık dizilimi simetrik olacak şekilde k=40 taş yaparsanız n_r=2 olacaktır. Belki k=30 içinde n_r=2 olabilir ama önemli olan bunu göstermek değil.)
Anlaşıldığı üzere k sayısının büyüklüğüyle paralel olarak n_? değerleride büyüyecektir. Bu durumda final hamlesine alternatif n₁ sayısı kadar "yem" taşımızın olacağı açıktır. Bunu sağlayacak "avcı taş" ise 3. seviyeden çıkagelecektir.
Hipotez3: n₁ taşlarının her biri, belli bir küme taşın "eş-örnek" yani aynı tarz bir hamle ve oyun silsilesinin sonuçları ise, 4. seviyedeki taş dağılımları, 5. seviyeye çıkışa olanak verecek nitelikte olamaz. örneğin animasyondaki taş kümesinin bir simetriği ile hemen yanında yapacağımız ikinci bir eşörnek oyun ile 4. seviyeye çıkan taş ile bu taşın izlediği yol ve varacağı kare aynı kalacaktır. Bu durumda amaca gideceğimiz her bir "taş kümesi" ile oynayacağımız "bağımsız oyunlar" herbiri birbirinden bağımsız olmalı başka deyişle orijinal nitelik taşımak zorundadır.
Bu koşullar altında "eşörnek olmayan" oyun silsileleri ile bir hat üzerinde "rastgele aralıklarla" sıralanmış n₁ taş elde ettiğimizi düşünerek finale yaklaşalım.
Hipotez4: Sınır hattının üzerindeki 3. sırada yalnız bırakılmış avcı taşın önüne getirilmek üzere yem edilecek n₁ kadar rastgele aralıklarla dizili "yem taşlarımız" var.
Yatay 4.sıra hat üzerinde rastgele dağılmış n₁ adet taş kümesinden en az 1 tanesini Avcı taşın önüne getirilebilecek şekilde bir permütasyon seçilebilirdir. :)
Şimdi biraz düşünme payı bırakarak ara veriyorum.

aerturk39'den alıntı:

ben bazı şeyler paylaşıcam soruyla ilgili olarak
5. seviyeye sonlu sayıda taş kullanılarak çıkılamayacağını göstermek bana biraz zor bir çözümmüş gibi geliyor. pek bişey düşündürtmüyor soru ben sadece şunu görebildim. taşların iki farklı hareketi var.
1.si bir taş diğerinin üzerinden atlayıp iki seviye yukarı çıkıyor
2.si bir taş diğerinin üzerinden atlayıp aynı seviyesinde kalıyor
1. durum sanki pozitif bir durum istenilen birşey 2. durum ise nötr bir durum
çizginin üzerine taş çıkarmak için ne kadar pozitif hareket ne kadar nötr hareket yapmamız gerekir sanki bunların bir fonksiyonu kuralı yazılıpta bu seviye çıkışı için bu fonksiyonların alması gereken minimum bir değer olmalı ilk 4 seviye içinde bu değere ulaşılıcak fakat daha yüksek seviyelere çıkmak için bu değere ulaşılamıyacak gibi bişeyler gösterilerek ispat yapılabilirmi çünkü bu tarz sorularda benim gördüğüm ispat olaylarında genel yaklaşım tarzı hep bu oluyor diye düşündüm ama bunları matematiğe dökmek :)
ilk 4 seviyenin geçilişinde bunlara baktım fakat pek bir şey yakalayamadım

evet hocam benim bildiğim ispatı bu dediklerinizin matematiğe dökülmesi, başka bir yoldan ispatı da muhakkak vardır belki ama bilmiyorum, zaten sonsuz sayıda hamle kombinasyonuyla 5. seviyeye taş çıkarılabildiği ispatlanmış.

neyse sorudaki bir güzelliği de paylaşayım çözümde altın oran da kullanılıyor desem ne düşünürdünüz?




matera hocam,
fikirlerinizi okudum , eğer bu dediklerinizi gösterebilirseniz doğru soruyu çözebilirsiniz ama ipucu olarak verilen bilgiden de anlaşılacağı üzere başlangıç noktanız yani 5. seviyeye taş çıkartılabiliyor olmsı durumu hatalı , doğal olarak da bu dediklerinizi göstermeniz pek mümkün değil. isterseniz bu uğraşınızı kesmemek adına çözümü daha sonra da yazabilirim ama bir saıncası yoksa bu akşam ya da en geç yarın kendi bildiğim çözümü ,tabi o zamana kadar bir çözüm getirlmezse, yazmak istiyorum.

gereksizyorumcu'den alıntı:

evet hocam benim bildiğim ispatı bu dediklerinizin matematiğe dökülmesi, başka bir yoldan ispatı da muhakkak vardır belki ama bilmiyorum, zaten sonsuz sayıda hamle kombinasyonuyla 5. seviyeye taş çıkarılabildiği ispatlanmış.

neyse sorudaki bir güzelliği de paylaşayım çözümde altın oran da kullanılıyor desem ne düşünürdünüz?




matera hocam,
fikirlerinizi okudum , eğer bu dediklerinizi gösterebilirseniz doğru soruyu çözebilirsiniz ama ipucu olarak verilen bilgiden de anlaşılacağı üzere başlangıç noktanız yani 5. seviyeye taş çıkartılabiliyor olmsı durumu hatalı , doğal olarak da bu dediklerinizi göstermeniz pek mümkün değil. isterseniz bu uğraşınızı kesmemek adına çözümü daha sonra da yazabilirim ama bir saıncası yoksa bu akşam ya da en geç yarın kendi bildiğim çözümü ,tabi o zamana kadar bir çözüm getirlmezse, yazmak istiyorum.

Bu dediklerimin daha detaylarına inebilsem ve siz bunu anlayabilseniz, ben harvard da siz cambridge da matematik profesörü olurduk :) şaka bir yana, benim izahatlarım doğrultusunda sonlu bir sayıda (belki sonsuza yakın sonlu bir sayıda) 5. seviyeye ulaşılabiliyor. en azından benim uslamlamalarım sonucu gördüğüm bundan ibaret. aksi tezlere açığım...

Bu arada yaklaşımıma daha berraklık katması açısından şunu söylemek istiyorum. Animasyondaki 20 taşlı kısmı bir "hücre" olarak düşünürseniz, benim kast ettiğim, toplam k tane taş içeren ve birbirlerinden taş sayısı ve dizilim olarak farklı n sayıdaki hücrenin herbiri için (en azından çoğu için) farklı oyunlar kurgulamak şartıyla 4. seviyeye her hücreden 1 temsilci (taş) çıkarılmak suretiyle öngördüğüm şeyler gerçekleşebilir. şimdi ben olaya somut bir yaklaşım sunamadığım için (ki sunmak olanaksız) bunu anlamakda güçlük çekilebilir. bir kağıt ve kalem ile bu dediklerimi anlatmaya çalışsam daha anlaşılır olurdum.

hocam ben demek istediğinizi anladım , siz rekürsif bir şekilde bir üste daha üste yetecek kadar taşı bir alttan yollamaya çalışıyosunuz ama dediğim gibi bunun sonlu operasyonla yapılamayacağını gösterebiliyoruz . hatta ispatını yazınca sizin bu yukarıda bir ileriye gidebilecek şekilde taş grubu oluşturma hipotezinizin de nasıl çökertildiğini görebileceğiz çünkü ispatta bu da kısmen gösteriliyor.

gereksizyorumcu'den alıntı:

hocam ben demek istediğinizi anladım , siz rekürsif bir şekilde bir üste daha üste yetecek kadar taşı bir alttan yollamaya çalışıyosunuz ama dediğim gibi bunun sonlu operasyonla yapılamayacağını gösterebiliyoruz . hatta ispatını yazınca sizin bu yukarıda bir ileriye gidebilecek şekilde taş grubu oluşturma hipotezinizin de nasıl çökertildiğini görebileceğiz çünkü ispatta bu da kısmen gösteriliyor.

hayır hayır hayır.... siz kesinlikle anlamamışsınız...
Benim yaptığım şey, taşları yukarılara yığmak yada üste yetecek kadar taşı bir altta biriktirmek değildi ki. değil, kesinlikle değil. bunu anladıysanız ben üzülürüm şimdi.. Aslında sizin benim anlattığım olaydan anladığınız, bu sorunun kendi öz-çıkmazı. bu çıkmazın kafalarımızda oluşturduğu "önyargı".

https://img14.imageshack.us/img14/7256/matcheckers.jpg


bi tane hedef kare belirleyip ona varmaya çalışmak üzere tüm kareleri şekildeki gibi hedef kareye uzaklıklarına bağlı olarak değer verelim. örneğin şeklin görünür kısmında sağ alt köşedeki kare 13 birim uzakta olduğu için x¹³ değerinde olsun.

şimdi 3 değişik hamle olabilir;
1.hamle hedefe doğruysa
xⁿ değerindeki bir taş x^n-1 değerindeki bir taşın üstünden atlayıp x^n-2 değerindeki bir taş oluşturacaktır
yani toplam değişim x^n-2-x^n-1-xⁿ=x^n-2.(1-x-x²)

2.hamle nötürse
xⁿ değerindeki bir taş x^n-1 değerindeki bir taşın üstünden atlayıp xⁿ değrindeki başka bir taş oluşturacaktır.
toplam değerdeki net değişim xⁿ-xⁿ-x^n-1=-x^n-1 olacaktır.

3.hamle hedeften uzağa doğruysa (saçma ama olsun yazmak lazım)
xⁿ değerindeki bir taş xⁿ⁺¹ değerindeki bir taşın üstünden atlayıp xⁿ⁺² değerindeki bir taş oluşturacaktır
değerdeki net değişim= xⁿ⁺²-xⁿ⁺¹-xⁿ=xⁿ.(x²-x-1)


şimdi gri bölgede yani bize taş yerleştirmemiz için izin verilen bölgede bir mikta taşımız olsun ve bunların toplam değeri S olsun.
x=(√5-1)/2 için
1. hamleyle S değerindeki değişim 0 dır (1-x-x²=0)
2. hamleyle S değerinde negatif değişim elde ederiz (-x^n-1<0)
3. hamleyle S değerinde negatif değişim elde ederiz (x²-x-1=1-√5<0)

yani hangi hamleyi yaparsak yapalım S değerini artıramıyoruz en fazla yapabildiğimiz bir sonraki hamleye S yi değiştirmeden devam edebilmek.

şimdi gri bölgedeki tüm karelere birer taş yerleştirdiğimizi düşünüp mümkün olan en büyük S değrini hesaplayalım.

ilk sıradan x⁵+2.x⁶+2.x⁷+....
ikinci sıradan x⁶+2.x⁷+2.x⁸+....
üçüncü sıradan x⁷+2.x⁸+2.x⁹+....
...
n. sıradan xⁿ⁺³.(x+2x²+2x³+...)
...

x+2x²+2x³+...=x+2.(x²+x³+x⁴...)=x+2x².(1+x+x²+...) , geometrik seri toplamından
=x+2x².(1/(1-x)) , ayrıca x i altın oran ya da 1-x-x²=0 denkleminin kökü olarak seçmiştik yani 1-x=x² , yerine yazılırsa

=x+2x².(1/x²)=x+2 elde edilir , yani parantez içindeki x+2x²+2x³+... lı kısım x+2 değerinde oluyormuş.

öyleyse n. sıradaki tüm taşların toplam değeri xⁿ⁺².(x+2) olur
bunu x=1 den ∞ a toplarsak

S_max=(x+2).(x⁴+x⁵+...)
=(x+2).x².(x²+x³+...) , x²+x³+... toplamının 1 olduğunu yukarıda geometrik toplamda göstermiştik.
S_max=(x+2).x²=x³+2x²
S_max=x³+2x²+x-x=(x³+x²-x)+x+x²=x(x²+x-1)+x+x² , ayrıca 1-x-x²=0 olduğunu biliyoruz
S_max=x+x²=1

tüm satırları doldurmamız halinde bile 5. sıradaki hedef kareye göre başlangıç değerimiz 1 oluyor , eğer 5. sıradaki bu hedef kareye 1 taş aktarılacaksa bitiş değerimiz de en az 1 olmalıdır öyleyse bunu sonlu sayıda hamle ve taşla yapmak mümkün değildir.