⭕ دائرة النجاة
ضع n شخصا في دائرة. نَعُدّ k ابتداءً من رقم 1 ونُقصي الشخص رقم k، ثم نُعيد العد من الذي يليه. نستمر حتى يبقى الناجي الأخير. أين يجب أن تجلس لتنجو؟
المتبقّون
41
آخر مُقصى
—
الناجي
—
مع n = 41 و k = 3 (رجل من كل ثلاثة)، تكون هذه بالضبط دائرة أسطورة فلافيوس جوزيفوس. شغّل المحاكاة لتكتشف المكان الذي يُنجي.
⚔️ سنة 67: دائرة من 41 رجلا وأسطورة
نحن في سنة 67 ميلادية، خلال الحرب اليهودية الرومانية. فلافيوس جوزيفوس — مؤرخ يهودي، ومواطن روماني مستقبلي — مُحاصَر مع أربعين رفيقا تقريبا في كهف بيودفات (يوتاباتا)، في الجليل. وبدلا من الاستسلام للرومان، قرر رفاقه أن ينتحروا جماعيا.
وفق الأسطورة التي نشأت عن ذلك، اصطفوا في دائرة واتفقوا على أن يقتل بعضهم بعضا: نَعُدّ على طول الدائرة، وعلى فترات منتظمة يُقصى الرجل المُعيَّن. أما جوزيفوس — الذي لم يكن يرغب في الموت إطلاقا — فيُقال إنه حسب ذهنيا الموضع الذي ينبغي شغله ليكون أحد الناجِيَيْن الأخِيرَيْن… ثم أقنع جاره بأن يستسلما معا للرومان. النجاة عبر الرياضيات.
تستعيد الصيغة الرياضية المعيارية للمسألة هذه الأرقام: n = 41 شخصا، نُقصي رجلا من كل ثلاثة (k = 3). المُحاكي أعلاه يُعيد بناء هذه الدائرة بالضبط.
🔁 المسألة المُعمَّمة J(n, k)
استخلص علماء الرياضيات من هذه الحكاية مسألة خالصة، هي مسألة جوزيفوس:
نَصُفُّ n شخصا مُرقَّمين من 1 إلى n في دائرة. ابتداءً من رقم 1، نَعُدّ k أشخاص ونُقصي الشخص رقم k. نُعيد العد من الذي يليه، ونَعُدّ k من جديد، ونُقصي… وهكذا حتى لا يبقى سوى شخص واحد. والسؤال: ما هو موضع الناجي؟
نرمز بـ J(n, k) لهذا الموضع الفائز. فبالنسبة لدائرة جوزيفوس، نبحث إذن عن J(41, 3). تعطيك المحاكاة الجواب… لكن يمكننا أيضا حسابه دون محاكاة، وهنا تصبح الرياضيات أنيقة.
📐 التراجع: الرجوع إلى دائرة أصغر
تكمن الحيلة في إعادة ترقيم الدائرة مباشرة بعد أول إقصاء. عندما نُقصي الشخص في الموضع k، يبقى n − 1 شخصا، ويُستأنف العد عند الموضع k + 1. وإذا سمّينا 0 هذا الشخص الأول الجديد، فإننا نرجع تماما إلى المسألة نفسها، لكن مع n − 1 شخصا.
بترقيم المواضع ابتداءً من 0 (من 0 إلى n − 1)، نحصل على علاقة التراجع الشهيرة:
J(1, k) = 0
J(n, k) = ( J(n − 1, k) + k ) mod n
أما الموضع «البشري» للناجي (المُرقَّم ابتداءً من 1) فيكون عندئذ J(n, k) + 1.
يُحسَب هذا التراجع بحلقة بسيطة، في زمن خطي O(n) ودون محاكاة أي دائرة: نبدأ من 0، ونضيف k بترديد n على m من أجل m من 2 إلى n. وهذا أسرع بكثير من قتل الناس واحدا واحدا. وعند تطبيقه على n = 41, k = 3، فإنه يعطي الناجي في الموضع 31.
✨ الحالة السحرية k = 2: الصيغة الثنائية
عندما نُقصي شخصا من كل اثنين (k = 2)، تظهر صيغة ذات جمال مُدهش. لنكتب n بعزل أكبر قوة للعدد 2 يحتويها:
إذا كان n = 2a + l حيث 0 ≤ l < 2a، فإن الناجي يكون في الموضع 2l + 1.
مثال: بالنسبة لـ n = 41 = 32 + 9، لدينا 2a = 32 و l = 9، إذن الناجي (من أجل k = 2) سيكون في الموضع 2·9 + 1 = 19.
وإليك الخدعة السحرية في الأساس 2: خذ الكتابة الثنائية للعدد n، احذف البت ذا الوزن الأكبر (الرقم 1 الموجود على اليسار) وألصِقه أقصى اليمين. العدد الناتج هو بالضبط موضع الناجي. إنها مجرد دوران دائري نحو اليسار ببت واحد:
n = 41 = 101001₂ → نُمرِّر الرقم 1 الأول إلى النهاية: 010011₂ = 010011₂ = 19.
من الصعب أن يكون هناك ما هو أكثر أناقة: حل مسألة مجزرة قديمة يكمن في إزاحة بِتّات.
💻 الصلة بالمعلوميات
مسألة جوزيفوس من الكلاسيكيات الكبرى في دروس الخوارزميات، لأنها تُجسّد عدة أفكار مركزية:
- اللوائح المترابطة الدائرية: النمذجة الأكثر طبيعية تربط كل شخص بجاره، في حلقة مغلقة؛ وإقصاء شخص = حذف عقدة.
- الطوابير (queues): نُخرج k − 1 أشخاص (ونُعيد إدخالهم خلفا) ثم نُقصي الشخص رقم k — تطبيق في O(n·k) واضح جدا.
- التراجع مقابل المحاكاة: الصيغة J(n, k) = (J(n−1, k) + k) mod n تحل المسألة في O(n) دون أي بنية معطيات، مثال مثالي على التحسين بواسطة الرياضيات.
- أشجار فينويك / أشجار المقاطع: للإجابة في O(n log n) حتى عندما نريد الترتيب الكامل للإقصاءات.
إنه تمرين يتكرر باستمرار في مقابلات العمل التقنية ومسابقات البرمجة (ICPC)، تحديدا لأن له عدة مستويات من الحل، من الساذج إلى الذكي.
🎓 الصلة ببرنامجك الدراسي
- الحساب بالترديد: «mod n» في علاقة التراجع، والرجوع إلى 0 عند الدوران حول الدائرة.
- المتتاليات المُعرَّفة بالتراجع: J(n, k) تُبنى حدا حدا انطلاقا من J(1, k) = 0.
- الترقيم في الأساس 2: الصيغة السحرية للحالة k = 2 هي درس خالص في الكتابة الثنائية وقوى العدد 2.
- الخوارزميات والتعقيد: مقارنة حل في O(n·k) (المحاكاة) بحل في O(n) (التراجع) نقطة انطلاق ممتازة.