عدد رامزي: لماذا تضمن ستة رؤوس مثلثًا بلون واحد ولا تكفي خمسة؟

الخلاصة السريعة

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

• نلون الحواف لا الرؤوس. الرسم الكامل يصل كل زوج مختلف، والمثلث المطلوب ثلاثة رؤوس حوافها الثلاث من اللون نفسه؛ ليس مجرد حافتين متتاليتين.
• على A وB وC وD وE، نلون AB وBC وCD وDE وAE بالأحمر، وبقية الحواف AC وAD وBD وBE وCE بالأزرق. لا مثلث أحادي اللون؛ هذا شاهد على أن خمسة لا تضمنه.
• مع ستة رؤوس، نثبت A. له خمس حواف، والألوان اثنان؛ لو ظهر كل لون مرتين كحد أقصى لما تجاوز المجموع4. لذلك نجد ثلاث حواف بلون واحد، ونسمي أطرافها B وC وD.
• إذا كانت AB وAC وAD حمراء، وحافة BC حمراء أيضًا، فمثلث ABC أحمر. حافة BD أوCD حمراء تعطي مثلثًا مماثلًا مع A. لا يشترط أن تكون الحواف الداخلية الثلاث كلها حمراء.
• إذا لم توجد حافة حمراء بين B وC وD، فالحواف BC وBD وCD زرقاء كلها؛ مثلث BCD أزرق. لو بدأت الحواف الثلاث من A بالأزرق، نتبادل اسمي اللونين ونحصل على الحجة نفسها.
• خمسة لا تكفي، وستة تكفي لكل تلوين في هذه الشروط؛ إذن الحد الأدنى6. [1] الضمان وجود مثلث واحد على الأقل من أحد اللونين، لا أن كل ثلاثية تصلح ولا أن اللون المحدد مسبقًا هو المضمون.

ما الذي نلونه وما معنى المثلث؟

نختار أسماء مختلفة للرؤوس. تصل الحافة كل زوج من اسمين، ولا يوجد اتجاه أو وزن أو اتصال من الرأس بنفسه. في الرسم الكامل لا نترك زوجًا دون حافة؛ AB وBA تسميتان للحافة نفسها.

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

الثلاثية ABC تشكل مثلثًا أحادي اللون إذا اتفق لون AB مع AC ومع BC. تكفي حافة واحدة بلون مختلف لرفض هذه الثلاثية. لا نستنتج اللون الثالث من اللونين الأولين؛ نفحصه مستقلًا.

يمكن ترجمة الأحمر إلى «يعرفان بعضهما» والأزرق إلى «لا يعرفان بعضهما» بشرط اعتبار العلاقة متبادلة ومحددة لكل زوج. سنبقى مع الألوان كي تكون الشروط واضحة، دون افتراض أن معرفة A بـB ومعرفة B بـC تعني معرفة A بـC.

عدد رامزي يبحث عن أصغر عدد يضمن النتيجة في كل رسم من هذا النوع. [1] العثور على مثال ناجح لا يثبت وحده أن كل تلوين ناجح؛ لإثبات الحد نحتاج عدم كفاية خمسة وكفاية ستة.

ارسم خمسة رؤوس دون مثلث أحادي اللون

نبدأ بخمسة رؤوس A وB وC وD وE. عدد أزواجها10؛ نلون حواف الحلقة AB وBC وCD وDE وAE بالأحمر. حوافها الأخرى AC وAD وBD وBE وCE زرقاء. القائمتان لا تتداخلان وتغطيان الأزواج العشرة.

الجيران الأحمران لـA هما B وE، لكن BE زرقاء؛ لذلك لا مثلث أحمر يمر بـA. ولـB جاران أحمران A وC وبينهما AC زرقاء. وبالطريقة نفسها نجد أن جاري كل رأس بالأحمر لا تتصل بينهما حافة حمراء.

ولـA جاران أزرقان C وD، لكن CD حمراء. ولـB جاران أزرقان D وE، وبينهما DE حمراء. كذلك يتصل الجاران الأزرقان لكل رأس بحافة حمراء. إذن لا مثلث أزرق أيضًا، لا مجرد غياب مثلث من لون واحد بعينه.

تستطيع متابعة الحلقة الزرقاء A→C→E→B→D→A؛ طولها خمسة كما في الحلقة الحمراء A→B→C→D→E→A. وجود حلقة لا يجعل ثلاثة من رؤوسها مثلثًا من لونها، لأن الحافة التي تختصر الحلقة قد تكون من اللون الآخر.

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

لماذا نجد ثلاث حواف بلون واحد عند ستة؟

انتقل إلى رسم كامل على ستة رؤوس. ثبت رأسًا A وانظر إلى الحواف الخمس منه إلى الرؤوس الأخرى. كل واحدة حمراء أو زرقاء، لذلك تنقسم الحواف إلى مجموعتين بحسب اللون.

لو كانت الحمراء اثنتين أوأقل والزرقاء اثنتين أوأقل، لم يتجاوز مجموعهما4. لكن حواف A خمس. إذن واحدة من المجموعتين تحوي ثلاث حواف على الأقل؛ الحجة لا تحتاج توزيعًا عشوائيًا أو تساوي احتمال اللونين.

اختر ثلاثًا من الحواف ذات اللون المتكرر وسم أطرافها B وC وD. هنا أسماء B وC وD تصف الرؤوس المختارة للحجة، وليست ادعاء بأن ثلاثة أسماء معينة منذ البداية يجب أن تحقق الشرط في كل تلوين.

سنفترض أن AB وAC وAD حمراء. إذا كان اللون المتكرر أزرق، نتبادل كلمتي أحمر وأزرق في البرهان. لا تتغير العلاقات أو عدد الحواف بهذا التبادل، لذلك يغطي البرهان الحالتين.

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

حافة حمراء داخلية أو مثلث أزرق كامل

إذا كانت AB وAC وAD حمراء، فوجود حافة حمراء بين B وC وD يعطي مثلثًا أحمر مع A. وإذا لم توجد، صارت الحواف الثلاث بينها زرقاء، فمثلث BCD أزرق. هذه الحالتان تستنفدان الخيارات. [1]

مثلًا إذا كانت BC حمراء، نقرأ AB وAC وBC فنجد ثلاث حواف حمراء لمثلث ABC. لا يهم لون BD أوCD لهذا الشاهد؛ المثلث المختار لا يستخدمهما. والحافة BD الحمراء تعطي ABD، وCD الحمراء تعطي ACD.

في الحالة الثانية نفحص BC وBD وCD كلها. عدم وجود الأحمر بينها يعني الأزرق لكل منها، لأن النموذج لا يسمح بلون ثالث أو حافة غير ملونة. عندئذ لا نحتاج A في المثلث؛ الرؤوس B وC وD وحدها هي الشاهد.

الصورة الداخلية تعرض أربع رؤوس مختارة فقط من الستة: يسارًا AB وAC وAD وBC حمراء، وBD وCD زرقاء؛ الشاهد ABC. يمينًا AB وAC وAD حمراء، والحواف الداخلية الثلاث زرقاء؛ الشاهد BCD.

الرأسان الآخران لا يدخلان في الشاهد المختار، لكنهما موجودان في الرسم الكامل ذي الستة الذي بدأنا منه. إخفاؤهما في لوحة الحجة لا يثبت أن أربعة رؤوس تضمن النتيجة؛ اختيار الثلاثة المتفقين احتاج خمس حواف من A أولًا.

لماذا يثبت المثال والحجة أن العدد6؟

التلوين على خمسة رؤوس يمنع كل مثلث أحادي اللون، فيسقط ضمان النتيجة عند خمسة. والحجة على ستة تبدأ من تلوين كيفما كان، ثم تجد مثلثًا في إحدى الحالتين، فتثبت ضمان النتيجة عند ستة.

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

إذن عدم كفاية خمسة مع كفاية ستة يعطي الحد الأدنى6. هذا يوافق R(3,3)=6؛ الرقمان داخل القوسين يشيران إلى ثلاثة رؤوس من اللون الأول أو ثلاثة من الثاني، لا إلى مجموع ستة أجزاء منفصلة. [1]

في يمين الصورة الرئيسية احتفظنا بالألوان العشرة بين A وB وC وD وE، وأضفنا F مع خمس حواف حمراء. أصبح ABF أحمر لأن AB وAF وBF حمراء. توجد أيضًا AEF وBCF وCDF وDEF حمراء، لكن المثال ليس بدلًا من البرهان العام.

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

وجود مثلث لا يحدد كل ثلاثية أو لونًا مسبقًا

إذا لونت كل حواف الستة بالأزرق، وجدت مثلثات زرقاء ولا مثلثًا أحمر. هذا تلوين صحيح، فيوضح أن الضمان «أحمر أوأزرق» لا يسمح باستبداله بضمان الأحمر وحده. وبالعكس عند تلوين الجميع بالأحمر.

ولا نضمن أن كل ثلاثية من الستة تكون أحادية اللون. في مثال الصورة، ABC تضم AB وBC الحمرتين وAC الزرقاء، بينما ABF أحمر. النجاح في ثلاثية لا يجعل جميع الثلاثيات صالحة.

عندما يوجد أكثر من مثلث، يكفي اختيار واحد لتحقيق صيغة الوجود. لا نستنتج من الحجة أن العدد الكلي للمثلثات يساوي واحدًا، ولا أن الشاهد الذي اكتشفناه وحيد. المثال ذو F يعرض خمسة مثلثات حمراء فعلًا.

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

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