Josephus Problemine kısa bir bakış-1

İsmini 1.yy’da yaşamış Romalı 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;

Birinci oyunda kalsın,

İkinci gitsin,

Üçüncü oyunda kalsın,

Dördüncü gitsin şeklinde devam edecek bir döngü halinde örüntü ilerler.

Mesela 3 kişi için bu oyunu oynarsak;

Birinci kalır, ikinci gider, üçüncü kalır sonra birinci gider, son olarak üçüncü kalır ve kazanan olur. Dolayısıyla 3 kişili oyunu üçüncü kazanmıştır. Yani oyunumuzun baş harfi ile bir fonksiyon yazarsak J(3)=3 diyebiliriz. Oyunu 2 kişili ve 1 kişili için de oynarsak J(2)=1 ve J(1)=1 olduğunu görebiliriz. Başka bir örnek olarak oyunda 4 kişi olduğunu varsayarak oynarsak;

Birinci kalsın,

İkinci gitsin,

Üçüncü kalsın,

Dördüncü gitsin,

Birinci kalsın,

İkinci zaten gitmişti bunu atlıyorum ve artık ikinci tur için yeni ikincimiz ilk başladığımızdaki üçüncü gibi düşünebiliriz. Bu durumda üçüncü 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 ya da 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 fakat matematiksel olarak ortaya koymadığım sürece bunlara sadece bir sezgi diyebilirim tıpkı Golbach’in 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ılar eleniyor. Yani 2n+1 (tek sayılı) kişili oyuncu ile başlayıp bir tur döndürüldüğü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 alalım ilk turdan sonra üçüncü ve beşinci 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.

Kullanılan kaynak: Concrete Mathematics

Textbook by Donald Knuth, Oren Patashnik, and Ronald Graham.

  • Site İçi Yorumlar

En az 10 karakter gerekli
Makale gönderim sistemimize hoş geldiniz

Galeri Alanı

828 x 478