Josephus problemi Milattan Sonra 1. Yüzyılda yaşandığı rivayet edilen kanlı bir olaya bağlanır. Roma imparatoru Nero Yahudi ayaklanmasının bastırılması için general Vespasian’ı görevlendirmiştir. Vespasian’ın emrindeki askerler ünlü Yahudi tarihçisi Flavius Josephus ve 40 arkadaşını bir mağarada esir alırlar. Vespasian esirlerin çember şeklinde dizilmelerini ve her kişiye belli bir yön takip edilerek 1’den 41’e kadar numara verilmesini ister. 1’inciden başlayarak 3’e kadar sayıp 3’üncü kişinin öldürülmesini, daha sonra 4’ten başlayarak üçe kadar sayıp 6’ıncının ve böylece sadece iki esir kalıncaya dek her üç kişiden birinin öldürülmesini emreder. Esirler 3, 6, 9 gibi numaraları almak istemezler ama Vespasian tarafından bu numaralar zorla verilir. Bu arada Josephus hızla yaptığı hesaplamayla sona kalacak olan iki numarayı bularak kendisinin ve yakın arkadaşının hayatını kurtarır. Sonrasında Vespasian’ın Roma imparatoru olacağı kehanetinde bulunması sayesinde bağışlanı.
Hikâyeden öğrendiğimize göre Josephus’un çok kısa bir sürede yaptığı hesapla ulaştığı sona kalan o iki sayının 16 ve 31 olduğunu bulmak oldukça kolay. Bu konuya yazının sonunda tekrar döneceğiz.
Bu problemin genel çözümü nedir? Kişi sayısı n alınırsa genel ve kapalı bir formül bulunabilir mi? Yazının bundan sonraki bölümünde bu soruları yanıtlayacağız.
Graham, Knuth, ve Patashnik, Concrete Mathematics adıyla yayımladıkları kitapta Josephus problemini iki kişiden birinin elendiği n kişi arasında oynanan bir oyun olarak ele almışlar. Bu güzel çözümü inceleyelim.
Problem. 1’den n’ye kadar numaralandırılmış n kişi sırayla (1,2,3…n) bir çember etrafında sıralanıyorlar. 1 numaralı kişiden başlayıp belli bir yön takip edilerek sayılıyor, her iki kişiden biri eleniyor. Bu şekilde n-1 kişi eleninceye dek devam ediliyor. Oyunu kazanan oyuncunun numarası kaçtır?
Çözüm. n sayma sayısı için oyunu kazanan kişinin numarasını J(n) ile gösterelim. Oyuncu sayısını çift ve tek olarak iki ayrı durumda inceleyeceğiz. Eğer oyun 2n kişiyle başlarsa ilk turun sonunda çember etrafında sadece tek numaralı oyuncular kalacak (Şekil 1) ve bu andan itibaren oyun başlangıçtaki gibi oynanacaktır.
İlk oyuncunun numarası yine 1, ama ikinci oyuncu önceki turun 3 numaralı oyuncusu olacak. Bu şekilde devam edilirse öncekinin 5 numarası sonrakinin 3 numarası, öncekinin 7 numaralısı sonrakinin 5 numaralısı olur. Bu numaraları önceki-sonraki diye yazarsak 1-1, 3-2, 5-3, 7-4, … ikililerini genel terimle ifade edersek önceki numaralı 2k-1, sonrakileri de k ile gösterebiliriz. O halde ikinci turdaki n kişiyle oynanan oyunu k numaralı oyuncu kazanıyorsa, ilk turda 2n kişiyle oynanan oyunu 2k-1 numaralı oyuncu kazanır. Buradan, J(n) kazanan oyuncunun numarası olduğundan, n≥1 için
J(2n)=2J(n)-1 (1)
eşitliği yazılabilir.
Şimdi de oyunun 2n+1 kişiyle oynandığını varsayalım. Bu durumda, ilk turun sonunda sırasıyla 2,4,6,… ,2n ve 1 numaralı oyuncular elenecek, çember etrafında tek numaralı oyuncular kalacak (Şekil – 2) ve bu andan itibaren oyun başlangıçtaki gibi oynanacaktır.
İlk oyuncunun numarası 3, ikinci oyuncuysa önceki turun 5 numaralı oyuncusu olacak. Bu şekilde devam edilirse öncekinin 7 numarası sonrakinin 3 numarası, öncekinin 9 numaralısı sonrakinin 4 numaralısı olur. Bu numaraları önceki-sonraki diye yazarsak 3-1, 5-2, 7-3, 9-4, … ikililerini genel terimle ifade edersek önceki numaralı 2k+1, sonrakileri de k ile gösterebiliriz. O halde ikinci turdaki n kişiyle oynanan oyunu k numaralı oyuncu kazanıyorsa, ilk turda 2n kişiyle oynanan oyunu 2k+1 numaralı oyuncu kazanır. Buradan, J(n) kazanan oyuncunun numarası olduğundan, n≥1 için
J(2n+1)=2J(n)+1 (2)
eşitliği yazılabilir.
(1) ve (2) eşitlikleri ile oyundaki tüm durumları tanımlayabiliriz:
J(1)=1,
J(2n)=2J(n)-1,
J(2n+1)=2J(n)+1. (3)
Bu formüllerden yararlanarak J(n) değerleri hesaplanabilir. Örneğin
J(16)=2J(8)-1
J(16) =2(2J(4)-1)-1=1
olarak bulunur. Ama daha büyük sayılar için bu yöntem hiç pratik değil, genel ve kapalı bir formül bulabilmek için n’nin ilk 16 değeri için J(n) değerlerinin yer aldığı aşağıdaki tabloya bakalım:
Tablodaki sayıları incelersek dikey çizgilerle ayrılmış bölmelerde n sayısı 2^k’den 2^(k+1)-1’e kadar değerler alırken J, 1,3,5,… , 2^(k+1)-1 değerlerini alıyor. Örneğin dikey çizgilerle ayrılmış bölmelerin ikincisine (soldan sağa sayarsak) ilk n değeri olan 4’ü 2^2+0 olarak yazarsak J(4)=2×0+1 olur. Benzer şekilde aynı bölümdeki diğer n değerlerine karşılık gelen J’ler aşağıdaki gibi yazılabilir:
J(5)=J(2^2+1)=2×1+1=3,
J(6)=J(2^2+2)=2×2+1=5,
J(7)=J(2^2+3)=2×3+1=7.
Dikey çizgilerle ayrılan üçüncü bölümdeki n değerleri bu kez 2’nin 3’üncü kuvvetinin sırasıyla 0,1,2,3,4,5,6,7 fazlası olurken J de sırasıyla
J(8)=J(2^3+0)=2×0+1=1,
J(9)=J(2^3+1)=2×1+1=3,
J(10)=J(2^3+2)=2×2+1=5,
J(11)=J(2^3+3)=2×3+1=7,
J(12)=J(2^3+4)=2×4+1=9,
değerlerini alıyor. Benzer şekilde J(13), J(14), J(15) hesaplanabilir.
Artık, yukarıdaki eşitliklerden yararlanarak aşağıdaki formülü tahmin edebiliriz. J sayılarının hesaplanması bakımından daha önce elde ettiğimiz (3) bağıntısına göre oldukça kullanışlı bir formül:
m≥0 ve 0≤k≤2^m olmak üzere
J(2^m+k)=2k+1. (4)
Şimdi formülün uygulamasını yapalım: Oyun 103 kişiyle oynanırsa hangi sıradaki oyuncu kazanır?
J(103)=〖J(2〗^6+39)=2 .39+1=79.
Oyunu 79. sıradaki oyuncunun kazanacağını kolayca bulduk. Kim bilir, belki de Josephus da böyle bir formül bularak kendisinin ve arkadaşının hayatını kurtarmış olabilir!
Bu formülü yukarıda da belirttiğimiz gibi tahmini olarak çıkardık, kanıtlamamız gerekiyor. Kanıtı tümevarımla yapacağız.
m=0 için k=0 olmalı. Bu değerleri (4)’te yerine koyarsak J(1)=1 olur.
Şimdi, m>0 ve 2^m+k=2n+1 iken, yani k tek sayıyken,
J(2^m+k)=2k+1
eşitliğinin doğru olduğunu gösterelim. m üzerine tümevarım yapacağız, yukarıdaki eşitlikte m yerine m-1 yazalım:
J(2^(m-1)+k)=2k+1. (5)
Şimdi artık (3) ve (5)’ten aşağıdaki eşitlikleri yazabiliriz.
J(2^m+k)=2J(2^(m-1)+(k-1)/2)+1
J(2^m+k)= 2( 2(k-1)/2 )+1
=2k+1.
Böylece k tek sayı iken kanıt tamamlandı. Benzer şekilde k’nın çift olma durumu da kanıtlanarak tahmini olarak çıkardığımız (4) formülü kesinleşmiş olur.
Son olarak yazının başındaki hikâyeye dönersek… Her 3 kişiden biri eleniyordu. Bu türdeki problemler matematiğin kombinatorik alanında genel olarak “Josephus işlemi” adı altında ele alınıyor ve hikâyedeki çeşitlemesi için tersinden sıralamayı (Inverse Permutatıon) ifade eden Josephus[n,m] gösterimi kullanıyor.[1] Bilgisayar programıyla yapılacak listeyle kazanan oyuncunun numarası bulunuyor. Bu gösterime göre çember etrafına n kişi sıralanıyorsa ve her m kişiden biri eleniyor. Örneğin n=41 ve m=3 alınırsa Josephus[41, 3] ile gösterilir, aşağıdaki listeyle Josephus ve arkadaşının numaraları olan 16 ve 31 sayıları bulunur.
3,6,9,12,15,18,21,24,27,30,33,36,39,
1,5,10,14,19,23,28,32,37,41,7,13,20,26,
34,40,8,17,29,38,11,25,2,22,4,35,16,31.
Kaynaklar
1) Petkovic, M, Famous Puzzles of Great Mathematicians, AMS, 2009.
2) Nesin, A, Sayma, Nesin Yayınları, 2009.
