سومة ليبية
05-08-2010, 03:31 AM
Pigeonhole Principle
مبدأ ديرشلت Dirichlet أو مبدأ برج الحمام , إذا كان في برج الحمام المكون من n من الأوكار يسكن به n+1 حمامة فلابد أن أحد الأوكار على الأقل يسكن به حمامتين أو أكثرهذا هو المبدأ في صورته البديهية.
يعتبر مبدأ برج الحمام من المبادئ الحسابية التي قد ترد في الحياة اليومية وقد تتعرض لموقف أو تجربة وتستخلص منها النتيجة[م] ([Only Registered Users Can See Links]) باستخدام هذا المبدأ فعلى سبيل المثال حينما يكون عدد طلاب فصلك 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 أصدقاء.
لننظر أولا للموضع رقم صفر: إذا كان هناك شخص على الأقل في هذا الموضع فهذا يعني أنه لا يعرف أحدا وبالتالي لا يعرفه أحد وبالتالي الموضع رقم [Only Registered Users Can See Links] ليس فيه أحد لأنه خاص بمن يعرف الكل وبذلك يتوزع n شخصا على [Only Registered Users Can See Links] موضعا. أما إذا كان الموضع رقم صفر خاليا فإن n شخصا سيوزعون على بقية المواضع وعددها [Only Registered Users Can See Links]
إذا في كلتا الحالتين سيتوزع n شخصا على [Only Registered Users Can See Links] موضعا ومن مبدأ برج الحمام أحد هذه المواضع فيه شخصين أو أكثر, وهذا يبين أن شخصين على الأقل لهما نفس العدد من الأصدقاء.
مثال 2:
إذا أعطيت n عددا صحيحا [Only Registered Users Can See Links] أثبت إنه يوجد صحيحين m, k و[Only Registered Users Can See Links] بحيث
[Only Registered Users Can See Links]
مضاعف للعدد n.
الحل: خذ المجاميع التالية والتي عددها n
[Only Registered Users Can See Links]
باقي قسمة كل واحد من هذه المجتميع على n هو أحد الأعداد
[Only Registered Users Can See Links]
إذا كان أحد هذه المجاميع له الباقي صفر, لإغنه من مضاعفات n ونصل للمطلوب. أما إذا لم يوجد مثل هذا المجموع فمن مبدأ برج الحمام , يوجد من ضمن n مجموع السابقة مجموعين على الأقل [Only Registered Users Can See Links] لهما نفس الباقي. إذا الفرق بينما
[Only Registered Users Can See Links]
يقبل القسمة على 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
الصيغة الثالثة لمبدأ برج الحمام
إذا كانت [Only Registered Users Can See Links] دالة[م] ([Only Registered Users Can See Links]) بحيث [Only Registered Users Can See Links] (حيث [Only Registered Users Can See Links] تعني عدد عناصر X) فإنه يوجد عنصرين على الأقل a,b من X بحيث [Only Registered Users Can See Links]
العلاقة واضحة بين هذه الصيغة وبين الأولى إذا ما نظرنا للمجموعة X باعتبارها مجموعة الحمام والمجموعة Y هي مجموعة أوكار برج الحمام والدالة f هي التي تخصص لكل حمامة x الوكر الذي تسكنه [Only Registered Users Can See Links] من برج الحمام.
مسائل
* كم اقل عدد يجب سحبة من ضمن مجموعة كرات مكونة من 3 خضراء , 5 بيضاء , 9 حمراء , 12 سوداء حتى نضمن الحصول على 6 كرات من نفس النوع على الأقل؟.
* إذا كانت [Only Registered Users Can See Links] أعداد صحيحة موجبة. أثبت أنه إذا وضع [Only Registered Users Can See Links] شيئا داخل N صندوقا فإنه إما الصندوق الأول به على الأقل [Only Registered Users Can See Links] من هذه الأشياء وإما الصندوق الثاني به على الأقل [Only Registered Users Can See Links] من هذه الأشياء وإما ...... وإما الصندوق رقم k به على الأقل [Only Registered Users Can See Links] من هذه الأشياء.
* لدينا A,B قرصين دائريين من البلاستيك. قسم كل واحد منهما إلى 200 قطاع دائري[م] ([Only Registered Users Can See Links]) متطابقة. لونت قطاعات القرص A بالأحمر والأزرق بالتساوي, بمعنى 100 قطاع عشوائية لونت بالأزرق والقطاعات المتبقية لونت بالأحمر, ولون القرص B عشوائيا باستخدام الأحمر والأزرق كذلك دون اعتبار لعدد الملونة بالأحمر أو الأزرق ووضع القرص B على A متطابقي المركز. اثبت أن هناك وضعا معين[م] ([Only Registered Users Can See Links]) للقرص B بحيث تكون عدد القطاعات منه والمطابقة للتي تحتها مباشرة من القرص A لا يقل عن 100 قطاع.
* اثبت أنه من كل n+1 عددا من بين الأعداد 1,2,....,2n يوجد عددان أحدهما يقسم الآخر.
* سبعة من صيادي السمك اصطادوا ما مجموعه 100 سمكة وكل واحد منهم اصطاد عددا مختلفا عن باقي الصيادين برهن على أن ثلاثة من بين السبعة اصطادوا 50 سمكة على الأقل
مبدأ ديرشلت Dirichlet أو مبدأ برج الحمام , إذا كان في برج الحمام المكون من n من الأوكار يسكن به n+1 حمامة فلابد أن أحد الأوكار على الأقل يسكن به حمامتين أو أكثرهذا هو المبدأ في صورته البديهية.
يعتبر مبدأ برج الحمام من المبادئ الحسابية التي قد ترد في الحياة اليومية وقد تتعرض لموقف أو تجربة وتستخلص منها النتيجة[م] ([Only Registered Users Can See Links]) باستخدام هذا المبدأ فعلى سبيل المثال حينما يكون عدد طلاب فصلك 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 أصدقاء.
لننظر أولا للموضع رقم صفر: إذا كان هناك شخص على الأقل في هذا الموضع فهذا يعني أنه لا يعرف أحدا وبالتالي لا يعرفه أحد وبالتالي الموضع رقم [Only Registered Users Can See Links] ليس فيه أحد لأنه خاص بمن يعرف الكل وبذلك يتوزع n شخصا على [Only Registered Users Can See Links] موضعا. أما إذا كان الموضع رقم صفر خاليا فإن n شخصا سيوزعون على بقية المواضع وعددها [Only Registered Users Can See Links]
إذا في كلتا الحالتين سيتوزع n شخصا على [Only Registered Users Can See Links] موضعا ومن مبدأ برج الحمام أحد هذه المواضع فيه شخصين أو أكثر, وهذا يبين أن شخصين على الأقل لهما نفس العدد من الأصدقاء.
مثال 2:
إذا أعطيت n عددا صحيحا [Only Registered Users Can See Links] أثبت إنه يوجد صحيحين m, k و[Only Registered Users Can See Links] بحيث
[Only Registered Users Can See Links]
مضاعف للعدد n.
الحل: خذ المجاميع التالية والتي عددها n
[Only Registered Users Can See Links]
باقي قسمة كل واحد من هذه المجتميع على n هو أحد الأعداد
[Only Registered Users Can See Links]
إذا كان أحد هذه المجاميع له الباقي صفر, لإغنه من مضاعفات n ونصل للمطلوب. أما إذا لم يوجد مثل هذا المجموع فمن مبدأ برج الحمام , يوجد من ضمن n مجموع السابقة مجموعين على الأقل [Only Registered Users Can See Links] لهما نفس الباقي. إذا الفرق بينما
[Only Registered Users Can See Links]
يقبل القسمة على 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
الصيغة الثالثة لمبدأ برج الحمام
إذا كانت [Only Registered Users Can See Links] دالة[م] ([Only Registered Users Can See Links]) بحيث [Only Registered Users Can See Links] (حيث [Only Registered Users Can See Links] تعني عدد عناصر X) فإنه يوجد عنصرين على الأقل a,b من X بحيث [Only Registered Users Can See Links]
العلاقة واضحة بين هذه الصيغة وبين الأولى إذا ما نظرنا للمجموعة X باعتبارها مجموعة الحمام والمجموعة Y هي مجموعة أوكار برج الحمام والدالة f هي التي تخصص لكل حمامة x الوكر الذي تسكنه [Only Registered Users Can See Links] من برج الحمام.
مسائل
* كم اقل عدد يجب سحبة من ضمن مجموعة كرات مكونة من 3 خضراء , 5 بيضاء , 9 حمراء , 12 سوداء حتى نضمن الحصول على 6 كرات من نفس النوع على الأقل؟.
* إذا كانت [Only Registered Users Can See Links] أعداد صحيحة موجبة. أثبت أنه إذا وضع [Only Registered Users Can See Links] شيئا داخل N صندوقا فإنه إما الصندوق الأول به على الأقل [Only Registered Users Can See Links] من هذه الأشياء وإما الصندوق الثاني به على الأقل [Only Registered Users Can See Links] من هذه الأشياء وإما ...... وإما الصندوق رقم k به على الأقل [Only Registered Users Can See Links] من هذه الأشياء.
* لدينا A,B قرصين دائريين من البلاستيك. قسم كل واحد منهما إلى 200 قطاع دائري[م] ([Only Registered Users Can See Links]) متطابقة. لونت قطاعات القرص A بالأحمر والأزرق بالتساوي, بمعنى 100 قطاع عشوائية لونت بالأزرق والقطاعات المتبقية لونت بالأحمر, ولون القرص B عشوائيا باستخدام الأحمر والأزرق كذلك دون اعتبار لعدد الملونة بالأحمر أو الأزرق ووضع القرص B على A متطابقي المركز. اثبت أن هناك وضعا معين[م] ([Only Registered Users Can See Links]) للقرص B بحيث تكون عدد القطاعات منه والمطابقة للتي تحتها مباشرة من القرص A لا يقل عن 100 قطاع.
* اثبت أنه من كل n+1 عددا من بين الأعداد 1,2,....,2n يوجد عددان أحدهما يقسم الآخر.
* سبعة من صيادي السمك اصطادوا ما مجموعه 100 سمكة وكل واحد منهم اصطاد عددا مختلفا عن باقي الصيادين برهن على أن ثلاثة من بين السبعة اصطادوا 50 سمكة على الأقل