Some Generalizations of the Bridge and Torch Problem

تخيل عالماً لا تكون فيه الألغاز الأكثر إثارة تتعلق بالعثور على كنز مخفي أو حل جريمة قتل، بل تتعلق بإيصال مجموعة من الأصدقاء عبر جسر مظلم ومتهالك قبل شروق الشمس. هذا هو مجال التحسين التوافقي (combinatorial optimization)، وهو فرع من الرياضيات يتساءل: "ما هي أفضل طريقة مطلقة للقيام بشيء ما عندما تلتزم بقواعد صارمة؟". فكر في الأمر كأنه اللعبة النهائية لـ "تيتريس"، ولكن بدلاً من الكتل، أنت تضع الأشخاص في فترات زمنية، والهدف هو إنهاء المستوى في أقصر وقت ممكن. النسخة الكلاسيكية من هذه اللعبة، والمعروفة باسم "مسألة الجسر والمصباح" (Bridge and Torch Problem)، مشهودة بفضل قواعدها البسيطة الخادعة: يجب على مجموعة من الأشخاص عبور جسر ليلاً باستخدام مصباح يدوي واحد فقط. الجسر ضيق (لا يتسع إلا لشخصين في آن واحد)، ويجب حمل المصباح في كل مرة يعبر فيها شخص ما، وإذا عبر شخصان معاً، فإنهما يتحركان بسرعة الشخص الأبطأ. يبدو الأمر سهلاً، لكن العثور على أسرع جدول زمني هو رقصة معقدة من التوقيت والاستراتيجية حيرت الكثيرين.

الآن، تخيل أنك تأخذ ذلك اللغز نفسه وترفع مستوى التحدي. ماذا لو كان الجسر يتسع لثلاثة أشخاص؟ أو ماذا لو لم يكن لديك جسر واحد، بل مركز له العديد من الأشباه، مثل شبكة العنكبوت، حيث يمكن للأشخاص العبور إلى وجهات مختلفة في نفس الوقت؟ هذا بالضبط ما استكشفه "ثانج بانج إيرن" و"جيرارد سايسون" في ورقتهما البحثية. لقد أخذا مسألة "الجسر ذي الشخصين" الكلاسيكية، حيث يمتلك كل شخص وقتاً محدداً للعبور من 1 إلى $n$، ولم يكتفيا بحلها فحسب؛ بل وجدا صيغة سحرية تتنبأ بالوقت الأدنى المطلوب لأي عدد من الأشخاص. ثم دفعا الحدود إلى أبعد من ذلك، حيث وضعا القواعد لجسر يتسع لثلاثة أشخاص، وحتى لشبكة على شكل نجمة. واكتشفا أنه بينما تصبح الإجابات معقدة، إلا أنها تتبع أنماطاً جميلة ومتكررة يمكن كتابتها في معادلة واحدة.

الرقصة الكلاسيكية لشخصين

لنبدأ باللغز الأصلي. لديك مجموعة من $n$ من الأشخاص، وأوقات عبورهم هي ببسا ممل مجرد الأرقام $1, 2, 3, \dots, n$. الشخص الذي وقته 1 هو عداء سريع، بينما الشخص الذي وقته $n$ هو بطيء الحركة. الهدف هو نقل الجميع من الجانب الأيسْتر للنهر إلى الجانب الأيمن.

أثبت المؤلفان أنه بالنسبة لهذا الإعداد المحدد، هناك صيغة مثالية مغلقة لحساب الحد الأدنى للوقت، $T(n)$. إنها ليست مجرد تخمين؛ بل استخرجاها عن طريق تقسيم المسألة إلى أجزاء أصغر. أدركا أن أفضل استراتيجية تتضمن إرسال أسرع شخصين (1 و 2) أولاً، ثم يعود أحدهما بالمصباح، ثم إرسال أبطأ شخصين معاً، ثم يعود الشخص السريع الآخر. هذه "الكتلة" من الحركات تنهي مهمة هذين الشخصين الأبطأ وتترك النظام جاهزاً لتكرار العملية للمجموعة المتبقية.

من خلال جمع تكاليف هذه الكتل، وجدا أن الوقت الإجمالي لـ $n$ من الأشخاص هو:
$$T(n) = \frac{n^2}{4} + 3n - \frac{5 + (-1)^n - 1}{8}$$
تعمل هذه الصيغة لكل عدد من الأشخاص $n$ أكبر من أو يساوي 2. كما لاحظا أن تسلسل الأوقات الناتج (1, 2, 6, 11, ...) هو نمط معروف في عالم الرياضيات، لكنهما قدما برهاناً مباشراً جديداً لسبب عمل هذه الصيغة تحديداً. ومن المثير للاهتمام، أنهما أظهرا أن الاستراتيجية "القياسية" المتمثلة في إرسال أسرع شخص ذهاباً وإياباً مع الجميع ليست دائماً هي الأفضل. فعلى سبيل المثال، مع 4 أشخاص، تستغرق الطريقة القياسية وقتاً أطول من طريقة "الكتلة" الذكية.

الجسر الذي يتسع لثلاثة

بعد ذلك، سأل المؤلفان: "ماذا لو كان الجسر أعرض؟". تخيلا جسراً يمكنه استيعاب ما يصل إلى 3 أشخاص في آن واحد، ولكن لا يزال هناك مصباح يدوي واحد فقط. هذا يغير اللعبة تماماً. مع ثلاثة أشخاص، يمكنك إرسال ثلاثي، ولكن لا تزال بحاجة إلى شخص يعيد الضوء.

وجدا أنه بالنسبة لنسخة "السعة 3" هذه، فإن الوقت الأمثل، $T_3(n)$، يتبع إيقاعاً مختلفاً وأكثر تعقيداً. تتضمن الصيغة مزيجاً من منحنى تربيعي (مثل $n^2/6$) وبعض المصطلحات الموجية المتماوجة التي تتضمن جيب التمام (cosine) و $(-1)^n$. وتحديداً، لـ $n \ge 7$، يكون الوقت هو:
$$T_3(n) = \frac{n^2}{6} + 2n - \frac{181}{36} + \frac{(-1)^n}{4} - \frac{2}{9} \cos\left(\frac{2n\pi}{3}\right)$$
هذه الصيغة فريدة جداً لدرجة أنها خلقت تسلسلاً جديداً تماماً من الأرقام في الموسوعة عبر الإنترنت للمتتاليات (A392434). أثبت المؤلفان ذلك من خلال إظهار أن أفضل استراتيجية تتضمن تحريك مجموعات من ستة أشخاص في كل مرة في دورة محددة، مما يقلل المسألة من $n$ من الأشخاص إلى $n-6$ من الأشخاص مع إضافة تكلفة متوقعة في كل مرة. كما تحققا من الأعداد الأصغر (مثل 1 إلى 6) عن طريق القوة الغاشمة (brute force) للتأكد من أن الصيغة تتناسب مع بداية الخط.

لقد نظرا لفترة وجيزة في جسر يتسع لـ 4 أشخاص، لكنهما اعترفا بأن النمط يصبح فوضوياً ولم يتمكنا من إيجاد صيغة بسيطة لذلك بعد. وهما يشกัน في أن صيغة موجودة، لكن العثور عليها أصعب بكثير.

الشبكة ذات الشكل النجمي

أخيراً، تأخذ الورقة البحثية قفزة عملاقة بعيداً عن جسر واحد. تخيل مركزاً (مثل محطة قطار) له العديد من الطرق (الأشبال) المؤدية إلى وجهات مختلفة (الأوراق). هذا يسمى "الرسم البياني النجمي" (star graph). في هذه النسخة، لديك $n$ من الأشخاص في المركز، و $k$ من الطرق، و $t$ من المصابيح اليدوية.

القواعد هنا مختلفة قليلاً: في "خطوة" واحدة، يمكنك إرسال أشخاص عبر طرق مختلفة في نفس الوقت، طالما لا يستخدم شخصان نفس الطريق ولا يوجد شخص في مكانين في آن واحد. يتم تحديد وقت تلك الخطوة بناءً على أبطأ شخص يتحرك في تلك الخطوة.

وجد المؤلفان أن الحد الأدنى للوقت يعتمد بشدة على عدد المصابيح والطرق التي تمتلكها. إذا كان لديك ما يكفي من المصابيح والطرق لإرسال الجميع في دفعة واحدة كبيرة، فإن الوقت هو مجرد وقت أبطأ شخص ($n$). ولكن إذا كنت محدوداً، فإن الوقت ينمو تقريباً مثل $n^2$. وقد استخرجا صيغة الحد الأدنى:
$$T(n, k, t) \ge sn - ms(s-1)$$
حيث $m$ هو الرقم الأصغر بين عدد الطرق أو المصابيح، و $s$ هو عدد "الجولات" اللازمة لإخراج الجميع.

أحد أروع أجزاء هذا القسم هو كيفية ارتباطه بالرياضيات البحتة. فعندما نظرا إلى الأرقام الناتجة عن مسألة الرسم البياني النجمي هذه، أدركا أنهما يعيدان إنشاء هويات رياضية شهيرة تتضمن "دالة الأرضية" (floor function) (والتي تعني ببساطة التقريب إلى أقرب عدد صحيح سفلي). على سبيل المثال، من خلال حل اللغز لأعداد محددة من الأشخاص والطرق، "أعادا اكتشاف" هوية معروفة حول مجموع دالات الأرضية، مما يظهر كيف يمكن للغز جدولة ممتع أن يكشف عن حقائق عميقة حول الأنماط العددية.

باختصار، تأخذ هذه الورقة لغزاً كلاسيكياً، وتحله بصيغة دقيقة، وتوسع نطاقه إلى جسور أعرض، ثم تديره إلى شبكة متعددة المسارات، كل ذلك مع الكشف عن الجمال الرياضي الخفي على طول الطريق. إنها تظهر أنه حتى في لعبة بسيطة مثل عبور جسر، توجد طبقات من الاستراتيجية والبنية تنتظر من يكتشفها.