Bu soruyu çözmek için nedense çizge teorisini denemekle başladım. Çizge teorisinin güzel tarafı anlaşılır ve kolay işlemlere sahip olmasıydı. Bir de problemi görsel olarak modellemek de kolaydı.
Tabii ki soruda verilenle değil de daha basit bir problemle başladım. Amacım basit bir formül bulmaktı. Bu hedefle ve yöntemle yola çıkmak bu örnekte de görüldüğü gibi bazen insanı çok erken sevindiriyor ve bir süre sonra da yarı yolda bırakabiliyor.
Önce çizge teorisiyle problemi modellemeyi denedim. Katları düğüm noktalarıyla, katlar arası geçişleri de bu noktaları birleştiren çizgilerle gösterdim. Bu durumda herhangi bir kattan başka herhangi bir noktaya tek asansörle gidebilmek, bütün noktaların birbirleriyle birer çizgiyle bağlı olması demek oldu.
Bu şekildeki N düğüm noktasına sahip bir çizgede toplam bağlantı sayısı aşağıdaki şekilde hesaplanabilir.
Birinci nokta diğer bütün noktalarla bağlantılı olacak: \(N – 1 \) bağlantı.
İkinci nokta birinci hariç kalan diğer bütün noktalarla bağlantılı olacak: \(N – 2 \) bağlantı.
Bu şekilde birinci noktadan son noktaya kadar toplarsak (son noktada bağlantı sayısı 0 olacaktır) toplam bağlantı sayısını buluruz: \(N-1 + N-2 + \dots + 1 + 0=\frac{(N-1)\cdot{N}}{2} \)
Burada en basit problem olarak sadece iki katta duran asansörleri ele aldım. Tabii bu şekilde hareket eden bir asansör çizgemizdeki tek bir bağlantıya karşılık gelecektir. Bu da N kat için gereken asansör sayısının, yukarıda bulduğumuz gibi, bağlantı sayısına eşit olduğu anlamına gelecektir.
Daha sonra üç kata giden asansörlere baktım. Toplam bağlantı sayısı aynı kalıyor tabii ki. Her asansörün bu bağlantıların kaçına karşılık geldiğine baktım. Üç kata giden asansör üç bağlantıya karşılık geliyor tabii ki. Örneğin 1., 2. ve 3. katlarda duran asansör, çizgede 12, 23 ve 31 katları arasındaki geçiş bağlantılarıyla gösterilmekte ve çizgedeki toplam bağlantı sayısını üçe bölerek gereken asansör sayısını bulabileceğimi düşündüm. Tabii bunu yapabilmek için aslında her zaman üç kat seçebileceğim varsayımını da yapmış oldum. Bu varsayım tabii ki yanlıştı. Eğer doğru olsaydı toplam bağlantı sayısının üçe bölündüğü bu formül gereken asansör sayısını bulacaktı:
\(\frac{(N-1)\cdot{N}}{6} \)
Fakat şu kısa tabloya bakılınca bazı kat sayıları için bu formülün doğru sonucu vermediğini görüyoruz.
Bunun üzerine formülde biraz daha oynadım. Örneğin tavan fonksiyonunu filan da kullandım ama her seferinde bu formülün işe yaramadığı bir örnek çıktı. Bunun üzerine formül aramaktan vazgeçip, başka ne tür kurallar bulunabilir diye aramaya başladım.
Farkettiğim basit kurallardan biri her katın asansörlerde yaklaşık olarak eşit sayıda bulunması gerektiği. Yani 10 kat varsa ve 4 katta duran 20 asansör varsa, asansörlerde her kat yaklaşık (bu durumda belki de tam) 8 kere bulunmalı.
Bir başka ilginç özellik de şöyle. Diyelim ki şöyle bir problem verilmiş. 7 katlı bir bina için 3 katta duran kaç asansör gerekmektedir? Bu probleme bir çözüm bulduğumuz an otomatik olarak 6 durakta duran aynı sayıda asansörün 14 katlı binanın bir çözümü olduğunu da buluyoruz. Daha basit bir örnekle başlayıp bu özelliğe bir bakalım.
3 katlı bir binada sadece 2 katta duran kaç asansör gereklidir?
Çözüm olarak kolayca şunu bulabiliriz:
1. asansör: 1, 2
2. asansör: 1, 3
3. asansör: 2, 3
Yukarıda her asansörün hangi katlarda durduğu yazılı. Bundan daha az asansör olamaz. Şimdi 4 durakta duran üç asansörle kaç kata gidilebileceğini bulmak için bu üç asansörü alıp her birine ikişer kat daha ekleyelim. Bu katları eklerken yapacağımız tek şey mevcut olan kat numaralarına basit problemdeki kat sayısını eklemek, yani 3.
1. asansör: 1, 2, 1 + 3 = 4, 2 + 3 = 5 (İlk iki kat önceki sorunun çözümüydü ve bina 3 katlıydı)
2. asansör: 1, 3, 1 + 3 = 4, 3 + 3 = 6
3. asansör: 2, 3, 2 + 3 = 5, 3 + 3 = 6
Peki bunun bir çözüm olduğunu nereden biliyoruz? Bunu göstermek daha kolay. Asansörlerin kat listelerindeki sol yarının 1. kattan N. kata kadar problemi çözdüğünü biliyoruz. Yani k numaralı kattayken, k numaralı katın bulunduğu asansörleri seçtiğimizde 1. kattan N. kata kadar gidebiliyorduk. Bu da bu seçilmiş asansörlerin kat listesinin sol tarafında 1’den N’ye kadar her katın bulunduğu anlamına geliyor. Biz bu kat listelerinin sağ yarısını oluştururken soldaki kat numaralarına N sayısını ekledik. Yani seçtiğimiz asansörlerin sağ tarafındaki numaralar da N+1’den 2N’ye kadar gidiyor. Dolayısıyle aynı asansörlerle 1’den 2N’ye kadar her kata ulaşabiliyoruz.
Yukarıdaki basit örnekle bunu deneyelim. Birinci katta olduğumuzu düşünelim. Bu durumda içinde 1 bulunan asansörleri seçiyoruz. Bunlar da 1. ve 2. asansörler.
1. asansör: 1, 2, 4, 5
2. asansör: 1, 3, 4, 6
Kat numaralarının sol yarısında 1, 2 ve 3 numaralı katlar var ve birinci kat ikisinde de ortak. Yani birinci kattan diğer katlara gidebiliyorduk. Sağ yarıdaki katları üretirken de bu sayılara 3 ekledik, yani sol taraf birden üçe giderken, sağ taraf da dörtten altıya kadar gidiyor. Birinci kat bu iki asansörde ortak olduğundan bu iki asansörle birinci kattan altıncı kata kadar asansör değiştirmeden gidebiliriz. Aynı mantığı diğer katlar için de uygulayabiliriz, bu sırada yapacağımız tek şey belki farklı katlar için farklı asansör gruplarını seçmek olacak.
Peki bu yöntem daha büyük soru için optimum çözümü mü veriyor? Bunu şimdilik bilmiyorum.
Şimdi temel sorumuza dönelim. 7 asansörümüz var ve her biri 6 katta duruyor. Bunu çözmek için biraz önce anlattığım yöntemi deneyelim. Her biri 3 katta duran 7 asansör sorusunu alalım. Biraz deneme yanılma yaparak şöyle bir çözüm bulabiliriz.
- asansör: 1, 2, 3
- asansör: 1, 4, 5
- asansör: 1, 6, 7
- asansör: 2, 4, 6
- asansör: 2, 5, 7
- asansör: 3, 4, 7
- asansör: 3, 5, 6
Yani bu kadar asansörle 7 katlı bir binayı çözebiliyoruz. O zaman yukarıdaki yöntemle durak sayısını ikiye katlarsak kat sayısını da ikiye katlayabiliriz.
- asansör: 1, 2, 3, 8, 9, 10
- asansör: 1, 4, 5, 8, 11, 12
- asansör: 1, 6, 7, 8, 13, 14
- asansör: 2, 4, 6, 9, 11, 13
- asansör: 2, 5, 7, 9, 12, 14
- asansör: 3, 4, 7, 10, 11, 14
- asansör: 3, 5, 6, 10, 12, 13
Çizge teorisiyle sorunu çözemedim ama orada bulduğum formüllerle asansör sayısıyla ilgili alt ve üst sınırları bulabiliriz. Internette bu problemlerin genel çözümünü ve formüllerini de aradım ama henüz bulabildiğim şeyler çok kısıtlı. Bu soru başka bir şekilde Kobon Fujimura’nın The Tokyo Puzzles kitabında çözülmüş ama kitaba henüz ulaşamadım. Bir de kodlama teorisinde de bu sorunun çözümü varmış diye okudum ama henüz onu araştıramadım. Yeni şeyler öğrendiğimde bunları da yazacağım.