تكرار فردي بين الجيران: لماذا تنجح ثلاث أوراق وتفشل أربع؟

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

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

• في التلوين الصحيح يختلف لون طرفي كل حافة. [2] ويكون التلوين Odd Coloring إذا وجد عند كل رأس غير معزول لون يظهر بعدد فردي من المرات بين جيرانه؛ العدد اللوني لهذا الشرط هو أقل عدد ألوان يحققه. [1] نموذجنا محدود وبسيط وغير موجه بلا حلقات أو أوزان، ورؤوسه غير فارغة.
• نعد مرات لون واحد على الأقل في الجوار المفتوح لكل رأس؛ لا نضم لون الرأس نفسه. يجوز أن يكون لون الشاهد مختلفًا من رأس لآخر، ولا نطلب فردية رقم اللون أو فردية كل الأعداد. الرأس المعزول معفى من شرط الجوار لكنه يلون مرة واحدة. ألواننا حرة، وتبديل الأسماء لا يغير تكرارها.
• في النجمة AB AC AD، التلوين A1 B2 C2 D2 صحيح، ويرى المركز اللون 2 ثلاث مرات، وهو عدد فردي. كل ورقة ترى 1 مرة واحدة، فينجح الجميع؛ الأقل 2 بسبب الحافة. تكرار لون الأوراق كلها ليس عائقًا إذا كان عددها فرديًا.
• في النجمة AB AC AD AE، A1 B2 C2 D2 E2 صحيح لكنه يفشل عند A: اللون 2 يتكرر 4 مرات، ولا لون آخر بين جيرانه. أي تلوين صحيح بلونين يكرر لون الأوراق كلها، فلا حل بلونين. A1 B2 C2 D2 E3 يعطي تكراري 3 و 1 عند المركز، فينجح بأقل 3، ولا يطلب اختلاف كل الأوراق.
• الدرجة الفردية الموجبة تضمن وجود تكرار فردي لأن مجموع مرات الألوان فردي، فلا تكون كلها زوجية. لذلك نجمة بخمس أوراق تقبل لونين أيضًا. الدرجة الزوجية لا تمنع الحل: تكرارا 3 و 1 ينجحان، و 2 و 2 يفشلان. عند الدرجة 2 يلزم اختلاف لونَي الجارين؛ لون واحد مرتان زوجي، ولونان مرة واحدة فرديان.
• مع صحة الحواف، درجة 2 تفرض أيضًا قيود مربع الرسم، فيحتاج C4 أربعة وC5 خمسة وC6 ثلاثة، ويحتاج P4 وP5 ثلاثة. الشواهد 1 2 3 4، و 1 2 3 4 5، و 1 2 3 1 2 3، و 1 2 3 1، و 1 2 3 1 2. المثلث 3، والماسة 3 بالشاهد 1 2 3 3؛ مركزاها بدرجة 3 يحققان الفردية تلقائيًا، وجارا كل ورقة مختلفان. K4 يحتاج 4، والحافة مع معزولين وحافتان منفصلتان 2، وأربعة رؤوس بلا حواف 1 مع إعفاء المعزولات.
• حصرنا 64 رسمًا رباعيًا و 960 تقسيمًا بعد تجاهل إعادة أسماء الألوان:337 صحيحًا، منها 256 تحقق شرط التكرار الفردي. اتفق الأقل مع بحث مستقل جرب 1900 تعيينات كاملة مسماة بحساب تكرار كل لون مباشرة. ارتفع الأقل فوق العادي في 27 رسمًا؛ التوزيع 1:1،2:13،3:46،4:4. النجوم من خمسة وستة، وP5 وC5 وC6، خارج الحصر الرباعي.

الفردية في عدد مرات اللون بين الجيران

في التلوين الصحيح يختلف لون طرفي كل حافة. [2] ويكون التلوين Odd Coloring إذا وجد عند كل رأس غير معزول لون يظهر بعدد فردي من المرات بين جيرانه؛ العدد اللوني لهذا الشرط هو أقل عدد ألوان يحققه. [1] نموذجنا محدود وبسيط وغير موجه بلا حلقات أو أوزان، ورؤوسه غير فارغة.

كل رأس يأخذ لونًا واحدًا، ثم ننظر إلى ألوان جيرانه المباشرين. إذا وجد لون بتكرار 1 أو 3 أو 5 وهكذا، تحقق شرط هذا الرأس. التكرار 0 زوجي ولا يكفي، فلا نشهد بلون غير موجود في الجوار.

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

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

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

كلمة فردي تصف عدد مرات الظهور، لا اسم اللون. قد يكون اللون 2 شاهدًا إذا تكرر 3 مرات، وقد يفشل اللون 1 إذا تكرر 4 مرات. تغيير أسماء الألوان معًا يحافظ على أعداد التكرار وصحة الحواف.

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

ثلاث أوراق متفقة اللون تحقق الشرط

النجمة على A B C D لها AB AC AD. المركز A يجاور الأوراق الثلاث، ولا توجد حواف بين الأوراق. اختر A1 B2 C2 D2؛ طرفا كل حافة مختلفان، فالتلوين صحيح.

عند المركز، قائمة ألوان الجيران هي 2 و 2 و 2. يظهر اللون 2 ثلاث مرات، وهذا عدد فردي موجب، فيشهد نجاح A. لا يضر عدم وجود لون آخر في جواره.

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

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

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

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

ورقة إضافية تجعل التكرار زوجيًا

أضف E إلى النجمة، بالحواف AB AC AD AE. اختر A1 B2 C2 D2 E2. بقيت كل الحواف صحيحة، وكل ورقة ترى 1 مرة واحدة عند جارها الوحيد.

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

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

أعطِ A1 B2 C2 D2 E3. عند المركز يظهر 2 ثلاث مرات و 3 مرة واحدة؛ كلاهما شاهد فردي، ويكفي وجود أحدهما. الأوراق لا تتجاور، فتكرار 2 بينها مسموح، وكل ورقة ما زالت ترى 1 مرة واحدة.

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

أما A1 B2 C2 D3 E3، فتكرارا 2 و 3 عند المركز هما 2 و 2؛ كلاهما زوجي، فيفشل رغم استعمال ثلاثة ألوان صحيحة على الحواف. عدد الألوان المستخدم لا يحل محل فحص تكرارات الجوار.

الدرجة الفردية تكفي والزوجية قد تنجح

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

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

في نجمة من ستة رؤوس A B C D E F وحواف AB AC AD AE AF، يعطي A1 وجميع الأوراق 2 تلوينًا صحيحًا. يرى المركز 2 خمس مرات، وكل ورقة 1 مرة واحدة، فيكون الأقل 2 بسبب الحافة.

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

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

عند الدرجة 1 ينجح اللون الوحيد بتكرار 1 تلقائيًا. الدرجة 0 لها الإعفاء المعلن ولا تدخل حجة المجموع الفردي الموجب. لا نخلط المعزول بورقة في الشاهد أو في العد.

درجات المسار والدورة تعطي قيود المربع

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

C4 على A B C D له AB AD BC CD. إضافة اختلاف الجارين تجبر AC وBD أيضًا، فتختلف الأزواج الستة بين الرؤوس الأربعة. الشاهد 1 2 3 4 صالح، وكل جار يظهر مرة واحدة عند كل رأس، والأقل 4.

C5 بحواف AB AE BC CD DE يجبر أزواج AC AD BD BE CE، إضافة إلى حوافه الخمس. غطت القيود كل أزواج الرؤوس الخمسة، فيلزم 5 ويصلح 1 2 3 4 5. الدرجة 2 لم تعطنا حدًا بثلاثة؛ لم نطلب تلوينًا عاديًا فقط.

C6 بحواف AB AF BC CD DE EF يقبل 1 2 3 1 2 3؛ طرفا كل حافة مختلفان، وعند كل رأس جاران بلونين مختلفين يظهر كل منهما مرة. لونان لا يكفيان لأن التناوب يجعل الجارين متفقين؛ فيكون الأقل 3.

P4 بحواف AB BC CD يقبل 1 2 3 1، وP5 بحواف AB BC CD DE يقبل 1 2 3 1 2. كل رأس داخلي يرى جارين مختلفين، وكل طرف يرى جارًا واحدًا؛ والأقل 3 لأن أي رأس داخلي مع جاريه يجبر ثلاثة ألوان مع صحة الحافتين.

النجمة ذات ورقتين AB AC تتبع الفكرة نفسها: A وجاراه B وC يجب أن تختلف ألوانهم، فيلزم 3. لكن النجمة ذات ثلاث أوراق احتاجت 2 فقط؛ لا نعمم قاعدة الدرجة 2 على جوار أكبر.

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

الماسة والمعزول لا يضيفان قيودًا خفية

المثلث AB AC BC يحتاج 3 بسبب صحة كل زوج، والشاهد 1 2 3 يعطي كل رأس جارين مختلفين بتكرار 1 و 1، فيحقق فردية الجوار.

الماسة على A B C D لها AB AC AD BC BD، ولا توجد CD. الشاهد A1 B2 C3 D3 صحيح عاديًا؛ عند A تكرارات الجيران هي 2 مرة واحدة و 3 مرتين، فيشهد اللون 2. وعند B يشهد 1 مرة واحدة رغم تكرار 3 مرتين.

كل من C وD له الجاران A1 وB2، فيرى لونين مرة واحدة لكل منهما. نجح الشاهد عند الجميع بثلاثة ألوان، والمثلث ABC يمنع أقل منها، فيكون الأقل 3. هذا يبين أننا لا نطلب فردية تكرار كل لون في الجوار.

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

حافة AB مع معزولين C وD تقبل A1 B2 C1 D1. الطرفان يريان لونًا مرة واحدة، والمعزولان معفيان من شرط الجوار لكنهما ملونان. الأقل 2 بسبب الحافة؛ لا نضيف لهما ألوانًا جديدة بلا سبب.

وحافتان منفصلتان AB وCD تقبلان A1 B2 C1 D2؛ كل رأس درجته 1 وله شاهد فردي. على أربعة رؤوس بلا حواف يجوز اللون 1 للجميع، والإعفاء يشملهم، فيكون الأقل 1 لا 0.

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

راجعنا التكرارات لا أسماء الألوان الفردية

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

فحصنا صحة الحواف أولًا، فقبلنا 337 تقسيمًا. ثم عدّينا مرات كل لون في جوار كل رأس غير معزول، واشترطنا وجود تكرار فردي واحد على الأقل؛ بقي 256 تقسيمًا. لا نساوي عدد التقسيمات بعدد الرسوم أو الحلول ذات الأقل.

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

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

حسب الأقل، يوجد رسم واحد يحتاج 1، و 13 تحتاج 2، و 46 تحتاج 3، وأربعة تحتاج 4؛ المجموع 64. في 27 رسمًا ارتفع الأقل فوق العدد العادي؛ في الباقي تساويا، ولم يقل لأنه يشترط الصحة.

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

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

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