$4\times 20$lik bir santranç tahtasında at'ın bütün noktaları gezebileceği bir rota var mıdır?

0 beğenilme 0 beğenilmeme
157 kez görüntülendi
27, Ocak, 2015 Serbest kategorisinde Safak Ozden (3,211 puan) tarafından  soruldu
Geçtiği bir noktadan bir daha geçebilir mi? Buna izin var mı?

3 Cevaplar

1 beğenilme 1 beğenilmeme

Hayır mümkün değil, shwenk teoremine göre. Teorem ise şöyle bir satranç tahtası üzerinde atın tüm noktaları izleyebileceği bir yol mümkündür aşağıdaki üç koşuldan biri  olmadığı sürece. Bu koşullar ise  $m\times n$ satranç tahtasında $n\geq m$ olmak üzere,

1. m ve n her ikiside tek ise

2. m 3 iken n 4,6, ya da 8 ise

3.  m 1,2 ya da 4 iken 

yukarıdaki üç durum haricinde atın tüm noktaları gezebileceği bir rotanın mümkün olduğunu söyler Shwenk teoremi

9, Şubat, 2015 yavuzkiremici (1,741 puan) tarafından  cevaplandı
9, Şubat, 2015 yavuzkiremici tarafından düzenlendi

Which Rectangular Chessboards Have a Knight's Tour? Author(s): Allen J. Schwenk Source: Mathematics Magazine, Vol. 64, No. 5 (Dec., 1991), pp. 325-332 Published by: Mathematical Association of America 

Şu adreste var:

http://www.mimuw.edu.pl/~rytter/TEACHING/ALCOMB/schwenk.pdf

Alıntılanan teoreme göre yok gibi gözüküyor. Zaten yok da!

Bu arada soru olimpiyat sorusu olarak sorulmuş bir soru.

1 beğenilme 0 beğenilmeme

Olimpiyat kategorisinde olduğu için genel bir teoreme referans vermek yerine doğrudan bir çözüm göstermek gerekebilir belki.


Diyelim ki böyle bir rota olsun ve boyalı olmayan bir tahta kullanıyor olalım.


Santranç tahtamız $4$ tane $20$şer kareden oluşan üstüste konmuş doğru parçalarıdır. Bu doğru parçalarını iki ayrı gruba ayıralım:


$A$ grubu: En alttaki ve en üstteki iki parçadaki kareler.

$B$ grubu: Ortada bulunan iki parçadaki kareler.


Birinci gözlem: At gezintisi sırasında $A$ grubundaki bir kareye geldiği zaman mecburen $B$ grubundaki bir kareye gitmek zorundadır. Çünkü $A$ grubundaki kareler kendisiyle ya aynı sıradadır ya da $3$ sıra aşağıdadır/yukarıdadır.

İkinci gözlem: At her noktadan bir kere geçeceği için, yukarıdaki gözlem nedeniyle (yani $A$'ya her gelişinde $B$'ye dönmek zorunda), at gezintisi sırasında $B$ grubundaki bir kareden mecburen $A$ grubundaki bir kareye geçmek zorunda.

Bu iki gözlem bize şunu söylemekte. At gezintisinin koordinatlarını bilmesek de gruplar arasında şu iki biçimden birisinden gezinmek sorunda:


$$A-B-A-\cdots -A-B-A-B$$

veya

$$B-A-B-\cdots -B-A-B-A$$


Diyelim ki ilk durumdaki gibi olsun. Buradan şu sonuç çıkar: Eğer atın tek adımlarında bastığı noktaları siyaha, çift adımlarında bastığı noktaları beyaz ile boyarsak boyalı olmayan tahta sonunda $A$ bölgesi siyaha, $B$ bölgesi beyaza boyanmış bir hale gelecektir.


Şimdi ikinci kısma geçelim:


Teorem: Satranç tahtasında at, çıktığı bir noktaya bitişik bir noktaya sadece tek sayıda hamle yaparak gelebilir.

Teoremimizin şöyle bir ek sonucu bulunmakta: Atımız satranç tahtasını dolaşıyorsa ve yukarıdaki biçimde adımlarında boyanın rengini değiştirerek boyama yapıyorsa sonuçta tahtayı yanyana noktaların rengi farklı olacak şekilde boyamak zorunda. Yani yukarıdaki gibi $A$ bölgesi siyah $B$ bölgesi beyaz olacak biçimde bir boyama yapamaz. Yani. Yanisi çelişki!


Teoremin ispatı: Atın bütün hareketlerini düzlemde $(1,2),(2,1),(1,-2),(-2,1)$ vektörlerin tamsayı katsayılı kombinasyonları biçiminde yazabiliriz (Elbette daha az sayıda vektörle de bunu yapabiliriz. Ama bu dört vektör ve bunların $-$ işaretlileri bize atın tek hamlede yapabileceği bütün hareketleri veriyor, bu açıdan daha kullanışlılar). Diyelim ki atımız belirli bir yol yürüyerek $(0,0)$ noktasından $(0,1)$ noktasına gelmiş olsun. Bu demektir ki elimizde

$$  a(1,2)+b(2,1)+c(1,-2)+d(-2,1)=(0,1)$$

denklemi vardır. Ufak bir hesaplamayla $a+b+c+d$ toplamının tek bir sayıya eşit olması gerektiği bulunabilir. 


Not: En son teoremde neden dört vektör yerine sekiz vektör (alınan vektörlere ek olarak onların eksi işaretlerinin alınmadığının da açıklamansı gerek. Ama bunun nedeni açık (Neden?)) 


9, Şubat, 2015 Safak Ozden (3,211 puan) tarafından  cevaplandı

Teşekkürler güzel çözüm için

rica ederim.


bu arada ispattan görülebileceği gibi aslında geçtiği bir noktadan bir daha geçmeyecek şartını koymaya da gerek yok. geçtiği noktadan istediği sayıda geçebilme hakkı olsa da, dolaşamaz.

A'dan B'ye geçmek zorunda olduğu doğru ama B'den A'ya geçmek zorunda değildir.

AAAAAAAAAAAAAAAAAAAA

BBBBBBBBBBBBBBBBBBBB

OBBBBBBBBBBBBBBBBBBB 

AAAAAAAAAAAAAAAAAAAA

---------------------------------------------

AAAAAAAAAAAAAAAAAAAA

BBOBBBBBBBBBBBBBBBBB

BBBBBBBBBBBBBBBBBBBB 

AAAAAAAAAAAAAAAAAAAA

0 beğenilme 0 beğenilmeme

Bir at'ın yan kareye (ve onun da yanındakine) geçebilmesi için 3x3'lük bir alan yeterli olduğundan 4x20'liği tek tek dolaşabilir. Ama belki de ben çok basit düşünüyorumdur. (-_-)

8, Kasım, 2015 WhiteWolf (491 puan) tarafından  cevaplandı

Diğer yanıtta neden dolaşamayacağı anlatılıyor.

Sanırım kural olarak bir bastığı kareyi tekrar kullanmıyorsunuz. Ben o açıdan düşünmemiştim. Yoksa 4x4 içinde her birini tek tek dolaşabiliriz.

Hayır, atın geçtiği kareden yeniden geçmeye izni olsa dahi dolaşamaz.

Diyelim ki aynı kareden birden fazla kez geçebiliyoruz. Çözüm adımlarım...

Adım1>> 3x3'lük alanda ortadaki kare hariç tüm kareler dolaşılabilir. (Tüm köşe ve kenarları)

Adım2>> 4x20'lik alan içerisinde çıkarabileceğimiz bütün 3x3'lük alanları düşünelim. (Alanlar birbirini istediği gibi kesebilir)

Adım3>> 4x20'lik alan üzerindeki her kare muhakkak bir 3x3'lük alanın köşesine ya da kenarına denk gelir.

Adım4>> Bir 3x3'lük düşündüğümüz alandan diğer bütün 3x3'lük alanlara ulaşılabilir.

Yanlışınızı bulmak için okumayacağım. Önce yukarıdaki ispatı okuyun bence.

...