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

  هذه المقالة عن مبدأ برج الحمام في الرياضات وعلم الحاسوب. لمعانٍ أخرى، طالع برج حمام.

في الرياضيات وعلم الحاسوب، ينص مبدأ برج الحمام (بالإنجليزية: Pigeonhole principle)‏ على أنه إذا تم وضع n عناصر في m خانات بحيث أن n > m، إذن هنالك على الأقل خانة واحدة تحتوي على أكثر من عنصر. يمكن تمثيل هذه المبرهنة ببديهيات من واقع الحياة مثل: «في صف مكون من 13 طالب يوجد على الأقل طالبين ولدوا في نفس الشهر». بالرغم من أن المبدأ يظهر بديهيا، إلا أنه بالإمكان استخدامه لإثبات نتائج ربما غير متوقعة; على سبيل المثال، بأنه هناك شخصين في القاهرة لديهم نفس عدد الشعر على رأسيهما.(انظر إلى الأسفل)

صورة لحمام في خانات. يوجد n = 10 حمامات في m = 9 خانات، ولذلك حسب مبدأ برج الحمام، هنالك على الأقل خانة واحدة تحتوي على أكثر من حمامة واحدة: في هذه الحالة، كلا من الخانتين في الزاويتين في الأعلى تحتويان على حمامتين.

يعتقد بأن أول من أضاف طابعا رسميا على الفكرة هو ديركلي في 1834 تحت اسم Schubfachprinzip («مبدأ الجارور» أو «مبدأ الرف»).

أمثلة

مبدأ برج الحمام يؤكد أنه يكفي سحب 3 جوارب من صندوق فيه جوارب بلونين حتى نحصل على زوج من الجوارب بنفس اللون.

اختيار الجوارب

على افتراض أنه يوجد في صندوق 10 جوارب زرق و 12 جوربًا أصفرًا، احسب العدد الأقصى من الجوارب المطلوب سحبها من الصندوق قبل أن يظهر زوج من الجوارب من نفس اللون. باستخدام مبدأ برج الحمام، للحصول على الأقل على زوج من نفس اللون واختيار خانة لكل لون (m = 2 خانات)، نحتاج إلى ثلاثة جوارب فقط (n = 3 عناصر). في هذا المثال، إذا كان الجورب الأول والثاني من ألوان مختلفة، سيكمل الجورب الثالث زوجا من نفس اللون.

عد الشعر

هناك شخصين في القاهرة يملكون نفس عدد الشعر على رأسيهما: لرأس الإنسان النموذجي يوجد حوالي 150,000 شعرة، ولذلك من المنطقي أن نفترض أنه لا يوجد شخص يملك أكثر من 1,000,000 شعرة على رأسه (خانة 1,000,000 = m). لأنه يوجد أكثر من 1,000,000 في القاهرة (n أكبر من مليون عنصر). إذا خصصنا خانة لكل عدد من الشعر على رأس شخص ما، ووضعنا كل شخص في خانة حسب عدد الشعر على رأسه، يجب أن يكون شخصان على الأقل بنفس الشعر على رأسيهما (n > m).

مسألة يوم الميلاد

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

تعميم لمبدأ برج الحمام

نسخة معممة لمبدأ برج الحمام هي أنه، إذا كان هنالك n عناصر والتي ستخصص لـ m خانات، إذن توجد على الأقل خانة واحدة تحتوي على ما لا يقل عن $\lceil n/m\rceil$ عناصر، حيث أن $\lceil x\rceil$ هي دالة السقف. بالمثل، توجد خانة واحدة تحتوي على ما لا يزيد عن $\lfloor n/m\rfloor$ عناصر، حيث أن $\lfloor x\rfloor$ هي دالة الجزء الصحيح.

انظر أيضًا

• مبرهنة رمزي
• مفارقة بينوكيو

مصادر إضافية

• Grimaldi، Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998. ISBN 0-201-19912-2. pp. 244–248.
• Jeff Miller، Peter Flor، Gunnar Berg، and Julio González Cabillón. "Pigeonhole principle". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics. Electronic document، retrieved November 11، 2006.