Rahip Kirkman'ın Kız Öğrenci Problemi: İkişerli Gruplar Halinde Birden Fazla Defa Yan Yana Gelmek İstemeyen 15 Öğrenci Nasıl Sıralanabilir?

Lady's and Gentleman's Diary, Company of Stationers tarafından 1841 ile 1871 arasında yıllık olarak yayımlanan ve çoğunlukla okuyucularının ortaya çıkardığı problemlerden ve sonraki ciltlerde verilen çözümlerden oluşan, aynı zamanda kelime bulmacaları ve şiir de içeren bir matematik dergisiydi. Derginin genel merkezi Londra'da bulunuyordu.

Tarihler 1850’yi gösterdiğinde, kilisede bir rahip olan Thomas Kirkman, Lady's and Gentleman's Diary dergisine, basitmiş gibi duran bir problem gönderdi. Problem şöyleydi:

Bir okuldaki on beş kız öğrenci, arka arkaya yedi gün boyunca üç kişilik gruplar halinde yan yana yürüyecektir. Kız öğrencilerden ikisi yan yana iki kez yürümeyecek şekilde nasıl sıralayabiliriz?

Bu problemi bir kez okuyunca çok da zor olmadığı anlaşılıyor; ancak soru, görünenden çok daha zor. Çünkü deneyecek olursanı, henüz 3. ya da 4. günde kafaların karıştığı ve işin içinden çıkılamaz bir hal aldığını görmeniz olasıdır.

Problemin hem kısa olması hem de çok uğraş gerektirmesi, problemi popüler yapmıştı. Problem elbette eğlenceli; ancak bunun gibi problem türleri, bu tarz dergilerde oldukça fazla yayımlanmıştır, dolayısıyla burada sıra dışı bir durum yok. Ama bu problemi diğerlerinden ayıran, Kombinatoryal Tasarım Teorisi adı verilen bir matematik alanını başlatmış olmakla kalmayıp, o zamandan beri deney tasarımında, hata düzeltme kodlarında, kriptografide ve hatta piyangoda uygulama alanı bulmuş olmasıdır.

Peki bu problemin çözümü var mı? Varsa, bu ve buna benzer problemlerin genel bir çözümü var mı? Birlikte bakalım.

Problemin Çözümü

Elbette amatör veya profesyonel matematikçiler bu soruyla pek çok kez uğraştılar ve bunun sonucunda birden fazla çözüm bulmayı başardılar. Bu birden fazla çözüm belki normal geliyor olabilir; ancak sorunun birden fazla cevabı olduğunu hesaba katarsak, hem çözümler farklı hem sonuçlar farklı çıkabiliyor. Biz bu çözümleri size işin denklem ve üst düzey hesaplama kısmından bahsetmeden anlatmaya çalışacağız.

Çözüm 1

Problemi ilk okuduğunuzda kalem kağıt çıkarıp haftanın günlerine ve kişilere harfler vererek (ya da numaralandırarak) işe koyulmuşsunuzdur. Kesinlikle tam olarak biz de böyle yapmaya çalışacağız.

Bir hafta boyunca üçerli gruplar halinde yürümeleri gerekiyorsa bir günde toplam grubun 5 olacağı aşikardır. Ve kişilerin isimlerinin A, B, C, D, E, F, G, H, I, J, K, L, M, N ve O olduğunu düşünelim. Bu sorunu çözmek için biraz lise düzeyinde matematiğe ihtiyaç duyuyoruz. Birkaç kişinin yan yana gelerek oluşturduğu dizilimler olsaydı rahatlıkla bulabilirdik ancak 15 öğrenci olunca iş biraz zorlaşıyor.

Şimdi, 15 kişinin bir günde yan yana sıralanması için $15!$ seçenek vardır. Bu sayı oldukça yüksek olmasına rağmen bunun bir hafta süreceğini hesaba katarsak $(15!{)}^7$ olarak buluruz. Bu, çok çok büyük bir sayıdır; o yüzden bazı koşullar getirebiliriz. Koşullardan ilki, pazar gününü sabitlemek olacaktır.

Elbette bu bize biraz yardımcı oldu; ancak hâlâ $(15!{)}^6$ seçenek var. Biraz daha zihnimizi yorarsak başka kısıtlamalar getirebiliriz. Şöyle ki; diğer günler ilk 3 grubun ilk üyelerini sabit tutabiliriz:

Bu durum sonucunda kişi sayısının seçilme durumunu 12'ye indirmiş oluyoruz böylelikle yeni olası yollar $(12!{)}^6$'dır. Evet, hâlâ yeterince büyük bir sayı ile karşı karşıyayız; bu öyle büyük bir sayı ki, evrenin yaşının yaklaşık 28 trilyon katıdır!

Peki, daha fazlasını yapmamız gerekiyor. Bunun için belirli kısıtlamalara devam ediyoruz; ancak bu kısıtlamaları anlatabilmek için tablonun tamamını doldurmalıyız. Doldurma işlemi, elbette şu anda anlattığımız yöntemin sonucunda oluşarak yapılmıştır, dolayısıyla bunu aslında baştan bilmeniz mümkün değildir:

Tablonun tamamını gördüğümüzde karşımıza çıkan 3 yeni kuralı şöyle derleyebiliriz:

• En soldaki sütundan aşağı inildiğinde değerler artar (yeşil renkli harfler).
• İlk sıranın ortasındaki harf her gün artar (kırmızı renkli harfler).

• Her satırda soldan sağa değerler artar. Yeşil harfler sarı harflerden daha düşük sarı harfler mavi harflerden daha düşük diyebiliriz. İlk satır hariç, çünkü ilk satırda sarı harf renklendirmesi yapmadık; halihazırda kırmızı oldukları için, onları şu şekilde sıralayabiliriz: Yeşil harfler kırmızı harflerden, kırmızı harfler mavi harflerden daha düşüktür.

Bu kısıtlamalar elbette işimizi kolaylaştırmış oldu; ancak tamamıyla bizim yapabileceğimiz bir tablo oluşturmak çok güç olduğu için, sadece bu kısıtlamalardan yararlanarak basit bir bilgisayarda yalnızca birkaç saniye süren, farklı konumlarda harflerin (yani kişilerin) 200 milyondan az deneme içeren bir geri izleme çözümü bulabiliriz. İşte bu kısıtlamalardan yararlanarak, bilgisayar yardımıyla geri izleme çözümlerinden bir tanesi, yukarıdaki tablodur.

Problemi ilginç kılan şeylerden bir tanesi tek bir çözümünün olmayışı demiştik, şimdi başka bir çözüme göz atalım.

Çözüm 2

15 kişiyi, sayılar yardımıyla isimlendirelim. 1, 2, 3, 4, ... ,15 gibi. Şimdi iç içe iki çemberi anımsatan numaralar ve ortak bir merkezlerinin olduğunu düşünelim. Bu numaralar iç içe geçmiş çember üzerindeki noktalara belirli şartlar yardımıyla yerleştirilecektir.

• Dış çemberde bulunan 7 nokta, saat yönünün tersi (yeşil ok) şekilde sıralanmış olsun ve bu noktalara 1'den 7'ye kadar en üst noktadan yeşil ok yönünde sıralanmış olsun.
• İç çemberdeki 7 nokta ise devam eden 7 tane sayıyı (8, 9, ..., 14) yine yeşil ok yönünde sıralanmış olsun.
• Son olarak çemberin merkezi son sayı olan 15 olsun.

Bu veriler sonucunda, soruya cevap olabilmesi için herhangi üç noktanın (üç kişinin yan yana olması) birleşmesi gerekiyor. Bu birleşmeyi öyle yapmamız gerekiyor ki hiçbiri birbiriyle çakışmasın. Şuna dikkat ediniz: Çakışmadan kastımız, kırmızı çizgilerin üst üste gelmesi değildir; başka günlerde aynı bağlanmanın olmasıdır. Mesela şekilde pazar günü olarak 1, 2 ve 4 numaralı kişiler dizilmiş, başka gün tekrardan bu dizilimin gerçekleşmemiş olmasıdır.

Bu bağlama şeklini elde edebiliriz ama elbette bunu da bilgisayar yardımıyla elde etmiş oluyoruz ancak bu yöntem sadece bir günlüktür. Bu şeklin tamamını yeşil ok yönünde birer adım ilerletirsek haftanın diğer günlerini de elde etmiş oluruz.

7 gün boyunca hepsinin birlikte oluşturacağı şekil ise şöyledir.

Prof. Dr. Reinhard Laue

Ve aynı problemin Çözüm 1'deki sonucu ile şu anda çözdüğümüz sonuç farklı olmasına rağmen, doğru olmuş oluyor. Bu durumu tablo halinde gösterelim.

Burada gördükleriniz, bu problemin bugüne kadar geliştirilmiş 7 cevabından sadece ikisidir. Hatta buna benzer başka problemler de vardır; ancak matematikçilerin aklına takılan soru, elbette bu soruların neden genel bir çözümünün olmayışıdır.

Görüldüğü üzere, üstünden 170 yıl geçmesine rağmen bu ve buna benzer problemlerin sabit bir çözümünün olmadığı görülüyor. Belki de bu problemleri popüler tutan şey, tek bir çözümünün ve tek bir cevabının olmamasıdır.

Yazımızı, bir dörtlük ile sonlandırmak istiyoruz. Bu dörtlük, Lady's and Gentleman's Diary dergisine bu problemi ele alan bir kadın (veya derginin adına ithafen, bir "hanımefendi") tarafından yazılmıştır:

Büyük şöhretli mürebbiye,

Kasabanın yakınlarında gezen,

On beş genç hanım vardı,

Yeşil çayırlar boyunca.