الفترات: هل تلاقي كل زوج يضمن نقطة للجميع؟

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

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

• في رسم الفترات، يمثل كل رأس فترة على خط الأعداد، وتتصل رؤوس مختلفة حين تتقاطع فتراتها تقاطعًا غير فارغ. [1] نثبت هنا فترات مغلقة، ونعامل أسماء المدخلات المختلفة كرؤوس مختلفة حتى لو تطابقت حدود فترتين.
• الفترات A=[0,4] وB=[2,6] وC=[3,5] وD=[6,8] تعطي الحواف AB AC BC BD. للثلاث A B C تقاطع كلي [3,4]؛ أما الأربع فلا تتلاقى كل أزواجها، وتقاطعها الكلي فارغ.
• B وD تتقاطعان في النقطة6 وحدها. النقطة المشتركة تكفي لحافة؛ لا نطلب تقاطعًا ذا طول موجب. لو استبعدنا6 من طرفي الفترتين فلن تبقى هذه النقطة المشتركة.
• ضع L أكبر بداية وR أصغر نهاية. اختر فترتين تحققان الحدين؛ تلاقيهما يفرض L≤R، ولذلك تنتمي L إلى الجميع. إذا جاءت القيمتان من الفترة نفسها، يفرض عدم فراغها الشرط نفسه.
• هذا هو شرط التلاقي في بعد واحد من مبرهنة هيلي للمجموعات المحدبة المغلقة المحدودة؛ عدد هيلي في البعد1 هو2. [2] [3] سنثبت الحالة التي نحتاجها مباشرة، لعائلة منتهية غير فارغة من فترات مغلقة غير فارغة.
• الشرط يتعلق بفترة واحدة لكل مدخل. المجموعات [0,1]∪[4,5] و[0,1]∪[2,3] و[2,3]∪[4,5] تتلاقى زوجيًا ولا تتقاطع كلها؛ هي اتحادات قطعتين، لا ثلاث فترات منفردة.
• راجعنا3375 ثلاثية مرتبة من15 فترة مغلقة صحيحة الطرفين داخل0..4، أي10125 مقارنة زوجية و3375 تقاطعًا كليًا. في1443 ثلاثية تحقق التلاقي الزوجي والتقاطع الكلي معًا. هذا فحص محدود؛ البرهان العام لا يعتمد عليه.

حدد نوع الفترة قبل رسم الحواف

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

الفترة المغلقة [a,b] تضم كل عدد حقيقي x يحقق a≤x≤b، بما في ذلك الطرفان. نطلب a≤b؛ وعند التساوي تصبح الفترة نقطة واحدة، وتظل غير فارغة. أسماء A وB وC وD تميز المدخلات، وليست مواضع على المحور.

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

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

أربع فترات وحواف معلنة

ثبت الفترات A=[0,4] وB=[2,6] وC=[3,5] وD=[6,8]. يتقاطع A وB في [2,4]، وA وC في [3,4]، وB وC في [3,5]. هذه الأزواج الثلاثة تعطي مثلثًا بين A وB وC.

أما B وD فيلتقيان عند6. A وD منفصلتان لأن4 أصغر من6؛ وC وD منفصلتان لأن5 أصغر من6. لذلك قائمة حواف الرسم AB AC BC BD فقط: أربعة رؤوس وأربع حواف، دون AD أوCD.

تقاطع A وB وC جميعًا هو [3,4]. العدد3 مثلًا ينتمي إلى الثلاثة، وكذلك4 وكل ما بينهما. لا يلزم أن تكون التقاطعات الزوجية متساوية؛ لدينا [2,4] و[3,4] و[3,5]، ومع ذلك يوجد تقاطع كلي.

إذا أضفنا D إلى سؤال التقاطع الكلي، أصبحت أكبر بداية6 وأصغر نهاية4. لا عدد يحقق6≤x≤4، فتكون النتيجة فارغة. هذه ليست مخالفة للقاعدة، لأن العائلة ذات الأربع لم تحقق التلاقي الزوجي أصلًا.

الصورة الرئيسية ستعرض الفترات على محور مشترك مع منطقة [3,4] المظللة للثلاثة الأولى، ثم رسم الحواف المحسوب. تشابه ارتفاع الخطوط في الصورة لا يثبت التلاقي؛ نرجع إلى الحدود المعطاة على المحور.

نقطة النهاية تكفي لوجود تقاطع

في B=[2,6] وD=[6,8]، تكون أكبر البداية6 وأصغر النهاية6. التقاطع [6,6] هو مجموعة تضم6 وحدها. طول هذه الفترة صفر، لكنها ليست المجموعة الفارغة، ولذلك نثبت الحافة BD.

لا تستخدم شرط L<R بدل L≤R للفترات المغلقة؛ الشرط الصارم سيفقد حالة التلامس. العبرة بوجود عنصر مشترك، لا بمساحة التظليل أو سماكة الخط الذي يرسمه البرنامج.

للمقارنة فقط، لو أخذنا B=(2,6) وD=(6,8)، لاستبعدت الأولى6 من يمينها والثانية6 من يسارها، ولن يوجد عنصر مشترك. هذا تغيير في المدخل، وليس إعادة رسم للفترتين المغلقتين نفسيهما.

نقتصر في بقية البرهان على الفترات المغلقة. لا نعمم اختبار L≤R بصيغته هذه على أطراف مفتوحة أو نصف مفتوحة دون فحص شمول الطرف عند التساوي. ولم نثبت هنا أن كل حكم عن التلاقي يتوقف على الإغلاق وحده.

أكبر بداية وأصغر نهاية تعطيان البرهان

هذا هو شرط التلاقي في بعد واحد من مبرهنة هيلي للمجموعات المحدبة المغلقة المحدودة؛ عدد هيلي في البعد1 هو2. [2] [3] سنثبت الحالة التي نحتاجها مباشرة، لعائلة منتهية غير فارغة من فترات مغلقة غير فارغة.

اكتب فترات العائلة [a_i,b_i]. لأنها منتهية وغير فارغة، توجد بداية أكبر من سائر البدايات، نسميها L، ونهاية أصغر من سائر النهايات، نسميها R. توجد فترات تحقق هذين الحدين؛ لا نستبدل الأكبر والأصغر بقيم غير متحققة.

اختر الفترة التي بدايتها L، والفترة التي نهايتها R. إذا كانتا مختلفتين، فإن فرض التلاقي الزوجي يعطي عددًا y فيهما. وجوده في الأولى يفرض L≤y، ووجوده في الثانية يفرض y≤R؛ إذن L≤R.

إذا حققت فترة واحدة الحدين معًا، فعدم فراغها يعطي L≤R مباشرة. هذه الحالة تشمل عائلة ذات فترة واحدة، ولا تحتاج اختراع زوج من مدخلين مختلفين داخلها.

كل فترة تبدأ عند قيمة لا تزيد على L، وتنتهي عند قيمة لا تقل عن R. وبما أن L≤R، فإن العدد L يقع داخل كل فترة. بل كل x بين L وR يقع فيها كلها، وأي عدد في الجميع يجب أن يكون بين هذين الحدين. لذلك التقاطع الكلي بالضبط [L,R].

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

اتحاد قطعتين يغير السؤال

خذ ثلاث مجموعات جديدة: U=[0,1]∪[4,5]، وV=[0,1]∪[2,3]، وW=[2,3]∪[4,5]. كل منها يجمع قطعتين منفصلتين، فلا يعامل كفترة واحدة تمتد بين أصغر حد وأكبر حد.

تقاطع U وV هو [0,1]، وتقاطع V وW هو [2,3]، وتقاطع U وW هو [4,5]. لكن لا جزء من هذه الأجزاء الثلاثة يدخل المجموعات جميعًا، فتقاطع الثلاث فارغ. التلاقي الزوجي وحده لا يكفي لهذا النوع من المدخلات.

استبدال U بالفترة [0,5] يملأ الفجوة المفتوحة (1,4) بأعداد لم تكن ضمنها. سيغير ذلك التقاطعات، لذلك لا نستخرج فترة بديلة من الحدود القصوى ثم نزعم أننا حسبنا المجموعات الأصلية.

رسم تقاطع هذه المجموعات هو مثلث على U وV وW. لا نستنتج أن المثلث ليس رسم فترات: المثلث نفسه يمكن تمثيله بثلاث فترات مغلقة متلاقية، مثل A وB وC السابقة. الفرق بين تمثيل معطى باتحادات قطع وبين إمكان تمثيل الرسم بفترات مفردة.

حصر صغير ومراجعة قابلة للتكرار

كونّا15 فترة [a,b] من الأعداد الصحيحة0 إلى4 مع a≤b؛ تشمل فترات النقطة الواحدة. أخذنا كل ثلاثية مرتبة منها مع السماح بتكرار الحدود، فكان عدد المدخلات15³=3375. كل موضع في الثلاثية مدخل مسمى مستقل.

لكل ثلاثية قارنا الأزواج الثلاثة باختبار أكبر البداية≤أصغر النهاية، ثم حسبنا التقاطع الكلي بالحدين L وR. وراجعنا النتيجة بطريقة أخرى: حولنا كل فترة إلى مجموعة الأعداد الصحيحة داخلها، ثم تقاطعنا المجموعات مباشرة.

هذه الطريقة الثانية تصلح لهذا الحصر لأن الأطراف كلها صحيحة: أي تقاطع مغلق غير فارغ بينها يحتوي طرفه الأدنى الصحيح. ليست شبكة الأعداد الصحيحة اختبارًا كافيًا لفترات حقيقية اعتباطية؛ مثل [0.2,0.4] غير فارغة ولا تحوي عددًا صحيحًا.

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

للمراجعة العملية، اكتب نوع الطرفين وحدود كل فترة أولًا. احسب L وR، ثم راجع شرطهما: L<R تقاطع ممتد، وL=R نقطة مشتركة في نطاق الفترات المغلقة، وL>R تقاطع فارغ. أعد فحص فرض تلاقي كل زوج قبل تقديم عائلة فارغة التقاطع كاعتراض على القاعدة.