Browse By

JOSEPHUS PROBLEMİNE KISA BİR BAKIŞ

İsmini 1.yy’da yaşamış Kudüslü tarihçi Flavius Josephus’dan alan problemin hikayesi şöyle başlar: Romalılar ve Yahudiler arasındaki savaşta sona kalan 41 Yahudi bir mağarada köşeye sıkıştırılır ve Romalı komutan bir oyun oynamaya karar verir.41 kişilik bir çember oluşturulup herkesin bir yanındaki öldürülerek en son kişiye kadar gelinecektir.Yani daha açık ve matematiksel bir ifadeyle bir çember etrafına dizili n tane oyuncu olsun bunlar sırasıyla;

1.oyunda kalsın

2.gitsin

3.oyunda kalsın 

4 .gitsin şeklinde devam edecek bir döngü halinde oyun ilerler.

3 kişi için bu oyunu oynarsak 1.kalır, 2.gider, 3.kalır sonra 1.gider, son olarak 3.kalır ve kazanan 3.olur dolayısıyla 3 kişili oyunu 3. kazanmıştır.Yani oyunumuzun baş harfi ile bir fonksiyon yazarsak J(3)=3 diyebiliriz.Oyunu 2 kişili ve 1 kişili versiyonları için de oynarsak J(2)=1 ve J(1)=1 olduğunu görebiliriz.Bir de 4 kişi olduğunu varsayarak oynarsak;

1. kalsın

2. gitsin

3.kalsın

4.gitsin

1.kalsın

2.zaten gitmişti o yüzden hesaba almıyorum artık ikinci tur için yeni ikincimizi ilk başladığımızdaki 3.gibi düşünebiliriz.Bu durumda 3. gidince geriye 1 kalır dolayısıyla J(4)=1 olur.

Bundan sonra sizi yormadan;

J(5)=3

J(6)=5

J(7)=7 

olduğunu söyleyeceğim, isterseniz deneyin yada bana güvenin.

Dikkat edilirse ;

J(1)=1

—-

J(2)=1

J(3)=3

—-

J(4)=1

J(5)=3

J(6)=5

J(7)=7

Örüntüyü fark ettiniz mi ?Muhtemelen J(8) için yazdığımda da 1 gelecek ve devamında 1,3,5,7,9 şeklinde J(12)’ye kadar ilerleyecek bir örüntü yakalayacağım fakat matematiksel olarak ortaya koymadığım sürece bunlara sadece bir sezgi diyebilirim ki tıpkı Golbach’ın her sayıyı iki asalın toplamı şeklinde yazılabileceğini sezip aksine örnek bulamadıysa da matematiksel olarak kesin bir ispat ortaya koyamadığından söylediklerinin ‘conjecture’ olarak kalması gibi.

Konumuza dönersek fark edilirse oyundaki kişi sayısı tek olunca çemberdeki ilk turda hep tek sayılı olanlar eleniyor.Yani 2n+1(tek sayılı) kişili oyuncu ile başlayıp bir tur döndüğünde 2,4,6…2n ve son olarak da tur bitince başa döndüğümüzde 1 elenir geriye 3,5,…,2n+1.ler (yani tekler) kalır.O zaman tek sayılı oynanan Josephus için bir bağıntı yakalamaya çalışırsak; 

Mesela J(5)’i ele alalim ilk turdan sonra 3. ve 5.kalacaktır dolayısıyla durum sanki 2.tur için 2 kişili oynanan Josephus’a benzedi diyebiliriz (J(5) ikinci turunda J(2)’ye benzedi).

Son durumda biliyoruz ki 2’li josephus’da (J(2)) 1.kazanıyor ;

5’li Josephus’un ikinci turunda birinci sayım 3 olduğu için J(5)=3 ve J(2)=1 aradaki 2n+1’lik gözlemden dolayı J(2n+1)=2J(n)+1 şeklinde tek sayılı Josephus’lar için genelleyebileceğim bir bağıntı yakalayabiliyorum şimdilik.

Artık çift sayılı oyuncu barındıran Josephus’lar için gerekli bağıntıyı da tekliler için yaptıklarımıza bakarak rahatlıkla çıkarabiliriz.

Bir sonraki yazımızda Josephus probleminin yinelemeli ilerleyişindeki bir ilginçliğe değinip kapalı formülünü araştıracağız.

Rüştü Erciyes Karakaya 

Kullanılan kaynak: Concrete Mathematics, by Donald Knuth, Oren Patashnik, and Ronald Graham.

Not:Konuyla alakalı daha ayrıntılı bilgi isteyenler türkçe kaynak olarak Ali Nesin hocanın Sayma kitabına bakabilirler.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir