عدّ التلوينات: هل 24 تعني 24 تقسيمًا؟

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

لا؛ في مثال المسار AB BC CD، توجد 24 إسنادًا لثلاثة ألوان مسماة، وأربعة تقسيمات دون أسماء ألوان. كل تقسيم هنا يعطي 6 إسنادات. هذه المساواة في الوزن ليست قاعدة لكل لوحة: مع أربعة ألوان نحصل على 108 إسنادات من خمسة تقسيمات، بأوزان مختلفة.

• كثير الحدود اللوني يحصي تلوينات الرؤوس، ويعد تبديل أسماء الألوان تلوينًا مختلفًا. تقييمه عند عدد صحيح من الألوان يعطي عدد تلك التلوينات، والعدد اللوني هو أقل عدد ألوان يسمح بتلوين صحيح. [1] في التلوين الصحيح، يجب اختلاف لوني كل رأسين متجاورين. [2] نثبت رسمًا منتهيًا بسيطًا غير موجه، ونلون الرؤوس بألوان مسماة؛ يجوز ترك بعض الألوان المتاحة دون استعمال، وتبقى أسماء الرؤوس ثابتة.
• للمسار أربعة رؤوس مسماة وثلاث حواف. مع ثلاثة ألوان، الخيارات 3 ثم 2 ثم 2 ثم 2، فيكون 3×2×2×2=24. منها 6 تستخدم لونين، و 18 تستخدم الثلاثة؛ العدد 24 لا يعني أن الرسم يحتاج 24 لونًا.
• التقسيمات الممكنة بثلاثة ألوان هي {A,C}|{B,D} و{A,C}|{B}|{D} و{A,D}|{B}|{C} و{B,D}|{A}|{C}. لكل منها 6 إسنادات لألوان اللوحة؛ ترتيب المجموعات أو عناصرها لا يضيف تقسيمًا.
• مع أربعة ألوان يضاف تقسيم الرؤوس الأربعة منفردة. تقسيم المجموعتين يعطي 4×3=12 إسنادًا، وكل تقسيم من ثلاث مجموعات يعطي 4×3×2=24، وتقسيم الأربع يعطي 24؛ المجموع 12+3×24+24=108، لا خمسة أضعاف وزن واحد.
• قسمة 108 على 4! تعطي 4.5 لا عدد التقسيمات 5، لأن الألوان غير المستخدمة تسمح باختلاف الأوزان. القسمة 24 على 3! تنجح في المثال ذي الثلاثة ألوان فقط لأن أوزان مجموعتي الألوان وثلاث مجموعات تتفق فيه.
• إضافة AD تحول المسار إلى دورة رباعية؛ تمنع تقسيم {A,D}|{B}|{C} وإسناداته 6. يبقى 24−6=18 تلوينًا بثلاثة ألوان وثلاثة تقسيمات. كلا الرسمين يحتاج لونين فقط، رغم اختلاف عدد تلويناتهما.
• راجعنا لوحات من 0 إلى 5 ألوان للرسمين، بعدد 1958 إسنادًا في حصر اللوحات المطلوبة، مع فحص مستقل للتقسيمات وأوزانها. لا توجد تلوينات بلا ألوان أو بلون واحد؛ مع لونين يوجد إسنادان لكل رسم. الحصر محدود، وحجة عدّ المسار منفصلة.

أسماء الألوان جزء من الإسناد

كثير الحدود اللوني يحصي تلوينات الرؤوس، ويعد تبديل أسماء الألوان تلوينًا مختلفًا. تقييمه عند عدد صحيح من الألوان يعطي عدد تلك التلوينات، والعدد اللوني هو أقل عدد ألوان يسمح بتلوين صحيح. [1]

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

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

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

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

أربع اختيارات متتابعة تعطي 24

ثبت الحواف AB BC CD فقط. للمسار أربعة أسماء A B C D، ولا توجد AC أوAD أوBD. اختر لون A من الثلاثة؛ ثم اختر لون B من اللونين المختلفين عن A.

بعد اختيار B، يملك C لونين غير لون B. قد يساوي لون A لأن AC ليست حافة. وبعد C، يملك D لونين غير لون C. لا نضيف قيدًا بين A وD، لأن AD غائبة في هذا المدخل.

لذلك العدد 3×2×2×2=24. لا نفترض استعمال الثلاثة كلها: مثلًا إعطاء A وC الأزرق، وB وD الذهبي، إسناد صحيح يترك الأخضر غير مستعمل.

إذا استعملنا لونين فقط، فرض المسار المجموعتين {A,C} و{B,D}. نختار لون الأولى بثلاث طرق ولون الثانية بطريقتين، فيكون 6 إسنادات تستخدم لونين بالضبط. الباقي 24−6=18 يستخدم الألوان الثلاثة.

وبالسبب نفسه، للوحة من k ألوان مع k≥1، يملك A خيارات k، وكل من الثلاثة اللاحقين خيارات k−1. عدد الإسنادات للمسار المعطى هو P(k)=k(k−1)³. عند k=1 تكون النتيجة صفرًا بسبب الحافة AB؛ ونعالج اللوحة الخالية k=0 بصفر مباشرة لأن الرؤوس غير فارغة.

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

أربعة تقسيمات وليست أربعة إسنادات

كل مجموعة في تقسيم اللون المشترك غير فارغة، ولا تضم طرفي حافة. لا يشترط أن تكون رؤوسها متصلة؛ المجموعة {A,D} مثلًا مسموحة في المسار لأن AD ليست حافة، رغم وجود طريق بينهما.

باستعمال مجموعتين فقط، يفرض اختلاف الجيران التقسيم {A,C}|{B,D}. لا نعد {B,D}|{A,C} مرة أخرى؛ إنه تبادل ترتيب عرض المجموعتين نفسيهما.

وباستعمال ثلاث مجموعات، لا بد من جمع رأسين في مجموعة واحدة وترك الآخرين منفردين. الأزواج غير المتجاورة هي AC وAD وBD، فتنتج التقسيمات الثلاثة {A,C}|{B}|{D} و{A,D}|{B}|{C} و{B,D}|{A}|{C}.

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

لكل تقسيم من مجموعتين، توجد 3×2=6 إسنادات لألوان مختلفة من اللوحة. ولكل تقسيم من ثلاث مجموعات توجد 3×2×1=6 أيضًا. لذلك تقسيم واحد من النوع الأول وثلاثة من الثاني يعطيان 6+3×6=24.

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

أربعة ألوان تغير وزن المجموعات

وسع اللوحة إلى أربعة ألوان مسماة، مع السماح ببقاء ألوان غير مستعملة. لم نغير الرسم؛ التقسيمات الخمسة الممكنة هي الأربعة السابقة، ومعها {A}|{B}|{C}|{D}.

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

ولكل تقسيم من ثلاث مجموعات، تكون الخيارات 4 ثم 3 ثم 2، فتنتج 24 إسنادًا. ولدينا ثلاثة تقسيمات من هذا النوع، فتساهم 72 إسنادًا. ولتقسيم الأربع منفردة، تكون الخيارات 4 ثم 3 ثم 2 ثم 1، فتنتج 24 أخرى.

المجموع 12+72+24=108، ويطابق 4×3×3×3 من عدّ المسار مباشرة. لدينا خمسة تقسيمات، لكن وزن الأول 12 بينما أوزان الأربعة الأخرى 24؛ لا يصح ضرب 5 في وزن موحد 24.

لهذا لا نقسم على مضروب عدد ألوان اللوحة آليًا. هنا 4!=24، وقسمة 108 على 24 تعطي 4.5، مع أن عدد التقسيمات 5. في لوحة الثلاثة كان 24/3!=4 صحيحًا، لأن أوزان المجموعتين والثلاث مجموعات كانت 6 في الحالتين، لا لأن قاعدة القسمة تصلح دائمًا.

إذا كان للتقسيم r مجموعات وللوحة k ألوان، نعطي المجموعات ألوانًا مختلفة بعدد k(k−1)…(k−r+1) عندما r≤k. وإذا كان r>k فلا إسناد يحقق تلك المجموعات. هذه طريقة عد الاختيارات المتتابعة، وليست اشتراطًا أن نستعمل كل لون متاح.

حافة واحدة تنقص العدد دون تغيير الأدنى

أضف AD إلى AB BC CD. صار لدينا دورة A→B→C→D→A بأربع حواف. تبقى كل شروط المسار، ويضاف أن يختلف لونا A وD. أي إسناد صالح للدورة كان صالحًا للمسار قبل هذا القيد.

من تقسيمات لوحة الثلاثة، الوحيد الذي جمع A وD هو {A,D}|{B}|{C}. تمنعه الحافة الجديدة، وتزيل إسناداته الستة. التقسيمات الثلاثة الأخرى ما زالت صحيحة، فيبقى 24−6=18 إسنادًا.

يمكن فحص الستة المزالة مباشرة: اختر لون A وD بثلاث طرق، ثم لون B بطريقتين، ويجب أن يختلف C عن B وعن D، فيبقى اللون الثالث وحده. العدد 3×2×1=6، وهو العدد الذي حسبناه من التقسيم الممنوع.

مع ذلك، أقل عدد ألوان للرسمين هو 2. لون A وC بالأزرق، وB وD بالذهبي؛ ينجح في المسار وفي الحافة AD المضافة. ولا يكفي لون واحد في أي منهما بسبب AB.

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

افحص الإسنادات والتقسيمات كلًا على حدة

في لوحة الثلاثة توجد 3⁴=81 إسنادًا أوليًا لكل رسم، قبل فحص الحواف. راجعناها كلها، فقبل المسار 24 والدورة 18. وسجلنا عدد الألوان المستخدمة فعليًا، لا عدد الألوان المتاحة في اللوحة وحده.

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

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

لا يوجد تلوين للوحتي 0 أو 1 هنا؛ ومع لوحة 2 يوجد إسنادان لكل رسم. ولوحة 4 تعطي 108 للمسار و 84 للدورة. هذه قيم لعدد الطرق، لا عدد الألوان المستخدمة في كل إسناد. الجدول يقارن كذلك لوحة 5 ضمن نطاق الحصر.

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

للمراجعة، ثبت الحواف وأسماء الرؤوس ولوحة الألوان أولًا. حدد هل يسمح بألوان غير مستخدمة، وهل تسجل أسماء الألوان أو العضوية وحدها. افحص اختلاف الجيران، ثم اجمع أوزان التقسيمات المناسبة؛ لا تخلط 24 طريقة مع 24 لونًا أو 24 تقسيمًا.