رقم اللون يفرض مسافة: لماذا لا يجوز تبديل اللونين؟

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

تبديل أرقام الألوان قد يفسد تلوين التعبئة لأن رقم اللون نفسه يحدد عتبة المسافة. في النجمة AB AC AD، ينجح A2 B1 C1 D1: مسافة كل زوج أوراق 2 أكبر من 1. بعد التبديل إلى A1 B2 C2 D2 تظل الحواف صحيحة، لكن المسافة 2 تساوي رقم الأوراق 2 فتفشل. الشرط هو أكبر من الرقم، لا أكبر منه أو مساوٍ له.

• في التلوين الصحيح يختلف لون طرفي كل حافة. [2] أما تلوين التعبئة فيربط رقم اللون بالمسافة: كل رأس يأخذ رقمًا من 1 إلى k، وأي رأسين مختلفين يحملان الرقم i يجب أن تكون المسافة بينهما أكبر من i. العدد اللوني للتعبئة هو أقل k يسمح بذلك. [1] نفحص هنا رسومًا محدودة بسيطة غير موجهة، بلا حلقات أو أوزان، ورؤوسها غير فارغة.
• المسافة عدد حواف أقصر طريق، وليست طول الخط في الصورة. اللون 1 يسمح بمسافة 2، لكن اللون 2 يحتاج مسافة 3 على الأقل، واللون 3 يحتاج 4. نفحص كل زوج متفق اللون، ولا نبحث عن شاهد منفرد في جوار رأس. الأرقام عتبات؛ تبديل الأسماء اعتباطيًا قد يفسد الحل. ضغط الأرقام المستعملة نزولًا مع حفظ ترتيبها آمن لأنه يخفض العتبات، لكنه لا يبرر تجاهل كل إعادة تسمية في الحصر. تعيين النجمة A3 B1 C1 D1 ينجح في لوحة 1 إلى 3، وخفض 3 إلى 2 يعطي الشاهد الأصغر؛ مجرد استعمال رقمين فيه لا يجعل كل تسمية بديلة صحيحة.
• في النجمة AB AC AD، ينجح A2 B1 C1 D1 بأقل 2: كل زوج أوراق مسافته 2 أكبر من 1، و 2 عند المركز وحده. بعد تبديل 1 و 2 يصبح A1 B2 C2 D2 صحيح الحواف أيضًا، لكنه يفشل لأن مسافة كل زوج أوراق 2 ليست أكبر من 2. اللون الواحد ممنوع بسبب الحافة. نجوم الورقتين والأربع والخمس لها الشاهد نفسه: المركز 2 والأوراق 1، والأقل 2.
• في C4 بحواف AB AD BC CD، التوزيع 1 2 1 2 صحيح لكنه يفشل عند B و D باللون 2 ومسافة 2. التوزيع 1 2 1 3 ينجح بأقل 3؛ اللون 1 عند A و C ومسافتهما 2، والبقية منفردة. أي لون 2 أو أعلى لا يتكرر لأن أكبر مسافة في C4 هي 2؛ لون 1 يغطي رأسين على الأكثر، فلا تكفي لوحة 1 و 2 لأربعة رؤوس. تقييد جميع الأزواج بمسافة أكبر من 2، كما في مربع الرسم، يحتاج 4 بدل 3.
• التعبئة تحقق صحة الحواف تلقائيًا: مسافة طرفي الحافة 1، ولا تتجاوز أي رقم لون موجب، فيمنع اتفاقهما؛ لذلك الأقل العادي لا يزيد على أقل التعبئة. العكس يفشل في أمثلة النجمة والدورة. في P4 و P5 و P6 يفرض أي تلوين صحيح بلونين التناوب، فتوجد مسافة 2 داخل الفئة التي تحمل 2 فيفشل؛ الشواهد 1 2 1 3، و 1 2 1 3 1، و 1 2 1 3 1 2 تحقق الأقل 3. ويقبل P4 أيضًا 1 2 3 1، حيث يتكرر 1 عند طرفين مسافتهما 3.
• C5 يقبل 1 2 1 3 4 بأقل 4: لون 1 يغطي اثنين، وكل لون أعلى منه منفرد، فلا تكفي ثلاثة أرقام لخمسة رؤوس. C6 يقبل 1 2 1 3 1 4 بأقل 4؛ في لوحة 1 إلى 3 لا يغطي لون 1 أكثر من ثلاثة، ولون 2 أكثر من اثنين متقابلين، ولون 3 أكثر من واحد؛ وإذا أخذ 1 ثلاثة متناوبة فالبقية مسافاتها 2 ولا يتكرر 2 بينها. المثلث والماسة يحتاجان 3، و K4 يحتاج 4. حافة مع معزولين تقبل 1 2 1 1 بأقل 2، وحافتان منفصلتان 1 2 1 2 بأقل 2؛ نسمح بإعادة الرقم عبر مكونات لا طريق بينها. بلا حواف يكفي 1 للجميع، والأقل 1 لا 0.
• حصرنا 64 رسمًا على أربعة رؤوس بتجربة لوحات 1 إلى k حتى أول k ناجح، لا بتجاهل إعادة أسماء الألوان. جربنا 4406 تعيينات كاملة؛ وجدنا 353 تعيينًا صالحًا عند الحدود الدنيا، وليس هذا عدد كل الحلول لجميع اللوحات. تحقق بحث منفصل من المسافات والقوائم الكاملة. أقل التعبئة 1 لرسم واحد، و 2 لخمسة وعشرين، و 3 لسبعة وثلاثين، و 4 لرسم واحد؛ زاد عن العادي في 15. الدورات والمسارات والنجوم الأكبر والمثلث الأصغر خارج هذا الحصر. لإثبات الأقل نعرض شاهدًا ونستبعد كل لوحة أصغر؛ الأرقام 1 إلى عدد الرؤوس تكفي دائمًا إذا أعطينا كل رأس رقمًا مختلفًا.

رقم اللون عتبة لمسافة أقصر طريق

في التلوين الصحيح يختلف لون طرفي كل حافة. [2] أما تلوين التعبئة فيربط رقم اللون بالمسافة: كل رأس يأخذ رقمًا من 1 إلى k، وأي رأسين مختلفين يحملان الرقم i يجب أن تكون المسافة بينهما أكبر من i. العدد اللوني للتعبئة هو أقل k يسمح بذلك. [1] نفحص هنا رسومًا محدودة بسيطة غير موجهة، بلا حلقات أو أوزان، ورؤوسها غير فارغة.

نحسب المسافة بأقل عدد حواف في طريق يصل الرأسين. الرسم الذي يظهر فيه خط طويل قد يعطي مسافة 1، لأن بين طرفيه حافة واحدة. تقصير الخط أو تدوير الصورة لا يغير المسافات ما دامت الحواف نفسها.

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

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

لوحة 1 إلى k تعني أن الأرقام المسموح بها تبدأ من 1 وتنتهي عند k. تعيين النجمة A3 B1 C1 D1 ينجح في لوحة 1 إلى 3 مع أنه يستعمل رقمين فقط؛ هذا لا يثبت أن الحد الأدنى 3. خفض 3 إلى 2 يعطي الحل الأصغر الذي سنعرضه.

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

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

النجمة تنجح قبل تبديل الرقمين

خذ A مركزًا وأوراق B و C و D، والحواف AB AC AD فقط. كل ورقتين بينهما طريق من حافتين عبر A: B A C، و B A D، و C A D. لا توجد حواف بين الأوراق، ولا نضيفها إلى الصورة.

اختر A2 B1 C1 D1. الأزواج BC و BD و CD متفقة في 1، ومسافة كل منها 2 أكبر من 1؛ كلها مقبولة. الرقم 2 عند A وحده، فلا يوجد زوج من رأسين يحملانه. ينجح التعيين رغم تكرار 1 ثلاث مرات.

أي حافة تمنع إعطاء الجميع 1، لأن طرفيها متفقان ومسافتهما 1 ليست أكبر من 1. الحل السابق ينجح بلوحة 1 و 2، وبعد استبعاد لوحة 1 يثبت الأقل 2.

بدل 1 و 2 في كل الرؤوس، فيصبح A1 B2 C2 D2. طرفا كل حافة مختلفان، فتظل صحة الحواف قائمة. لكن BC و BD و CD بالرقم 2، ومسافة كل زوج 2 تساوي العتبة ولا تتجاوزها، فيفشل التعيين كله.

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

نجمة الورقتين AB AC تقبل A2 B1 C1؛ ونجمة الأربع AB AC AD AE تقبل A2 B1 C1 D1 E1؛ ونجمة الخمس AB AC AD AE AF تقبل A2 B1 C1 D1 E1 F1. زوج الأوراق يظل بمسافة 2 ورقم 1، والمركز منفرد 2؛ الأقل 2 في كل حالة بسبب الحافة.

C4 يحتاج ثلاثة أرقام دون فرض أربعة

الدورة C4 على A B C D لها AB AD BC CD. الأزواج المتجاورة مسافتها 1، والمتقابلان AC و BD مسافتهما 2؛ لا توجد مسافة أكبر من 2 في هذا الرسم.

التوزيع A1 B2 C1 D2 صحيح: طرفا كل حافة مختلفان. AC بالرقم 1 ومسافته 2 أكبر من 1 فيقبل؛ BD بالرقم 2 ومسافته 2 ليست أكبر من 2 فيرفض. نجاح زوج 1 لا يعفي زوج 2 من شرطه.

غيّر D إلى 3، فيصبح A1 B2 C1 D3. AC هو الزوج المتفق الوحيد، ومسافته 2 أكبر من 1. الرقم 2 عند B وحده و 3 عند D وحده، فلا زوج مخالف فيهما. الصورة الداخلية تعرض فشل الزوج BD ثم الحل بعد تغييره، دون إضافة قطري الدورة كحواف.

ثبت الأقل 3: أي رقم 2 أو أعلى لا يتكرر لأن كل مسافات C4 لا تزيد على 2. رقم 1 يغطي رأسين على الأكثر، إذ لا يسمح برأسين متجاورين. لوحة 1 و 2 تغطي على الأكثر رأسين برقم 1 ورأسًا برقم 2، أي ثلاثة رؤوس فقط، لا الأربعة المطلوبة. لوحة 1 تفشل بالحافة أيضًا.

الصحة العادية تقبل 1 2 1 2 بأقل 2. أما اشتراط اختلاف كل رأسين مسافتهما 1 أو 2، وهو قيد مربع الرسم هنا، فيجعل الأزواج الستة مختلفة ويحتاج 4. التعبئة تسمح بتكرار 1 عند المتقابلين، لذلك تحتاج 3 في C4 ولا تساوي هذا القيد الموحد.

المسارات تبين لماذا لا تكفي صحة الحواف

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

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

أي تلوين صحيح للمسار P4 بحواف AB BC CD، عند حصر الأرقام في 1 و 2، يكون متناوبًا: 1 2 1 2 أو 2 1 2 1. في الأول B و D يحملان 2 ومسافتهما 2، وفي الثاني A و C يحملان 2 ومسافتهما 2؛ كلاهما يفشل.

الشاهد 1 2 1 3 ينجح: A و C بالرقم 1 ومسافتهما 2 أكبر من 1، و 2 و 3 منفردان. ويوجد شاهد آخر 1 2 3 1، حيث A و D بالرقم 1 ومسافتهما 3. استبعدنا لوحة 1 بالحافة ولوحة 1 و 2 بالتناوب، فيثبت الأقل 3.

P5 بحواف AB BC CD DE و P6 بحواف AB BC CD DE EF يفرضان التناوب أيضًا عند استعمال رقمين مع صحة الحواف. كل جهة من التناوب فيها زوج بمسافة 2، فتفشل الجهة التي تأخذ 2 أيًا كان اتجاه البداية.

P5 يقبل 1 2 1 3 1: الأزواج المتفقة في 1 مسافاتها 2 أو 4، و 2 و 3 منفردان. P6 يقبل 1 2 1 3 1 2: أزواج 1 مسافاتها 2 أو 4، و B و F بالرقم 2 ومسافتهما 4 أكبر من 2، و 3 عند D وحده. لذلك الأقل 3 في المسارين بعد استبعاد الرقمين.

الدورتان C5 و C6 تحتاجان أربعة

C5 بحواف AB AE BC CD DE أقصى مسافة فيه 2، لذلك كل رقم 2 أو أعلى يظهر مرة واحدة على الأكثر. رقم 1 يغطي رأسين على الأكثر، لأن ثلاثة رؤوس في دورة خماسية لا تكون كلها غير متجاورة. اختيار ثلاثة رؤوس غير متجاورة يتطلب رأسًا آخر بين كل اثنين متتاليين منها على الدورة، أي ستة رؤوس على الأقل؛ الخمسة لا تكفي.

لوحة 1 إلى 3 تغطي على الأكثر 2 مع الرقم 1 و 1 مع 2 و 1 مع 3، أي أربعة رؤوس فقط. لا تكفي خمسة رؤوس؛ واللوحات الأصغر لا تغطي أكثر. الشاهد 1 2 1 3 4 ينجح: A و C بالرقم 1 ومسافتهما 2، والبقية منفردة. الأقل 4، مقابل 3 للصحة العادية.

C6 بحواف AB AF BC CD DE EF أقصى مسافة فيه 3. فئة 3 لا تتكرر، وفئة 2 تضم رأسين على الأكثر، ولا يقبل فيها زوج إلا إذا كان متقابلًا بمسافة 3. فئة 1 تضم ثلاثة رؤوس على الأكثر. لكل رأس مقابل واحد فقط بمسافة 3، فلا توجد ثلاثة رؤوس يمكن إعطاؤها جميعًا 2 مع تحقق الشرط لكل زوج.

لو فرضنا حلًا بلوحة 1 إلى 3 وفيه فئة 1 من رأسين أو أقل، لغطت الفئات على الأكثر 2 و 2 و 1، أي خمسة رؤوس، فلا تكفي الستة. وإذا ضمت فئة 1 ثلاثة رؤوس، فلا بد أن تكون A C E أو B D F، وهي ثلاثية متناوبة.

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

التوزيع 1 2 1 3 1 4 ينجح في C6: A و C و E بالرقم 1، ومسافة كل زوج منها 2 أكبر من 1؛ و 2 و 3 و 4 منفردة. لذلك الأقل 4، مع أن الصحيح العادي يقبل رقمين متناوبين. الشواهد هنا لا تجعل كل دورة تحتاج 4؛ C4 يحتاج 3 كما سبق.

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

المثلث AB AC BC يحتاج 3 لأن كل زوج متجاور، فتختلف الرؤوس الثلاثة. K4 بحواف AB AC AD BC BD CD يحتاج 4 للسبب نفسه عند الأزواج الستة. الشاهد بأرقام مختلفة يجعل شرط كل فئة خاليًا من أي زوج مخالف.

الماسة بحواف AB AC AD BC BD، دون CD، تقبل A2 B3 C1 D1. الزوج CD بالرقم 1 ومسافته 2 عبر A أو B، والبقية أرقام منفردة. المثلث A B C يمنع رقمين، فيثبت الأقل 3 كما في التلوين العادي.

خذ حافة AB ومعزولين C و D، وعيّن A1 B2 C1 D1. طرفا الحافة مختلفان؛ وكل زوج متفق في 1 يوجد طرفاه في مكونات منفصلة بلا طريق يصل بينهما. نسمح بإعادة الرقم عبر هذه المكونات، ولا نطالب المعزول برقم خاص أو بوجود جار يشهد له.

الحافة تمنع لوحة 1، والحل يستخدم 1 و 2، فالأقل 2. وعلى الحافتين المنفصلتين AB و CD ينجح A1 B2 C1 D2؛ زوجا 1 و 2 كلاهما بين المكونين، وفي داخل كل حافة طرفان مختلفان. الأقل 2 أيضًا.

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

نجمتا الأربع والخمس على خمسة وستة رؤوس، والدورتان C5 و C6 والمساران P5 و P6 أكبر من الحصر الرباعي اللاحق. المثلث ونجمة الورقتين أصغر منه. نعرض كل نموذج بحوافه وشاهده وحده الأدنى، ولا نعده رسمًا رباعيًا.

حصر أربعة رؤوس يحافظ على أرقام الألوان

ثبتنا A B C D والأزواج AB AC AD BC BD CD، وأبقينا أو حذفنا كل حافة ممكنة، فحصلنا على 2^6=64 رسمًا مسمى. في كل رسم جربنا لوحة 1، ثم 1 إلى 2، وهكذا حتى أول لوحة تسمح بحل.

لكل لوحة 1 إلى k جربنا كل تعيينات الأرقام على الرؤوس الأربعة، بما فيها التعيينات التي لا تستخدم بعض الأرقام. حسبنا أقصر المسافات، ثم فحصنا كل زوج متفق في الرقم i بالمقارنة الصارمة: المسافة أكبر من i. لم نختزل التعيينات بتجاهل أسماء الفئات، لأن الرقم جزء من الشرط.

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

المجموع 4406 تعيينات كاملة أثناء البحث حتى أول لوحة ناجحة لكل رسم؛ ليس عدد خطوات جزئية أو قياسًا للسرعة. وجدنا 353 تعيينًا صالحًا عند الحدود الدنيا. لم نكمل تعداد كل اللوحات بعد العثور على الأقل، فلا نسمي 353 عدد كل حلول التعبئة لجميع الأرقام.

الأقل 1 في رسم واحد، و 2 في خمسة وعشرين، و 3 في سبعة وثلاثين، و 4 في رسم واحد. زاد أقل التعبئة عن العادي في 15 رسمًا رباعيًا؛ ولم ينقص عنه لأن كل حل للتعبئة صحيح الحواف. ليس هذا توزيعًا لكل أحجام الرسوم.

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

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