أحجيات

أحجيات

التحديد الدقيق لموقع دب قطبي^(*)

<E.D.شاشا>

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

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

للتوصل إلى دب قطبي في تصميم على هيئة دولاب وبرانق، ينطلق أربعة قناصين من الكوخ المركزي (1)، ويتجه ثلاثة قناصين نحو أحد الأكواخ الخارجية (2)، ثم يتحرك قناصان حول المحيط في أي من الاتجاهين (3). ولكن ما العدد اللازم من القناصين في حالة بيان مستوى planar graphمُصمم كالموضح في (4)؟

لنفترض أن المجمع مصمم بالنمط المبين في الشكل الجانبي 1، حيث يوجد كوخ أول في المركز، وستة أكواخ واقعة على المحيط. في هذه الحالة، يكفي أربعة من القناصة لتعقب الدب [انظر الأشكال 1 و 2 و 3 في يسار هذه الصفحة]. لكن ماذا لو أن العلماء نسوا المخطط الدقيق لمركز الأبحاث؟ إن كل ما يعرفونه يقينا هو أن ثمة دهليزا واحدا فقط يصل بين كل كوخ وآخر، وأن الدهاليز لا تتلاقى، ولا يقطع أي منها أي دهليز آخر. (يُسمي علماء الرياضيات هذه الطپولوجيا⁽¹⁾ بيانا مستويا planar graph). وفي الشكل 4 نعرض مثالا على بيان مستو. فإذا أمكن أن يبدأ القناصة من أي كوخ في الشكل 4، فما هو أصغر عدد يلزم إيفاده من القناصة؟

لنفترض الآن أن ثمة 100 كوخ مرتبة في شبكة مستطيلة، وأن لكل كوخ دهاليز تُفْضي إلى الأكواخ المجاورة له أفقيا ورأسيا (لا وجود لدهاليز قطرية). عندئذ ما هو أصغر عدد من القناصة يلزم إيفاده لإنجاز مهمة صيد الدب؟

(*) Pinpointing a Polar Bear

(1) أي هذا الوصف التفصيلي للموقع أو ما يسمى طبوغرافية الموقع. (التحرير)