مسألة الأصدقاء والغرباء

هل بإمكاننا دومًا إيجاد ترتيبٍ ما في الأنظمة العشوائيّة؟ وفي حال كان بإمكاننا ذلكَ، فكم يجب أن يكونَ حجمُ نظامٍ ما حتّى يحوي قدرًا معيّنًا من التّرتيب؟

دعونا نتأمّلُ مثالًا ملموسًا: لنفترض وجودَ غرفةٍ تحوي 6 أشخاص. ولنهتّمَ بمعرفةِ ما إذا كان الأشخاصُ في هذه الغرفةِ يعرفونَ بعضَهم أم لا. سندعو اثنينِِ من الأشخاص أصدقاءَ في حالِ كانوا يعرفونَ بعضهم وعدا ذلكَ فسوف ندعوهم بغرباء.

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

هذا الرّسمُ البيانيُّ يبدو فوضويًّا بعضَ الشّيء. ولكن لنطرحِ السّؤالَ التّالي: هل بإمكاننا إيجادُ ثلاثةِ أشخاصٍ على الأقلِّ في هذه الغرفةِ بحيثُ يكونونَ جميعهم أصدقاء (مثلّثٌ أزرق) أو جميعهم غرباءُ (مثلّثٌ أحمر)؟ في هذه الحالة، الإجابةُ هي نعم. ولكن ماذا لو كانَ الرّسمُ البيانيُّ مختلفًا؟ فهل بإمكاننا دومًا إيجادُ مجموعةٍ مرتّبةٍ من ثلاثةِ أشخاص؟

الإجابةُ هي نعم، وإحدى طرقِ الإثباتِ هي إيجادُ جميعِ التّشكيلاتِ الممكنةِ لتلوينِ الرّسمِ السّابقِ والتّحقُّقِ في كلِّ تشكيلةٍ من وجودِ مثلّثٍ أزرقَ أو أحمرَ. لكن لسوءِ الحظِّ، يوجدُ أكثرُ من 30000 تشكيلةً، الأمرُ الّذي يجعلُ هذا الإثباتَ بحاجةٍ للكثيرِ من العملِ الشّاق. ولحسن الحظِّ، يوجدُ طريقةٌ أسهل، أولًا: اختر أيَّة نقطةٍ (شخصٍ) تريدُ من الرّسمِ البيانيِّ ولاحظ أنَّ خمسَةَ خطوطٍ تخرجُ من هذه النّقطة، كلَّ خطّ متّجهٍ إلى إحدى النّقطِ المتبقّيةِ كما في الشّكل التّالي:

بوجود خمسةِ خطوطٍ ملوّنةٍ بأحدِ لونينِ فقط (أحمر أو أزرق) لابدَّ من وجودِ ثلاثةِ خطوطٍ على الأقلِّ من اللّونِ نفسه. لنفترض هنا أنّه لدينا ثلاثةَ خطوطٍ حمراءَ. يصبح لدينا أربعُ نقاطٍ متّصلةٍ كما في الشّكلِ التّالي:

ما لون الخطوطٍ الثّلاثةِ المتبقّيةِ الّتي تصلُ بين هذه النّقاط الأربعة؟

في حال كان أحدُها على الأقلِّ أحمرًا فسيتشكّلُ لدينا مثلّثًا أحمرَ كما في الشّكلِ:

وفي حالِ كانت جميعها زرقاءَ فسيتشكّلُ لدينا مثلّثًا أزرقَ كما في الشّكل:

وهكذا نكون قد أثبتنا أنّه بوجودِ ستِّ نقاطٍ (أو أكثرَ)، يمكننا دومًا إيجادُ إمّا ثلاثةِ أصدقاءٍ أو ثلاثةِ غرباءٍ. وهذا يطرحُ السّؤالَ التّالي:

"ماهو أقلُّ عددٍ نحتاجه من الأشخاصِ لنكونَ أكيدينَ من إيجادِ إمّا ثلاثةِ أصدقاءِ أو ثلاثةِ غرباء؟" وإجابةُ هذا السّؤال هو عددٌ يُدعى بعددِ "رامزي" ويكتبُ على الشّكلِ التّالي:

R(3،3)

. وسُميَّ بهذا الاسمِ تيمُّنًا بعالمِ الرّياضيات فرانك رامزي الّذي عملَ في عشرينيّاتِ القرنِ الماضي

الآن، لقد رأينا أنَّ ستَّةَ أشخاصٍ عددٌ كافٍ لإيجادِ إمّا ثلاثةِ أصدقاءٍ أو ثلاثةِ غرباءٍ وبالتّالي فإنَّ R(3،3) بالتّأكيد لن يكونَ أكبرَ من 6، ولكن يا تُرى هل خمسةُ أشخاصٍ تكفي؟

الرّسمُ البيانيُّ التّالي يوضِّح لنا أنَّ الإجابةَ هي لا:

وبذلك نكون قد أثبتنا أنّ:

6=(3،3)R

مع القليلِ من العملِ يمكنكَ أيضًا إثباتُ أنَّ:

18=(4،4)R

أي أنّ أقلَّ عددٍ من الأشخاصِ الّذي نحتاجهُ لإيجادِ إمّا أربعةِ أصدقاءٍ أو أربعةٍ غرباءٍ هو 18. ولكن ماذا عن قيمةِ:

R(a،b)

بحيث تأخذ a وَ b أيَّةَ قِيَمٍ صحيحةٍ؟ هل حتّى يوجدُ هكذا قيمة؟ وهل يوجدُ عددٌ من الأشخاصِ كافٍ لضمانِ وجودِ إمّا a من الأصدقاءِ أو b من الغرباءِ؟ لحسنِ الحظِّ يمكننا التّأكُّدُ من وجودِ هكذا قيمةٍ مهما كانت a وَ b بفضلِ نظريّةِ رامزي الّتي تقولُ بأنَّه مهما كان مقدارُ التّرتيبِ الّذي نريدُه يمكننا إيجادُه طالما كانَ الرّسمُ البيانيُّ كبيرًا بما يكفي.

إذًا ما قيمةُ (5،5)R؟ الإجابة هي أن لا أحدَ يعلم! في الحقيقةِ، القليلُ فقط من أعدادِ رامزي معروفةٌ. وأكثرُ ما يمكننا قولُه عن (5،5)R باستخدام ِمعرفتِنا الحاليّةِ هو أنّه محصورٌ بينَ العددَين 42 وَ 49.

وكيف يمكنُ أن يكونَ تحديدُ القيمةِ تمامًا بهذه الصّعوبةِ؟ طريقةُ الإثباتِ تتضمّنُ إيجادَ حدٍّ أعلى، أي على سبيلِ المثالِ، رأينا بسهولةٍ أنَّ (3،3)R لا يمكن أن يكونَ أكبرَ من 6. ولكن لإثباتِ أنّه لا يمكن أن يكونَ 5 كان علينا بناءَ رسمٍ بيانيّ بـ 5 نقاطٍ كمثالٍ معاكسٍ. المشكلةُ هي أنّنا نبحثُ عن التّرتيبِ في كل التّشكيلاتِ الممكنةِ، لذا فإنَّ أفضلَ الأمثلةِ المعاكسةِ سوفَ يكونُ غالبًا يحوي الكثيرَ من العشوائيّةِ وسيبدو عشوائيًّا. وهذا يجعلُه صعبًا أو حتّى مستحيلًا إيجادُ قاعدةٍ تعطي أمثلةً مُعاكسةً جيّدةً.

أيضًا، قد يكون الحدُّ الأعلى كبيرًا جدًّا، فكيف سنثبتُ ذلكَ عندها ؟ ربّما عن طريقِ فحصِ كلِّ التّشكيلاتِ الممكنةِ للرّسمِ البيانيِّ عن طريقِ حاسوبٍ لإثباتِ أنّها تحوي دومًا العددَ المناسبَ من الأصدقاءِ أو الغرباءِ؟ المشكلةُ في هذه الطّريقةِ أنَّ العددَ سيكونُ ضخمًا جدًّا. إذ أنَّنا لإثباتِ أنَّ (5،5)R هو على الأكثرِ 49 سنحتاجُ للتّحقُّقِ من 21176 تشكيلةٍ ممكنةٍ. وهذا العددُ يُعدُّ أكبرَ بكثيرٍ من عددِ الذّراتِ الموجودةِ في الكونِ المعروف. لذا لا يوجدُ أيَّةُ فرصةٍ لوجودِ كومبيوترٍ سريعٍ بما فيه الكفايةِ لإكمالِ هكذا بحث. ممّا يجعلنا نقول إنَّ هذه أحجيةٌ قد لا نعرفُ إجابتَها يومًا.

المصدر :

هنا

تصميم الصورة:Kenan Dada