مشكلة يوسيفوس

تُحل المشكلة بشكل صريح عندما يُقتل شخص واحد من كل شخصين (أي أن كل شخص يقتل الشخص الذي على يساره أو يمينه)، أي${\displaystyle k=2}$(للحالة الأكثر عمومية)${\displaystyle k\neq 2}$(يُوضح الحل أدناه.) يُعبّر عن الحل بشكل تكراري . ليكن${\displaystyle f(n)}$يشير إلى موقع الناجي عندما يكون هناك في البداية n شخصًا (و${\displaystyle k=2}$في الدورة الأولى، يموت جميع الأشخاص ذوي الأرقام الزوجية . وفي الدورة الثانية، يموت الشخص الثاني الجديد، ثم الشخص الرابع الجديد، وهكذا؛ وكأن الدورة الأولى لم تكن موجودة أصلاً.

إذا كان العدد الأولي للأشخاص زوجيًا، فإن الشخص الموجود في الموضع x خلال الدورة الثانية حول الدائرة كان في الأصل في الموضع x.${\displaystyle 2x-1}$(لكل اختيار لـ x ). ليكن${\displaystyle n=2j}$الشخص في${\displaystyle f(j)}$الشخص الذي سينجو الآن كان في الأصل في هذا المنصب${\displaystyle 2f(j)-1}$وهذا ما ينتج عنه التكرار$${\displaystyle f(2j)=2f(j)-1.}$$

إذا كان العدد الأولي للأشخاص فرديًا ، فيمكن اعتبار الشخص رقم 1 ميتًا في نهاية الدورة الأولى حول الدائرة. ومرة ​​أخرى، خلال الدورة الثانية حول الدائرة، يموت الشخص الثاني الجديد، ثم الشخص الرابع الجديد، وهكذا. في هذه الحالة، كان الشخص الموجود في الموضع س في الأصل في الموضع س${\displaystyle 2x+1}$وهذا ما ينتج عنه التكرار $${\displaystyle f(2j+1)=2f(j)+1.}$$

عندما يتم جدولة القيم${\displaystyle n}$و${\displaystyle f(n)}$يظهر نمط ( OEIS : A006257  ، وهو أيضًا العمود الأيسر من الأرقام الزرقاء في الشكل أعلاه):

ن	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
${\displaystyle f(n)}$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

يشير هذا إلى أن${\displaystyle f(n)}$هي متتالية فردية متزايدة تبدأ من جديد مع${\displaystyle f(n)=1}$عندما يكون الدليل n قوة للعدد 2. لذلك، إذا تم اختيار m و l بحيث${\displaystyle n=2^{m}+l}$و${\displaystyle 0\leq l<2^{m}}$، ثم${\displaystyle f(n)=2l+1}$من الواضح أن القيم في الجدول تحقق هذه المعادلة. أو يمكن افتراض أنه بعد وفاة l شخصًا، لا يتبقى سوى${\displaystyle 2^{m}}$الناس، ويذهب إلى${\displaystyle 2l+1}$الشخص الأول. يجب أن يكون هذا الشخص هو الناجي.${\displaystyle f(n)=2l+1}$فيما يلي، يتم تقديم برهان بالاستقراء .

النظرية: إذا${\displaystyle n=2^{m}+l}$و${\displaystyle 0\leq l<2^{m}}$، ثم${\displaystyle f(n)=2l+1}$.

البرهان: يُستخدم الاستقراء القوي على n . الحالة الأساسية${\displaystyle n=1}$هذا صحيح. تُدرس الحالات بشكل منفصل عندما يكون n زوجيًا وعندما يكون n فرديًا.

إذا كان n زوجيًا، فاختر${\displaystyle l_{1}}$و${\displaystyle m_{1}}$بحيث${\displaystyle n/2=2^{m_{1}}+l_{1}}$و${\displaystyle 0\leq l_{1}<2^{m_{1}}}$. لاحظ أن${\displaystyle l_{1}=l/2}$.${\displaystyle f(n)=2f(n/2)-1=2[(2l_{1})+1]-1=2l+1}$يتم الحصول على حيث تتبع المساواة الثانية من فرضية الاستقراء.

إذا كان n فرديًا، فاختر${\displaystyle l_{1}}$و${\displaystyle m_{1}}$بحيث${\displaystyle (n-1)/2=2^{m_{1}}+l_{1}}$و${\displaystyle 0\leq l_{1}<2^{m_{1}}}$. لاحظ أن${\displaystyle l_{1}=(l-1)/2}$.${\displaystyle f(n)=2f[(n-1)/2]+1=2[(2l_{1})+1]+1=2l+1}$حيث أن المساواة الثانية تتبع من فرضية الاستقراء. وهذا يكمل البرهان.

يمكن حل المعادلة l للحصول على تعبير صريح لـ${\displaystyle f(n)}$: $${\displaystyle f(n)=2(n-2^{\lfloor \log _{2}(n)\rfloor })+1.}$$

أكثر أشكال الإجابة أناقةً تتضمن التمثيل الثنائي بحجم n :${\displaystyle f(n)}$يمكن الحصول على ذلك عن طريق إزاحة دورية لليسار بمقدار بت واحد للعدد n نفسه. إذا تم تمثيل n بالنظام الثنائي على النحو التالي:${\displaystyle n=1b_{1}b_{2}b_{3}\dots b_{m}}$إذن، الحل يُعطى بواسطة${\displaystyle f(n)=b_{1}b_{2}b_{3}\dots b_{m}1}$ويستند برهان ذلك إلى تمثيل n على النحو التالي :${\displaystyle 2^{m}+l}$أو من التعبير أعلاه لـ${\displaystyle f(n)}$.

التنفيذ: إذا كان n يمثل عدد الأشخاص، فإن الموقع الآمن يُحدد بواسطة الدالة${\displaystyle f(n)=2l+1}$، أين ${\displaystyle n=2^{m}+l}$و${\displaystyle 0\leq l<2^{m}}$.

أما إذا تم تمثيل الرقم بالصيغة الثنائية، فإن البت الأول يشير إلى${\displaystyle 2^{m}}$وستشير البتات المتبقية إلى l . على سبيل المثال، عندما ⁠${\displaystyle n=41}$، تمثيله الثنائي هو

ن = 1 0 1 0 0 1 2 م = 1 0 0 0 0 0 ل = 0 1 0 0 1

/** * @param n عدد الأشخاص الواقفين في الدائرة * @return الموضع الآمن الذي سينجو من التنفيذ * f(N) = 2L + 1 حيث N = 2^M + L و 0 <= L < 2^M */ public int getSafePosition ( int n ) { // إيجاد قيمة L للمعادلة int valueOfL = n - Integer . highestOneBit ( n ); return 2 * valueOfL + 1 ; }

ن = 1 0 1 0 0 1 f(n) = 0 1 0 0 1 1

/** * @param n (41) عدد الأشخاص الواقفين في الدائرة * @return الموضع الآمن الذي سينجو من التنفيذ */ public int getSafePosition ( int n ) { return ~ Integer . highestOneBit ( n * 2 ) & (( n << 1 ) | 1 ); // ---------------------- --- | ------------ // الحصول على أول بت مضبوط | | إزاحة n إلى اليسار وقلب البت الأخير // وأخذ مكمله | | // | | // ضرب n في 2 | // عملية AND المنطقية لنسخ البتات الموجودة في كلا المعاملين. }

في عام 1997، اكتشف لورنز هالبايزن ونوربرت هونجربوهلر صيغة مغلقة للحالة${\displaystyle k=3}$لقد أظهروا أن هناك ثابتًا معينًا

${\displaystyle \alpha \approx 0.8111...}$

يمكن حساب ذلك بدقة اختيارية. بمعلومية هذا الثابت، اختر m ليكون أكبر عدد صحيح بحيث${\displaystyle \operatorname {round} (\alpha \cdot (3/2)^{m})\leq n}$(سيكون هذا إما${\displaystyle m^{\prime }=\operatorname {round} (\log _{3/2}n/\alpha )}$أو${\displaystyle m^{\prime }-1}$ثم، يكون الناجي الأخير هو

${\displaystyle f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+(2}$إذا تم تقريبها لأعلى وإلا${\displaystyle 1)}$

للجميع${\displaystyle n\geq 5}$.

كمثال على الحساب، يقدم هالبايزن وهونغربوهلر${\displaystyle n=41,k=3}$(وهي في الواقع الصيغة الأصلية لمسألة يوسيفوس). يقومون بحساب ما يلي:

${\displaystyle m^{\prime }\approx \operatorname {round} (\log _{3/2}41/0.8111)\approx \operatorname {round} (9.68)=10}$

${\displaystyle \operatorname {round} (\alpha \cdot (3/2)^{m^{\prime }})\approx \operatorname {round} (0.8111\cdot (3/2)^{10})=47}$وبالتالي${\displaystyle m=9}$

${\displaystyle \operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31}$(لاحظ أن هذا الرقم تم تقريبه إلى الأدنى)

${\displaystyle f(n)=3(41-31)+1=31}$

يمكن التحقق من ذلك من خلال النظر إلى كل تمريرة متتالية على الأرقاممن 1 إلى41 :

1، 2، 4، 5، 7، 8، 10، 11، 13، 14، 16، 17، 19، 20، 22، 23، 25، 26، 28، 29، 31، 32، 34، 35، 37، 38، 40، 41

2، 4، 7، 8، 11، 13، 16، 17، 20، 22، 25، 26، 29، 31، 34، 35، 38، 40

2، 4، 8، 11، 16، 17، 22، 25، 29، 31، 35، 38

2، 4، 11، 16، 22، 25، 31، 35

2، 4، 16، 22، 31، 35

4، 16، 31، 35

16، 31

31

تُستخدم البرمجة الديناميكية لحل هذه المشكلة في الحالة العامة من خلال تنفيذ الخطوة الأولى ثم استخدام حل المشكلة المتبقية. عندما يبدأ الفهرس من واحد، فإن الشخص الموجود في${\displaystyle s}$يتحول من الشخص الأول إلى الشخص الأول في الوضع${\displaystyle ((s-1){\bmod {n}})+1}$حيث n هو العدد الإجمالي للأشخاص.${\displaystyle f(n,k)}$يشير إلى موقع الناجي. بعد${\displaystyle k}$يُقتل الشخص رقم -، دائرة من${\displaystyle n-1}$يبقى، ويبدأ العد التالي بالشخص الذي كان رقمه في المسألة الأصلية${\displaystyle (ك{\bmod {n}})+1}$سيكون موقع الناجي في الدائرة المتبقية هو${\displaystyle f(n-1,k)}$إذا بدأ العد عند${\displaystyle 1}$؛ تغيير هذا لمراعاة حقيقة أن نقطة البداية هي${\displaystyle (ك{\bmod {n}})+1}$ينتج عنه التكرار ^{[ 12 ]}$${\displaystyle f(n,k)={\big (}[f(n-1,k)+k-1]{\bmod {n}}{\big )}+1,{\text{ with }}f(1,k)=1,}$$ والتي تأخذ الشكل الأبسط $${\displaystyle g(n,k)=[g(n-1,k)+k]{\bmod {n}},{\text{ with }}g(1,k)=0}$$ إذا كانت المواضع مرقمة من${\displaystyle 0}$ل${\displaystyle n-1}$بدلاً من.

يستغرق هذا النهج وقتًا تشغيليًا${\displaystyle O(n)}$لكن بالنسبة للصغار${\displaystyle k}$وكبيرة${\displaystyle n}$هناك نهج آخر. يستخدم النهج الثاني أيضًا البرمجة الديناميكية ولكنه يستغرق وقتًا أطول للتنفيذ.${\displaystyle O(k\log n)}$يعتمد ذلك على النظر في قتل الرتبة k ، ثم الرتبة 2k ، وهكذا.${\displaystyle (\lfloor n/k\rfloor k)}$-th أشخاص كخطوة واحدة، ثم تغيير الترقيم.

يتخذ هذا النهج المحسن الشكل التالي: $${\displaystyle g(n,k)={\begin{cases}0&{\text{if }}n=1,\\(g(n-1,k)+k){\bmod {n}}&{\text{if }}1<n<k,\\{\begin{Bmatrix}g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)-n{\bmod {k}}+n&{\text{if }}g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)<n{\bmod {k}}\\\left\lfloor {\dfrac {k\left(g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)-n{\bmod {k}}\right)}{k-1}}\right\rfloor &{\text{if }}g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)\geq n{\bmod {k}}\end{Bmatrix}}&{\text{if }}k\leq n.\\\end{cases}}}$$