Hikâyeye göre Yahudi tarihçi Flavius Josephus ve kırk arkadaşı, Roma askerleri tarafından bir mağarada sıkıştırıldı.. Teslim olmak yerine ölmeye karar verdiler. Bunun için bir çember oluşturdular ve belirli bir düzene göre sırayla birbirlerini öldürmeye başladılar. Josephus, sonunda hayatta kalan iki kişiden biri oldu. Diğer kişiyi teslim olmaya ikna etti ve böylece kurtuldu.
Bu anlatı zamanla şu matematik sorusuna dönüştü. Bir çemberde duran n kişi, belirli bir sayma kuralına göre sırayla elenirse en son hangi kişi hayatta kalır?
Josephus Problemi, matematik ve bilgisayar bilimlerinde klasik örneklerden biridir. Özellikle algoritmalar, veri yapıları ve özyinelemeli hesaplamalar gibi konuları anlatmak için sıklıkla kullanılmaktadır.
Josephus Problemi Nasıl Çözülmelidir?
Josephus Problemi’ni anlamak için çocuk oyunlarına benzer bir örnek düşünelim. Bir grup çocuk çember olur. Sayma belirli bir yerden başlar ve her ikinci çocuk oyundan çıkar. Sayma, elenen kişinin hemen yanındaki çocuktan devam eder. En sonunda yalnızca bir çocuk kalır.
13 çocukla başladığımızı varsayalım. Her ikinci çocuk elendiğinde kazananı tek tek sayarak bulabiliriz. Ancak asıl amaç, bunu her seferinde baştan saymadan bulmaktır. Josephus Problemi tam olarak bunu sorar. Başlangıçta kaç kişi olursa olsun, son kalan kişinin yerini önceden nasıl bulabiliriz?
Bu soruyu basitleştirmek için önce her ikinci kişinin elendiği duruma bakalım. Küçük örnekler yazıldığında dikkat çekici bir örüntü ortaya çıkar.
Tabloda iki şey hemen fark edilecektir. Kazanan her zaman tek numaralıdır. Ayrıca kişi sayısı 2’nin kuvveti olduğunda kazanan yine 1 numaradır. Yani 2, 4, 8 ve 16 kişilik çemberlerde hayatta kalan kişi 1 numaralı kişidir.
Bunun nedeni ilk turda tüm çift numaralı kişilerin elenmesidir. Geriye yalnızca tek numaralı kişiler kalır. Kişi sayısı 2’nin kuvveti olduğunda bu eleme düzeni her turda aynı biçimde küçülür ve 1 numara hiçbir turda elenmez. Bu yüzden sonunda kazanan yine 1 olur.
Josephus Problemi modüler aritmetik ile de ilgilidir.
Bir çemberde sayma yapıyor olmamız, bu problemi çözmek için modüler aritmetiğin uygun bir araç olabileceğini düşündürür.
Modüler aritmetik, bir sayının başka bir sayıya bölünmesinden kalanla ilgilenir. Örneğin, 7≡1(mod2) yazarız çünkü 7 sayısı 2’ye bölündüğünde kalan 1 olur.
Modüler aritmetiğe bazen saat aritmetiği de denir. Örneğin 12 saatlik bir saatte 12’den sonra yeniden 1’e dönülür. Çember üzerinde yapılan sayma işlemi de aynı mantıkla ilerlediği için Josephus Problemi’nin çözümünde modüler aritmetik önemli bir rol oynar.
Şimdiye kadar iki önemli örüntü gördük. Kişi sayısı 2’nin kuvveti olduğunda kazanan her zaman 1 numaralı kişidir. Diğer durumlarda ise kazanan konum, 2’nin en büyük kuvvetinden sonra kalan kişi sayısına bağlı görünür.
Bu nedenle kişi sayısını n=2k+r şeklinde yazalım. Burada 2k, n’den büyük olmayan en büyük 2 kuvvetini, r ise geriye kalan kişi sayısını gösterir. Örneğin 11 kişi varsa, 11=8+3=23+3 biçiminde ifade edilir.
Tabloya baktığımızda 11 kişi için kazananın 7 numara olduğunu görüyoruz. Ayrıca kazananın 7 olması da dikkat çekicidir. Çünkü 7=2×3+1 biçiminde de yazılır. Aslında aynı ilişkiyi başka örneklerde de görebiliriz.
Buradan basit bir kural elde ederiz. Önce kişi sayısından büyük olmayan en büyük 2 kuvvetini buluruz. Ardından kişi sayısından bu değeri çıkarırız. Son olarak bulduğumuz sayıyı ikiyle çarpıp 1 ekleriz. Sonuç, hayatta kalan kişinin başlangıçtaki konumunu verir.
Şimdi bu sonucu baştaki problemimize uygulayalım. Josephus Probleminde 41 kişi vardır. 41 için en büyük 2 kuvveti 32’dir ve 41 ile aralarındaki fark 9 sayısıdır. Bu sayıyı ikiyle çarpıp 1 eklersek 19 spnucunu elde ederiz. Yani Josephus, 41 kişilik çemberde 19. sırada durursa hayatta kalır.
Sonuç Olarak
Aynı sonuca ulaşmanın daha ilginç bir yolu daha vardır. Bunun için ikili sayı sistemine bakmamız gerekir. Bir sayıyı ikili sistemde yazdığımızda yalnızca 0 ve 1 rakamlarını kullanırız. Josephus Problemi’nin her ikinci kişinin elendiği özel durumunda, ikili gösterimdeki ilk 1’i en sona taşımak yeterlidir.
Örneğin 41 sayısının ikili gösterimi 101001’dir. Baştaki 1’i en sona taşırsak 010011 elde ederiz. Bu sayı onluk sistemde 19’a karşılık gelir. Yani sonuç yine 19 çıkar.
Bu yöntem, problemin neden algoritmalarla bu kadar yakından ilişkili olduğunu da gösterir. Bir çemberdeki basit sayma oyunu, düzen, örüntü ve hesaplama üzerine güçlü bir matematik problemine dönüşür.
Not: Tarihsel anlatının bazı sürümlerinde her üçüncü kişinin elendiği söylenir. Bu yazıda çözümü daha anlaşılır göstermek için her ikinci kişinin elendiği klasik sadeleştirilmiş versiyon ele alınmıştır.
Ayrıca okumak isterseniz:
- Parrondo Paradoksu: İki Yanlış Strateji Bazen Bir Doğruyu Getirir
- Patatesten Paradoks Çıkar mı? Patates Paradoksu İle Tanışın!
Kaynaklar ve ileri okumalar
- The Josephus Problem – Numberphile. Yayınlanma tarihi: 28 Ekim 2016; Bağlantı: https://www.youtube.com
- Park, Jang-Woo & DOGAN, Ali & Teixeira, Ricardo. (2021). Block Josephus Problem: When the Reality is More Cruel Than the Old Story. Hacettepe Journal of Mathematics and Statistics. 50. 1-12. 10.15672/hujms.750167.
Matematiksel
