Rahip Kirkman'ın Kız Öğrenci Problemi: İkişerli Gruplar Halinde Birden Fazla Defa Yan Yana Gelmek İstemeyen 15 Öğrenci Nasıl Sıralanabilir?
Özgün Nedir?
Bu yazı, Evrim Ağacı'na ait, özgün bir içeriktir. Konu akışı, anlatım ve detaylar, Evrim Ağacı yazarı/yazarları tarafından hazırlanmış ve/veya derlenmiştir. Bu içerik için kullanılan kaynaklar, yazının sonunda gösterilmiştir. Bu içerik, diğer tüm içeriklerimiz gibi, İçerik Kullanım İzinleri'ne tabidir.
Özet
Lady's and gentleman's diary dergisinde yayınlanan bir matematik problemi daha sonraki yıllarda hem profesyonel hem de amatör matematikçileri etkilemiş aynı zamanda Kombinatoryal tasarım teorisi adı verilen bir matematik alanının başlamasına sebep olmuştur. İşte o problem: "Bir okuldaki on beş genç bayan, arka arkaya yedi gün boyunca üç kişilik gruplar halinde yan yana yürür; hiçbirinin iki kez yan yana yürümemesi için bunları günlük olarak nasıl düzenlemek gerekir?" Bu yazıda bu problemin çözüm yöntemlerine değiniliyor.
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.
Evrim Ağacı'nın çalışmalarına Kreosus, Patreon veya YouTube üzerinden maddi destekte bulunarak hem Türkiye'de bilim anlatıcılığının gelişmesine katkı sağlayabilirsiniz, hem de site ve uygulamamızı reklamsız olarak deneyimleyebilirsiniz. Reklamsız deneyim, Evrim Ağacı'nda çeşitli kısımlarda gösterilen Google reklamlarını ve destek çağrılarını görmediğiniz, daha temiz bir site deneyimi sunmaktadır.Kreosus
Kreosus'ta her 10₺'lik destek, 1 aylık reklamsız deneyime karşılık geliyor. Bu sayede, tek seferlik destekçilerimiz de, aylık destekçilerimiz de toplam destekleriyle doğru orantılı bir süre boyunca reklamsız deneyim elde edebiliyorlar.
Kreosus destekçilerimizin reklamsız deneyimi, destek olmaya başladıkları anda devreye girmektedir ve ek bir işleme gerek yoktur.Patreon
Patreon destekçilerimiz, destek miktarından bağımsız olarak, Evrim Ağacı'na destek oldukları süre boyunca reklamsız deneyime erişmeyi sürdürebiliyorlar.
Patreon destekçilerimizin Patreon ile ilişkili e-posta hesapları, Evrim Ağacı'ndaki üyelik e-postaları ile birebir aynı olmalıdır. Patreon destekçilerimizin reklamsız deneyiminin devreye girmesi 24 saat alabilmektedir.YouTube
YouTube destekçilerimizin hepsi otomatik olarak reklamsız deneyime şimdilik erişemiyorlar ve şu anda, YouTube üzerinden her destek seviyesine reklamsız deneyim ayrıcalığını sunamamaktayız. YouTube Destek Sistemi üzerinde sunulan farklı seviyelerin açıklamalarını okuyarak, hangi ayrıcalıklara erişebileceğinizi öğrenebilirsiniz.
Eğer seçtiğiniz seviye reklamsız deneyim ayrıcalığı sunuyorsa, destek olduktan sonra YouTube tarafından gösterilecek olan bağlantıdaki formu doldurarak reklamsız deneyime erişebilirsiniz. YouTube destekçilerimizin reklamsız deneyiminin devreye girmesi, formu doldurduktan sonra 24-72 saat alabilmektedir.Diğer Platformlar
Bu 3 platform haricinde destek olan destekçilerimize ne yazık ki reklamsız deneyim ayrıcalığını sunamamaktayız. Destekleriniz sayesinde sistemlerimizi geliştirmeyi sürdürüyoruz ve umuyoruz bu ayrıcalıkları zamanla genişletebileceğiz.Giriş yapmayı unutmayın!
Reklamsız deneyim için, maddi desteğiniz ile ilişkilendirilmiş olan Evrim Ağacı hesabınıza üye girişi yapmanız gerekmektedir. Giriş yapmadığınız takdirde reklamları görmeye devam edeceksinizdir.
Şimdi, 15 kişinin bir günde yan yana sıralanması için 15!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(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(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(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.
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.
Bu içeriğimizle ilgili bir sorunuz mu var? Buraya tıklayarak sorabilirsiniz.
İlginizi Çekebilecek Sorular
- Çok yakınım olmayan kişilerin yanında heyecanlanıyorum ve geriliyorum bu durumu nasıl aşarım?
- Covıd-19 aşıları anormal kan pıhtılaşmasına (tromboz) neden olur mu?
- Turkovac aşısı güvenilir mi?
- 3
- 3
- 3
- 2
- 1
- 1
- 1
- 0
- 0
- 0
- 0
- 0
- I. Italia. (2012). The Rise Of Literary Journalism In The Eighteenth Century: Anxious Employment. ISBN: 9780415651516. Yayınevi: Routledge.
- E. W. Weisstein. Kirkman's Schoolgirl Problem. (28 Kasım 2020). Alındığı Tarih: 28 Kasım 2020. Alındığı Yer: Wolfram Alpha | Arşiv Bağlantısı
- R. Laue. (, 2020). The Schoolgirl Problem of Reverend Kirkman (1806-1895).
- A. Hui. An Introduction To Kirkman’s Schoolgirl Problem. (28 Kasım 2020). Alındığı Tarih: 28 Kasım 2020. Alındığı Yer: Hong Kong University | Arşiv Bağlantısı
- String. Is There A Memorable Solution To Kirkman's School Girl Problem?. (24 Mart 2015). Alındığı Tarih: 28 Kasım 2020. Alındığı Yer: Stack Exchange | Arşiv Bağlantısı
- E. Klarreich. Answer To A 150-Year-Old Math Conundrum Brings More Mystery. (20 Haziran 2015). Alındığı Tarih: 28 Kasım 2020. Alındığı Yer: Wired | Arşiv Bağlantısı
Evrim Ağacı'na her ay sadece 1 kahve ısmarlayarak destek olmak ister misiniz?
Şu iki siteden birini kullanarak şimdi destek olabilirsiniz:
kreosus.com/evrimagaci | patreon.com/evrimagaci
Çıktı Bilgisi: Bu sayfa, Evrim Ağacı yazdırma aracı kullanılarak 31/07/2021 05:58:41 tarihinde oluşturulmuştur. Evrim Ağacı'ndaki içeriklerin tamamı, birden fazla editör tarafından, durmaksızın elden geçirilmekte, güncellenmekte ve geliştirilmektedir. Dolayısıyla bu çıktının alındığı tarihten sonra yapılan güncellemeleri görmek ve bu içeriğin en güncel halini okumak için lütfen şu adrese gidiniz: https://evrimagaci.org/s/9612
İçerik Kullanım İzinleri: Evrim Ağacı'ndaki yazılı içerikler orijinallerine hiçbir şekilde dokunulmadığı müddetçe izin alınmaksızın paylaşılabilir, kopyalanabilir, yapıştırılabilir, çoğaltılabilir, basılabilir, dağıtılabilir, yayılabilir, alıntılanabilir. Ancak bu içeriklerin hiçbiri izin alınmaksızın değiştirilemez ve değiştirilmiş halleri Evrim Ağacı'na aitmiş gibi sunulamaz. Benzer şekilde, içeriklerin hiçbiri, söz konusu içeriğin açıkça belirtilmiş yazarlarından ve Evrim Ağacı'ndan başkasına aitmiş gibi sunulamaz. Bu sayfa izin alınmaksızın düzenlenemez, Evrim Ağacı logosu, yazar/editör bilgileri ve içeriğin diğer kısımları izin alınmaksızın değiştirilemez veya kaldırılamaz.