[MD-sorular] prens, sato ve anne

[Firat Solgun]

Eger prens satodan ciktiktan sonra herhangi bir 'sonsuz dongu'ye girmezse
eninde sonunda satosuna geri doner.

kanit:

tanim

sonsuz dongu:

Adadaki yol ve kavsaklari bir cizge gibi dusunelim, yollar cizgenin
kenarlarini, kavsaklar ise dugumlerini olustursun. Sonsuz donguden kastim
prensimizin icinde bir saga bir sola sonsuza dek dolasacagi bir kavsaklar ve
yollar kumesidir. Bu tek bir cokgen olabilecegi gibi, bir kenari ortak iki
cokgen de olabilir(duzlemsellik sart degilse). Cokgenin koseleri dongumuze
dahil olan kavsaklari, kenarlari ise yollari temsil eder. Cokgendeki her
koseye iki kenar bagli olacagindan adamizdaki duruma uygun olmasi icin
ucuncu kenarlari da eklemeliyiz(bu kenarlar sonsuz donguye ait degil adaya
ait ve iki cokgenli durumda ortak kenarin koselerinin uc kenari zaten
vardir). Bunu yapmak icin cokgenden herhangi bir koseyi secip keyfi olarak
ucuncu kenari cokgenin icine ya da disina dogru cizebiliriz. Diyelim ki
iceri dogru cizdik. Bu koseye komsu diger iki kosenin kenarlari disari dogru
olmalidir ki dongumuz sonsuz donguye benzesin. Bu kural diger koseler icin
de gecerli. Sonucta prensimiz bu donguye girecekse bir saga bir sola donerek
dolasacak ve amacimiz onu bu dongude sonsuza dek dolastirmak(en azindan
annesi bulana kadar). Ilk durumdaki sonsuz dongunun kose ve kenar sayisi
cift, ortak kenara sahip iki cokgenden olusanin ise kose sayisi cift, kenar
sayisi tek olmak zorundadir(cokgenler ayri ayri tek sayida kose ve kenara
sahiptir). Bu tanima gore prens bu sonsuz dongulerden birinde ilk kavsakta
dogru yonu secerse(donme yonune gore degisir) sonsuza kadar dongude kalir,
tabii yurume kuralini degistirmezse. Tek sayida kose ve kenara sahip,
koselerinin ucuncu kenarlari yukaridaki tanima uyan ve bu ozelliklere sahip
baska bir cokgenle ortak kenari olmayan cokgenleri yanlizca 'dongu' olarak
adlandiralim, sonucta prens girdigi kavsaktan cikacaktir.

Eger prensimiz herhangi bir sonsuz donguye(tek cokgenden olusan) girecekse,
yukarida tanim yaparken ekledigimiz ucuncu kenarlardan birinden girecektir.
Ancak saga donerek girerse bir sonraki kavsakta sola donerek donguden
cikacaktir, benzer sekilde sola donerek girerse bir sonraki kavsakta saga
donerek donguden cikacaktir(kolayca dogrulayabilirsiniz). Eger sonsuz dongu
tek ortak kenarli iki cokgenden olusuyorsa, ortak kenarin bagli oldugu
koselere komsu koselerden girmek istenirse yine dongu disina cikilir ancak
bu durumda bir yonde ucuncu kavsakta donguden cikilir, ikinci kavsakta
degil. Diger koseler tek cokgenli durumla aynidir. Sonuc olarak prensimiz
adada var olan sonsuz dongulerden hicbirine giremeyecektir. Tabii sato
sonsuz bir dongu uzerindeyse prensimiz bu donguden hic cikmayabilir,
cikmasin ne guzel sato etrafinda tur atar durur, tabii ilk kavsakta 'dogru'
yone donerse!

Yukarida prensimizin herhangi sonsuz bir donguye giremeyecegini kanitladik.
Adadaki yollara isim verelim: a, b, c... Ve prensimizin gectigi yollari
sirasiyla yazalim. Ornek: acdfoazde... Bu yazilista ayni harf ikiden fazla
kere yer alamaz aksi taktirde sonsuz donguye girmis demektir, kanitimizla
celisir. Satonun sonsuz dongu uzerinde olmadigini varsayiyoruz, sonsuz dongu
uzerindeyse prensin ilk kavsakta sonsuz donguden ciktigini varsayiyoruz,
aksi takdirde zaten kanitlayacak bir sey yoktur. Sonlu sayida yol oldugu
icin tum yollar bu yazilista belirecektir(prens yorulmazsa) ve elbet sato o
yollardan birinin uzerindedir.

Bir de, yukaridaki iddialar iki kavsak arasinda en fazla bir yol varsa
dogru. Aksi takdirde prens satosuna donemeyebilir.
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20070209/10eced37/attachment.htm