مبدأ برج الحمام

Pigeonhole Principle

مبدأ ديرشلت Dirichlet أو مبدأ برج الحمام , إذا كان في برج الحمام المكون من n من الأوكار يسكن به n+1 حمامة فلابد أن أحد الأوكار على الأقل يسكن به حمامتين أو أكثرهذا هو المبدأ في صورته البديهية.

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

مبدأ برج الحمام : ينص على أنه إذا كان لديك n+1 شيئا ونريد وضعها في n موضعا فإن أحد هذه المواضع على الأقل يحتوي على شيئين أو أكثر.

صيغة أخرى لمبدأ برج الحمام: إذا كان لدينا kn+1 شيئا ونريد وضعها في n موضعا فإن أحد هذه المواضع على الأقل يحتوي على k+1 شيئا أو أكثر.

مثال1:
أثبت أن كل تجمع فيه n من الأشخاص يوجد بينهما اثنان على الأقل لهما نفس العدد من المعارف (الأصدقاء) داخل هذا التجمع, هنا خذ في الاعتبار أن الشخص x صديق للشخص y يعني أن y صديق x.

للحل أنشئ n موضعا وكل موضع نحدد له رقم وحيد k من بين الأرقام

0, 1, 2, ......., n -2, n -1

ليتجمع في ذلك الموضع الأشخاص الذين لهم k من الأصدقاء. مثلا الموضع ذو الرقم 3 سيجتمع فيه أولئك الذين لكل فرد منهم 3 أصدقاء.

لننظر أولا للموضع رقم صفر: إذا كان هناك شخص على الأقل في هذا الموضع فهذا يعني أنه لا يعرف أحدا وبالتالي لا يعرفه أحد وبالتالي الموضع رقم $n - 1$ ليس فيه أحد لأنه خاص بمن يعرف الكل وبذلك يتوزع n شخصا على $n - 1$ موضعا. أما إذا كان الموضع رقم صفر خاليا فإن n شخصا سيوزعون على بقية المواضع وعددها $n - 1$ .

إذا في كلتا الحالتين سيتوزع n شخصا على $n - 1$ موضعا ومن مبدأ برج الحمام أحد هذه المواضع فيه شخصين أو أكثر, وهذا يبين أن شخصين على الأقل لهما نفس العدد من الأصدقاء.

مثال 2:
إذا أعطيت n عددا صحيحا $a_1 ,a_2 , \ldots ,a_n$ أثبت إنه يوجد صحيحين m, k و $0 \le m < k \le n$ بحيث

$a_{m + 1} + a_{m + 2} + \cdots + a_k$

مضاعف للعدد n.

الحل: خذ المجاميع التالية والتي عددها n

$S_1 = a_1 ,\quad S_2 = a_1 + a_2 ,\quad S_3 = a_1 + a_2 + a_3 ,\quad \cdots ,\quad S_n = a_1 + a_2 + \ldots + a_n$

باقي قسمة كل واحد من هذه المجتميع على n هو أحد الأعداد

$0,\,1,\,2,\, \ldots ,(n - 1)$

إذا كان أحد هذه المجاميع له الباقي صفر, لإغنه من مضاعفات n ونصل للمطلوب. أما إذا لم يوجد مثل هذا المجموع فمن مبدأ برج الحمام , يوجد من ضمن n مجموع السابقة مجموعين على الأقل $S_m ,\;S_k$ لهما نفس الباقي. إذا الفرق بينما

$S_m - S_k = a_{m + 1} + a_{m + 2} + \ldots + a_k$

يقبل القسمة على n وبالتالي مضاعف للعدد n.

مثال 3: حقيبة فيها 6 أقلام زرقاء و 8 حمراء و 11 سوداء, ما هو أقل عدد من الأقلام يجب سحبه عشوائيا من الحقيبة حتى نضمن أن من ضمنه 5 أقلام على الأقل من لون واحد؟
الحل: استخدم الصيغة الثانية لمبدأ برج الحمام. لو سحبنا مجموعة من الأقلام ووزعت على ثلاثة صناديق ملونة بحسب ألوان الأقلام بحيث نضع كل قلم في الصندوق المطابق له في اللون. إذا علينا وفق مبدأ برج الحمام أن نحسب ما عدده 4*3+1 أي 13 قلما.

ماذا لو كان المطلوب عدد الأقلام التي يجب سحبها عشوائيا من الحقيبة حتى نضمن حصولنا على 9 أقلام على الأقل من لون واحد؟
في هذه الحالة n=3,k=8ولكن لاحظ أن هناك حد علوي للأقلام الزرقاء وهو 6 فما زاد عن هذا العدد (أي 2) لن يكون ضروريا فيجب أن يستبعد من الحساب. إذا اقل عدد ممكن من الأقلام المسحوبة هو

8*3+1-(8-2)=25-2=23

طريقة أخرى:
إن أسوأ الاحتمالات الممكنة أن يكون في الأقلام المسحوبة اكبر ما يمكن من الأقلام الزرقاء أي 6 أقلام زرقاء. على افتراض حدوث هذا الاحتمال ننظر حينها إلى الصندوقين الآخرين ونطبق الصيغة الثانية لمبدأ برج الحمام . إذا علينا أن نسحب لهذين الصندوقين 8*2+1 من الأقلام. إذا المجموع الكلي لأقل عدد من الأقلام المسحوبة هو المجموع

(8*2+1)+6=23

العلاقة واضحة بين هذه الصيغة وبين الأولى إذا ما نظرنا للمجموعة X باعتبارها مجموعة الحمام والمجموعة Y هي مجموعة أوكار برج الحمام والدالة f هي التي تخصص لكل حمامة x الوكر الذي تسكنه $f(x)$ من برج الحمام.

مسائل

* كم اقل عدد يجب سحبة من ضمن مجموعة كرات مكونة من 3 خضراء , 5 بيضاء , 9 حمراء , 12 سوداء حتى نضمن الحصول على 6 كرات من نفس النوع على الأقل؟.

* إذا كانت $n_1 ,n_2 , \ldots ,n_k$ أعداد صحيحة موجبة. أثبت أنه إذا وضع $n_1 + n_2 + \ldots + n_k - N + 1$ شيئا داخل N صندوقا فإنه إما الصندوق الأول به على الأقل $n_1$ من هذه الأشياء وإما الصندوق الثاني به على الأقل $n_2$ من هذه الأشياء وإما ...... وإما الصندوق رقم k به على الأقل $n_k$ من هذه الأشياء.

* لدينا A,B قرصين دائريين من البلاستيك. قسم كل واحد منهما إلى 200 قطاع^[م] دائري متطابقة. لونت قطاعات القرص A بالأحمر والأزرق بالتساوي, بمعنى 100 قطاع^[م] عشوائية لونت بالأزرق والقطاعات المتبقية لونت بالأحمر, ولون القرص B عشوائيا باستخدام الأحمر والأزرق كذلك دون اعتبار لعدد الملونة بالأحمر أو الأزرق ووضع القرص B على A متطابقي المركز. اثبت أن هناك وضعا معين للقرص B بحيث تكون عدد القطاعات منه والمطابقة للتي تحتها مباشرة من القرص A لا يقل عن 100 قطاع^[م].

* اثبت أنه من كل n+1 عددا من بين الأعداد 1,2,....,2n يوجد عددان أحدهما يقسم الآخر.

* سبعة من صيادي السمك اصطادوا ما مجموعه 100 سمكة وكل واحد منهم اصطاد عددا مختلفا عن باقي الصيادين برهن على أن ثلاثة من بين السبعة اصطادوا 50 سمكة على الأقل

نبذة عن كاتب الموضوع

$User picture$