Topluca İntihar Edilen Bir Çemberde Hayatta Kalmanın Anahtarı: Josephus Problemi
m.s. birinci yüzyıla uzanan bir matematik problemi. anlatılanlara göre, bir mağaranın içinde saklanan yahudi tarihçi flavius josephus ve 40 adamının etrafı romalı askerler tarafından çevrilir. askerler tarafından öldürülmek yerine intihar etmeyi seçen flavius ve arkadaşları daire şeklinde dizilirler ve birinci kişiden başlayarak sırayla herkesin yedi sıra sonrakini öldüreceği ve geriye kalan son kişinin de intihar edeceği bir kural geliştirirler. sonuçta ise toplamdaki 41 kişiden geriye bir tek flavius josephus kalır, o da bir şekilde romalılardan kurtulmayı başarır.
josephus problemi de -yukarıdaki örnekten yola çıkarak- toplamda n kişi için sıradaki kişinin k sıra sonraki kişiyi öldüreceği bir dairesel dizilimde en sona kaçıncı sıradaki kişinin kalacağını bulmayı amaçlamakta. (not: kolayca görüleceği üzere çift sayılı elemanların hiçbir şekilde kurtuluşu olmayacaktır çünkü ilk hamleyi 1. sıradaki eleman 2. sıradaki elemana, ikinci hamleyi 3. sıradaki eleman 4. sıradaki elemana... yapacağı için daha ilk turdan bütün çift sayılı elemanlar öldürülecektir.)
numberphile, problemin birer kişi atlanarak (yani k=2 için) bir video (ref 1) hazırlamış. buna göre herhangi bir n sayısı için n=2^a+l şekilde maksimum a tamsayısı bulunur, ardından da sona kalan kişiyi bulmak için s=2l+1 formülü uygulanır.
Mevzubahis video
örnekler
n=8 kişi ---> 8=2³+0 ---> s=2*0+1=1
n=41 kişi ----> 41=2^5+9 ---> s=2*9+1=19
n=123 kişi ---> 123=2^6+59 ---> s=2*59+1=119
(benzer örnek alıştırmaları için ref 2'deki linkteki script kullanılabilir.)
problemin en genel tekrarlamalı çözümü için ise (2<=k<n)
g(n,k)=(g(n-1,k)+k) mod(n),
g(1,k)=0
formülasyonu bulunmakta (algoritmalar için ref 5 ve ref 7).
1. https://www.youtube.com/watch?v=ucsd3zgzmge
2. http://webspace.ship.edu/…ensley/mathdl/joseph.html
3. https://www.quora.com/…o-solve-the-josephus-problem
4. http://sites.math.northwestern.edu/…ns/josephus.pdf
5. http://www.geeksforgeeks.org/…blem-using-bit-magic/
6. http://mathworld.wolfram.com/josephusproblem.html
7. https://en.wikipedia.org/wiki/josephus_problem
8. https://www.slideshare.net/…on-for-josephus-problem
