[MD-sorular] prens, sato ve anne

[Firat Solgun]

Kimsenin yanıt vermediğine bakılırsa önceki mesajım çok okunaksız olmuş.
Oysa ben bazı hatalarımı buldum. Aşağıda kanıtımın gözden geçirilmiş ve daha
okunaklı(umarım) halini yolluyorum. Ancak kanıtın temelindeki düşünce yine
aynı.

Çizgedeki noktaları(kavşaklar) a, b, c, ... olarak adlandıralım ve prensin
yolculuğunu, geçtiği noktaları sırasıyla yazarak kaydedelim. Prensin
şatosuna geri dönse bile tekrar bir sağ, bir sol kuralına uyarak gezintiye
çıktığını varsayalım. Bu durumda prensin kaydettiğimiz yolculuğu noktaların
adlarından oluşan bir dizidir. Bu diziyi, noktaların sırasını bozmadan üçlü
parçalara böldüğümüzü düşünelim. Örneğin dizimiz a c d g z t u v m ...
şeklinde gidiyorsa, üçlü parçalar (a c d), (g z t), (u v m) ... olacaktır.
Parça sayısı sonsuz, nokta sayısı(tabi bu noktalarla oluşturulabilecek üçlü
sayısı da) sonlu olduğu için en azından bir parça sonsuz kere dizide yer
almalıdır.

Prensin gideceği bir sonraki noktayı bulunduğu nokta ve önceki iki nokta
belirler. Örneğin prens 'p' noktasında olsun ve önceki iki nokta da 'm' ve
'n' olsun. Prensin yolculuk dizisinde ... m n p ... şeklinde bir kısım
vardır. 'm' ve 'p' noktaları, prensin 'n' noktasında hangi yöne döndüğünü
belirledikleri için dolaylı olarak 'p' noktasında da hangi yöne döneceğini
belirlerler(prens bir sağ bir sola döndüğü için). Prensin p'den sonra
gitmesi gereken nokta 'r' olsun. Aynı kuralı (n p r) üçlüsüne uygularsak
prensin r'den sonra hangi noktaya gideceğini buluruz. Tümevarımla prensin
tüm yolculuğunu bulabiliriz. İlk paragrafta en az bir üçlünün yolculuk
dizisinde sonsuz kere yer alacağını kanıtlamıştık. Bu paragraftaki
düşüncelerimizi uygularsak, dizinin bir yerden sonra kendini tekrar ettiği
sonucunu çıkarırız. Çünkü aynı iki üçlüden sonra takip edilen yol aynıdır.

3. paragaraf için not: 'döngü' kelimesi önceki paragrafta bahsedilen bir
üçlüyle başlayan ve bir sonraki aynı üçlüde biten tekrar eden yolu belirtmek
için kullanmıştır.

Yolculuk dizisinin kendini tekrar etmesi demek prensin bir döngüde dönüp
durması demektir. Prens bu döngüye sonradan girmiş de olabilir, hep döngü
içinde kalmış da olabilir. Eğer sonradan girmişse sorun var demektir çünkü
şato bu döngü üzerinde olmayabilir. Ancak ne mutlu bize ki prens böyle bir
döngüye sonradan giremez. Neden öyle olduğunu görmek için herhangi bir
döngüde yer alan bir noktayı ele alalım ve 'a' olarak adlandıralım. Döngü
içinde bulunan ve 'a'ya komşu olan noktalar ise 'b' ve 'c' olsun. 'a'
noktasının döngüye dahil olmayan üçüncü komşusunu ise 'd' olarak
adlandıralım. Bir döngü iki yönde dönülebilir. b a c sırası saat yönünde
dönüşü c a b sırası tersi yönde dönüşü göstersin. Döngüye girmek için
öncelikle 'd'den 'a'ya geçmeliyiz. Saat yönünde döneceksek a'dan da c'ye
geçeceğiz. Asıl döngüdeki b a c sırasının a noktasında sağa dönüşe karşılık
geldiğini varsayarsak, d a c sırası sola dönüşe karşılık gelecektir. İlk
durumda bir sonraki nokta c'den sola dönmemiz gerekirken, döngüye d'den
girdiğimiz ikinci durumda c'den sağa dönmemiz gerekecek ve döngüden çıkmış
olacağız. Aynı durum saat yönünün tersine döngüye girmeye çalışırsak da
oluşacak. Bu nedenle prens herhangi bir döngüye sonradan girmiş olamaz.
Ancak ikinci paragrafta yolculuk dizisinin kendisini bir yerden sonra tekrar
etmesi gerektiğini kanıtladık, yani prens eninde sonunda bir döngüde
olmalıdır. Demek ki başından beri bir döngüdedir. Yani şato zaten bir döngü
üzerindedir ve prens istese de istemese de o döngüyü takip edip şatosuna
geri dönebilecektir.
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20070211/27dfd6cd/attachment.htm