مجموع أرقام الحواف: لماذا نحتاج الرقم 5 مع أربعة ألوان؟

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

نحتاج حد اللوحة 5 للمسارين المنفصلين لأن أوراقهما الأربع تفرض أربعة أرقام مختلفة، وكل تقسيم للأرقام 1 إلى 4 بين المسارين يكرر مجموعًا، بينما الأرقام 1 و 3 و 2 و 5 تعطي ستة مجاميع مختلفة بأربعة أرقام مستخدمة.

• نختار للحواف أرقامًا صحيحة موجبة من 1 إلى k، ونمنع تساوي رقمي حافتين تلتقيان، ونطلب اختلاف مجاميع الحواف عند كل رأسين مختلفين؛ نقلل k، وهو حد اللوحة المسموحة، ونعد الأرقام المستخدمة كلًا على حدة. [1]
• للمسارين AB BC وDE EF، التعيين AB=1 وBC=3 وDE=2 وEF=5 يعطي مجاميع A B C D E F بالأرقام 1،4،3،2،7،5. نستخدم أربعة أرقام {1,2,3,5}، لكن k=5 والرقم 4 غير مستخدم.
• الأوراق الأربع ترى أرقام حوافها وحدها فتفرض أربعة أرقام مختلفة. عند k=4، لا يبقى إلا تقسيم {1,2,3,4} إلى 1،2 مع 3،4؛ أو 1،3 مع 2،4؛ أو 1،4 مع 2،3. كل تقسيم يكرر مجموعًا؛ لذلك لا تكفي أربعة أو أقل.
• تبديل الرقم المستخدم 5 إلى 4 يحافظ على صحة الحواف واختلاف مجموعات ألوان الرؤوس، لكنه يجعل مجموع B ومجموع F يساويان 4؛ تغيير الأسماء لا يحفظ شرط المجموع دائمًا.
• مجموعتا {1,4} و{2,3} مختلفتان لكن مجموع كل منهما 5. التعيين AB=1 وBC=4 وDE=2 وEF=3 يميز مجموعات الرؤوس، ويفشل بالمجموع عند B وE؛ اختلاف المجاميع يفرض اختلاف المجموعات في تلوين صحيح، والعكس لا يلزم. [1] [3]
• حافة تشكل مكونًا وحدها أو رأسان معزولان يمنعان الحل. إذا غابت الحافة المنفردة وكان المعزولون واحدًا أو لا أحد، فقوى 2 على الحواف تعطي مجاميع مختلفة؛ هذا يثبت الوجود، ولا يثبت الحد الأدنى. الرأس الوحيد بلا حواف يقبل k=0.
• راجعنا 25 نموذجًا و 64 رسمًا من أربعة رؤوس دون تجاهل تبديلات الأرقام. للمسارين هناك 144 تعيينًا صحيحًا من 1 إلى 4، ولا واحد يميز المجاميع؛ ومن 1 إلى 5 هناك 32 تعيينًا يميزها. عشرة من رسوم الأربعة رؤوس بلا حل، والبقية أقل k لها 2 في 12 و 3 في 32 و 4 في 9 و 5 في رسم واحد.

الأرقام من 1 إلى k، والمطلوب أقل حد للوحة

في تلوين الحواف الصحيح، يأخذ كل خط لونًا واحدًا، وتختلف ألوان أي حافتين تلتقيان عند رأس واحد؛ التلوين العادي يقلل عدد الأسماء المستخدمة. [2]

في المسألة هنا، الألوان أرقام صحيحة موجبة من 1 إلى k، مع التلوين الصحيح للحواف، واختلاف مجموع الأرقام الملتقية عند كل رأسين مختلفين؛ نطلب أصغر k. [1]

نكتب Q[A] لمجموع أرقام الحواف الملتقية عند A. إذا كانت حافتاه تحملان 1 و 3، كان Q[A]=4؛ لا نخصص رقمًا مستقلًا للرأس، ولا نجمع أسماء رؤوس جيرانه.

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

يجوز ترك أرقام من اللوحة دون استعمال؛ {1,2,3,5} أربعة أرقام مستخدمة، والحد k=5، ولا يصبح الحد 4 بمجرد عد الأسماء. [1]

نفترض رسومًا بسيطة غير موجهة لها رأس واحد على الأقل. نتبع تعريف اللوحة الذي يسمح k=0 للحالة الخالية من الحواف؛ حين توجد حافة، رقمها موجب من 1 إلى k. [1]

مساران منفصلان: أربعة أرقام مستخدمة، والحد k=5

خذ المسارين AB BC وDE EF، دون حواف بينهما. أعط AB=1 وBC=3 وDE=2 وEF=5. تختلف الأرقام عند المركز B وعند المركز E، فيصح تلوين الحواف.

الأوراق A وC وD وF لكل منها حافة واحدة، فمجاميعها 1 و 3 و 2 و 5. المركز B له Q[B]=1+3=4، والمركز E له Q[E]=2+5=7.

إذن مجاميع A B C D E F هي 1،4،3،2،7،5، والست مختلفة. لا توجد مقارنة معفاة بسبب انفصال المسارين؛ نجح التعيين عبر المكونين أيضًا.

أرقام الحواف المستخدمة {1,2,3,5}، وعددها أربعة. أعلى رقم مستخدم 5، وكلها من 1 إلى 5؛ هذا شاهد يحقق k=5 دون استعمال الرقم 4.

المجموع عند B يساوي 4 رغم أن 4 غير مستخدم على حافة. والمجموع عند E يساوي 7، أعلى من حد اللوحة 5؛ الشرط 1 إلى k يخص أرقام الحواف، لا مجاميع الرؤوس.

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

كل تقسيم للأرقام 1 و 2 و 3 و 4 يكرر مجموعًا

الأوراق الأربع لها مجاميع مساوية لأرقام حوافها الوحيدة. لو تكرر رقم على حافتين، لتساوى مجموع ورقتين؛ لذلك يجب أن تختلف أرقام الحواف الأربع جميعًا.

هذا يستبعد k أقل من 4. وعند k=4، يجب أن تكون الأرقام الأربعة المستخدمة هي {1,2,3,4} بالضبط، لأن لدينا أربعة أرقام مختلفة مسموحة من هذه المجموعة.

يمكن توزيع المجموعة على المسارين بثلاثة تقسيمات إلى زوجين: {1,2} مع {3,4}، أو {1,3} مع {2,4}، أو {1,4} مع {2,3}. تبديل طرفي مسار أو تبديل المسارين لا يغير وجود مجموع مكرر، ولا يعيد تسمية القيم العددية.

في الأول، مركز الزوج {1,2} له المجموع 3، مساويًا لمجموع الورقة ذات الرقم 3 في المسار الآخر. في الثاني، مركز {1,3} له المجموع 4، مساويًا لمجموع الورقة ذات الرقم 4.

في الثالث، المركزان لهما المجموع 5، لأن 1+4=2+3=5. إذن كل تقسيم يفشل في مقارنة زوج من الرؤوس، رغم أن أرقام الحواف الأربع مختلفة وصحيحة.

لا يوجد حل بحد 4، وكل حد أصغر مستبعد بالأوراق. الشاهد بحد 5 صحيح، فتكون القيمة الدنيا k=5، مع أربعة أرقام مستخدمة فقط.

تبديل 5 إلى 4 يبقي الحواف صحيحة لكنه يكرر مجموع 4

ابدأ بالشاهد AB=1 وBC=3 وDE=2 وEF=5. بدل اسم اللون المستخدم 5 بالرقم 4، وأبق بقية الأرقام كما هي؛ صارت الحواف 1،3،2،4.

الأرقام الأربعة ما زالت مختلفة، وتختلف أرقام الحافتين عند كل مركز، فيبقى التلوين الصحيح. لكن Q[B]=1+3=4، وصار Q[F]=4 لأن F ورقة على الحافة EF.

مجاميع A B C D E F بعد التبديل هي 1،4،3،2،6،4. يتساوى مجموع B مع مجموع F، فيفشل الشرط العام بين مركز في مكون وورقة في مكون آخر.

قبل التبديل، مجموعتا ألوان B وF هما {1,3} و{5}. بعده تصبحان {1,3} و{4}؛ هما مختلفتان في الحالتين. بل تبقى مجموعات الألوان الست مختلفة، رغم فشل المجاميع العددية.

لذلك لا تحذف فجوات الأرقام بمجرد ضغط الأسماء إلى 1 و 2 و 3 و 4. هذا الإجراء يحفظ مقارنة المجموعات، لكنه قد يخلق مساواة جديدة بين المجاميع؛ يجب إعادة فحص كل زوج رؤوس.

اختلاف مجموعات الألوان لا يضمن اختلاف مجموع أرقامها

في تمييز الرؤوس بمجموعات ألوان الحواف، نطلب تلوينًا صحيحًا للحواف ومجموعات مختلفة عند كل زوج رؤوس، مع تقليل عدد الألوان. [3]

خذ AB=1 وBC=4 وDE=2 وEF=3 على المسارين. مجموعات الأوراق هي {1} و{4} و{2} و{3}، ومجموعتا المركزين {1,4} و{2,3}؛ الست مختلفة.

لكن Q[B]=1+4=5 وQ[E]=2+3=5؛ يفشل شرط المجموع عند B وE. عدد عناصر المجموعتين متساوٍ، ومجموع الأرقام متساوٍ، لكن المجموعتين نفسيهما مختلفتان.

في تلوين الحواف الصحيح، لا يتكرر رقم داخل مجموعة حواف الرأس. فإذا تساوت مجموعتا الأرقام عند رأسين، تساوى مجموع الأرقام أيضًا؛ لذلك اختلاف كل المجاميع يفرض اختلاف كل المجموعات، والعكس لا يلزم.

نعد الحد k وعدد الأرقام المستخدمة كلًا على حدة. لحالة المسارين، تمييز المجموعات يحتاج أربعة أسماء، وتمييز المجاميع يحتاج حدًا 5؛ لا تستبدل جواب إحدى المسألتين بجواب الأخرى.

قوى 2 تثبت الوجود عند غياب الموانع، وقد تكون بعيدة عن الأقل

طرفا حافة تشكل مكونًا وحدها لهما الرقم نفسه مجموعًا، لأن كليهما يرى الحافة نفسها وحدها؛ لا يوجد حل مهما كان حد اللوحة. والمعزولان لهما المجموع 0، فيمنعان الحل أيضًا.

معزول واحد مسموح: مجموع حوافه 0، ومجموع أي رأس غير معزول موجب لأن أرقام حوافه موجبة. الرسم ذو رأس واحد بلا حواف يقبل التعيين الفارغ وحدًا k=0.

عند غياب الحافة المنفردة ووجود معزول واحد على الأكثر، أعط الحواف أرقامًا مختلفة من قوى 2: 1 و 2 و 4 و 8، ثم 16 إن احتجت حافة خامسة.

مجموع أي مجموعة من قوى 2 المختلفة يحدد تلك المجموعة وحدها؛ لا يمكن لمجموعتي حواف مختلفتين أن تعطيا الرقم نفسه. والأرقام المختلفة على جميع الحواف تحقق التلوين الصحيح أيضًا.

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

على المسارين، الأرقام AB=1 وBC=2 وDE=4 وEF=8 تعطي المجاميع 1،3،2،4،12،8، وكلها مختلفة. لكنها تستعمل حدًا 8، بينما الشاهد السابق يحقق حدًا 5؛ الوجود ليس برهانًا على الحد الأدنى.

نحصر القيم العددية نفسها، دون تجاهل تبديلات أسماء الألوان

جدول النماذج يعرض أقل حد k للمجاميع، وعدد الأرقام المستخدمة في شاهد، وتعيين ذلك الشاهد. قد يختلف الشاهد عن المثال في النص مع تحقيق الحد الأدنى نفسه؛ للمسارين الشاهد 1،2،4،5 صالح أيضًا وحد لوحته 5.

راجعنا 25 نموذجًا بحصر الأرقام الفعلية من 1 إلى كل حد نجربه، وفحصنا الحدود من 0 حتى أول حد يقبل حلًا؛ لم نتجاهل تبديلات الأسماء، لأن التبديل قد يغير المجاميع.

فحص منفصل في طريقة الحصر جرب 213987 تعيينًا عدديًا في هذه النماذج؛ منها 39093 صحيحة للحواف و 1431 تميز المجاميع. هذه أعداد تعيينات عبر الحدود المجربة، لا أعداد رسوم أو أزمنة تنفيذ.

للمسارين، عند k=4 هناك 144 تعيينًا صحيحًا للحواف، ولا واحد يميز مجاميع الرؤوس الستة. وعند k=5 هناك 32 تعيينًا يميزها؛ راجعنا أيضًا التقسيمات الثلاثة التي تفسر استحالة الحد 4.

في أربعة رؤوس، ست حواف ممكنة تعطي 64 رسمًا مسمى. عشرة رسوم بلا حل؛ في البقية أقل k هو 2 في 12، و 3 في 32، و 4 في 9، و 5 في رسم واحد. المجموع 64.

الفحص المنفصل جرب 31333 تعيينًا عدديًا عبر الحدود المجربة لهذه الرسوم؛ منها 1974 صحيحة للحواف و 600 تميز المجاميع. راجعنا الشواهد، وأقل حد، وعدد الأرقام المستعملة، وحالات الحافة المنفردة والمعزولين، وشواهد قوى 2.

البراهين والأمثلة والفحوص من إعداد المقال بعد قراءة التعريف؛ لا نزعم صيغة لكل عائلة رسوم. الطريقتان تستعملان Python، ولا ندعي مراجعًا بشريًا مستقلًا أو برنامجًا يحل كل رسم.