الرياضيات > الرياضيات
عشرة تطبيقات ممتعة لمبدأ Pigeonhole في الرياضيّات
يقدم لنا "علمُ المنطق الرياضي" قواعدَ بسيطةً جداً لفهم واستنتاج قواعدَ جامعةً و لهذا العلم تطبيقاتٌ ممتعة .
بدايةً، لابد من أن نورد توضيحاً مبسطاً عن المبدأ الأساسي في العدّ “Basic-counting-principle”.
يطبّق المبدأ الأساسي في العد عند حساب عدد الطرقِ الممكنةِ لاختيار عدة أشياء، وذلك بحساب ناتج ضرب الطرق الممكنة لكل منها. فمثلاً لاختيار كتابين من ٥ كتب نحسب ناتج ضرب ٥ و ٤. إذاً عددُ الطرق الممكنة هنا يساوي ٢٠ طريقة مختلفة.
الآن، فكرة Pigeonhole ليكن لديك ثلاثةُ طيورٍ من الحمام و عليك ترتيبهم في بيتين فقط .. هل يمكنك ذلك ؟
بالطبع نعم. فلم يرد في المسألة شرطُ أن ينفرد كلُ طير من هذه الطيور ببيت خاص. وبذلك فإن حل هذه المسألة يقتضي أن أحد البيوت سوف يحوي على طائرين بالتأكيد. يمكن تعميم هذا المبدأ لأي عدد صحيح.
إذن فالمبدأ هو " إذا أردت توزيع m طائراً على n بيت فقط، فيجب أن يحتوي بيتٌ واحد ـ على الأقل-ـ على أكثر من طائر واحد إن كان n < m ".
إليك صيغة أخرى لهذا المبدأ " ضمن مجموعة منتهية من القيم الحقيقية، إن القيمة العظمى (Maximum Value) تزيد أو تساوي متوسط تلك القيم (Average Value)"*. قد تبدو هذه الصيغة مختلفة عن الصيغة السابقة ولكن يمكننا إثبات تكافؤ تلك الصيغ.
إن التحديّات التالية قد توضح مبدأ “Pigeonhole” :
1- هل يمكنك أن تكتب 30 كلمة مختلفة على أن لا تبدأ أي كلمتين منهم بنفس الحرف؟
المجموعة المؤلفة من 30 كلمة لا بد أن تغطي الأحرف الأبجديةً التسع والعشرين(2) جميعاً، الكلمة المتبقية لابد من أنها ستبدأ بواحد من الأحرف المستعملة مسبقاً. لذا فإن كلمتين سوف تبدآن بنفس الحرف بشكل أكيد .
2- هل ستجد في مدينة نيويورك شخصين ممن لديهم شعر رأس ـ يملكان العدد نفسه من الشعر على رؤوسهم؟
رأس الإنسان يمكن أن يحتوي مئات الألوف من الشعرات، وعلى الأكثر 500،000 شعرة. وبما عدد سكان مدينة نيويورك يبلغ الملايين لذا فمن المؤكد أن يشترك شخصان على الأقل بنفس العدد تماما من الشعر. طبعاً يمكنك أن تبدأ بعدّ شعرات رأس ملايين البشر هناك وسنكون أكثر من سعداء إن أثبتت خطأ هذا المبدأ !.
3- هل سيشترك شخصين على الأقل ممن يقرأون هذه المقال بتاريخ الميلاد نفسه؟
عدد أيام السنة هو 366 يوم في السنة (باعتبار عدد أيام السنة الكبيسة) وفإن زاد عدد قراء هذا المقال عن 367 شخصاً، فإن اثنين من القراء المحظوظين سيكونان قد خُلقا بنفس التاريخ .
4- إن كنت في حفلٍ يحضره 1000 شخص مثلاً، فيمكنك أن تتحدى صديقك بهذه العبارة
"هنالك شخصان على الأقل يتشاركان الحرف الأول و الأخير من أسماءهم".
عدد الحالات الممكنة لاختيار الحرف الأول و الأخير لأي شخص يمكن حسابه بمعرفة ناتج جداء 29 حرفاً بنفسها، أي أن عدد الأسماء المختلفة التي يمكن تركبيها بأي ترتيب تريد هو 29*29=841.
لذا في قاعة كبرى تتسع لـ1000 شخص مثلاً، فليس من الصعب أن تجد شخصين على الأقل يشتركان بالحرف الأول والأخير من أسماءهم.
5- خدعةٌ سحريةٌ بسيطة: تحضر أوراق اللعب الـ52، وتتحدى أخاك الصغير بأنه يمكنك وبدون النظر للبطاقات أن تختار 5 بطاقات فقط بحيث أن يكون لاثنتين منها على الأقل النمط نفسه.
عدد أنماط الموجود الممكنة هو 4، لذا فإن خمس بطاقات ستكون حاسمة بأن إحدى البطاقات ستعود لنمط واحد من الأنماط الأربعة. ودائماً بحسب مبدأ Pigeonhole .
أرجو أن يكون هذا المبدأ قد توضح بما فيه الكفاية لتقوم أنت ببناء التحدي التالي:
6- تحديك الخاص: صندوق يحتوي على 10 كرات بيضاء و 10 كرات سوداء. ما هو عدد الكرات الأدنى الذي ينبغي أن تتناوله من الصندوق، دون النظر فيه، لتضمن حصولك على كرتين من نفس اللون؟
7- ليكن لدينا مجموعةَ أعدادٍ طبيعيةٍ من 1 إلى 8. هل يمكنك أن تختار أيّ خمسِ بطاقاتٍ منها على أن لا يكون مجموع أي اثنتين منها 9 ؟
لدينا 4 أزواج من الأرقام مجموعها يساوي 9 و هي : 1 و 8 ، 2 و7 ، 3 و 6 ، 4 و 5 .
الحالات الممكنة لاختيار البطاقة الأولى هي {1،2،3،4،5،6،7،8}، لنفترض أنك اخترت {1}، فإن الحالات الممكنة لاختيار الأربعة الباقيين هي {2،3،4،5،6،7}، ولاحظ أننا حذفنا 8 ذلك لكي لايكون المجموع 9. ولنختر رقماً ثانياً {7} وبذلك فسيختفي الزوج 2 و7 من الحالات الممكنة لتصبح {3،4،5،6} .
أصبحت الخيارات محدودة لاختيار 3 بطاقات أخرى. تلاحظ أن لديك زوجين فقط لتختار منها. إذا لابد من أنك ستضطر للاختيار من هذه الأزواج. ودائماً حسب مبدأ Pigeongole فإن اثنتين من البطاقات الخمس لابد من أن يكون مجموعها يساوي 9.
الأمثلة التالية قد تكون أكثر تشويقاً.
8- لنفترض أن عدد الطلبة في جامعةٍ سورية 2000 طالب. وأن فيها طلبة من جميع المحافظات الأربعة عشر. فما هو أدنى حد أعلى Supremum" (3)" لعدد الطلبة المنتمين لنفس المحافظة؟
لنبدأ بتوضيح معنى "أدنى حد أعلى" بحسب مثالنا. لاشك أن لدينا طرقأً كثيرة لتوزيع 2000 طالب على 14 محافظة. وفي أي طريقة نقوم بذلك التوزيع فلابد من يكون لدينا محافظةً ما (أو أكثر) لديها أكبر عدد ممكن من الطلبة. إن استقرأنا جميع تلك الطرق فإنه لن تجد طريقةً تضمن لك أن يكون الحد الأعلى لأي محافظة أقل من " أدنى حد أعلى". فهو القيمة الأصغر لجميع الحدود العليا.
لنقوم بحساب هذه القيمة، سنعتمد هنا على الصيغة الثانية للمبدأ، لذا فإن الحد الأعلى (Maximum) لن يكون أصغر من المعدل (Average) وهو 2000/14= 142.7 طالب. ولأنه لن يكون لديك (0.7) فلا بد أن أدنى حد أعلى لعدد الطلبة القادمين من أي محافظة لن يقل عن 143 طالباً.
9- يمكن أن نغطي رقعة الشطرنج بـ ٣٢ لوحاً من ألواح الدومينوز. ولكن هل يمكن أن تغطي رقعة الشطرنج الموضحة في الشكل التالي بـ ٣١ لوحاً من الدومينوز؟
خذ وقتك بحل هذه المسألة، وسنعرض الجواب في آخر المقال.
10- ضمن أي مجموعة من 6 أشخاص، فإن لديك إحدى حالتين إما أن تجد 3 أصدقاء مشتركين أو 3 أشخاص غرباء عن بعضهم البعض (يمكنكم مراجعة مقالنا السابق عن مسألة الأصدقاء والغرباء هنا)
لتوضيح هذه الحالة يمكننا تمثيل الأشخاص بنقاط والأضلاع تمثّل الصداقة. كيفما رُسم الشكل فلابد من وجود إما مجموعة من 3 الأصدقاء، أو وجود 3 غرباء.
يمكن لهذا المبدأ أن يتعقد أكثر، ولكن تطبيقاته تكاد تكون يومية في الكثير من الحالات. أرجو أن تشاركنا ببعض الأمثلة التي يمكنك أن تعتمد بها على مبدأنا هذا باتخاذ القرار المناسب.
حل التحدي التاسع:
بالطبع لايمكنك تغطية رقعة الشطرنج المعدلة بـ ٣١ لوحاً من ألواح الدومينوز مهما حاولت. والسبب إن كل لوحٍ من الألواح يغطي مربعين متجاورين أي أنه يغطي مربعاً فاتحاً وآخر غامق. فإن أزلت مربعين فاتحين فلا بد من أن تُوجد مربعين غامقين متجاورين عوضاً عنها، وبحسب نفي المبدأ فلا يمكنك تغطية المربعات بألواح الدومينوز.
المصادر:
* صياغة هذه القاعدة بلغة البروفيسور: Dijkstra
(2) باعتبار أن الهمزة حرف من اللغة العربية.
(3) هنا
(5 ) مسألة الأصدقاء والغرباء: