محاضرة ( مبدأ برج الحمام )

مبدأ ديرشلت 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 شخصا على اضغط على الصورة لمشاهدتها بالحجم الطبيعي موضعا. أما إذا كان الموضع رقم صفر خاليا فإن n شخصا سيوزعون على بقية المواضع وعددها اضغط على الصورة لمشاهدتها بالحجم الطبيعي.
إذا في كلتا الحالتين سيتوزع n شخصا على اضغط على الصورة لمشاهدتها بالحجم الطبيعي موضعا ومن مبدأ برج الحمام أحد هذه المواضع فيه شخصين أو أكثر, وهذا يبين أن شخصين على الأقل لهما نفس العدد من الأصدقاء.
مثال 2:
إذا أعطيت n عددا صحيحا اضغط على الصورة لمشاهدتها بالحجم الطبيعي أثبت إنه يوجد صحيحين m, k واضغط على الصورة لمشاهدتها بالحجم الطبيعي بحيث
اضغط على الصورة لمشاهدتها بالحجم الطبيعي
مضاعف للعدد n.
الحل: خذ المجاميع التالية والتي عددها n
اضغط على الصورة لمشاهدتها بالحجم الطبيعي
باقي قسمة كل واحد من هذه المجتميع على n هو أحد الأعداد
اضغط على الصورة لمشاهدتها بالحجم الطبيعي
إذا كان أحد هذه المجاميع له الباقي صفر, لإغنه من مضاعفات n ونصل للمطلوب. أما إذا لم يوجد مثل هذا المجموع فمن مبدأ برج الحمام , يوجد من ضمن n مجموع السابقة مجموعين على الأقل اضغط على الصورة لمشاهدتها بالحجم الطبيعي لهما نفس الباقي. إذا الفرق بينما
اضغط على الصورة لمشاهدتها بالحجم الطبيعي
يقبل القسمة على 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) فإنه يوجد عنصرين على الأقل a,b من X بحيث اضغط على الصورة لمشاهدتها بالحجم الطبيعي.
العلاقة واضحة بين هذه الصيغة وبين الأولى إذا ما نظرنا للمجموعة X باعتبارها مجموعة الحمام والمجموعة Y هي مجموعة أوكار برج الحمام والدالة f هي التي تخصص لكل حمامة x الوكر الذي تسكنه اضغط على الصورة لمشاهدتها بالحجم الطبيعي من برج الحمام.

مسائل
* كم اقل عدد يجب سحبة من ضمن مجموعة كرات مكونة من 3 خضراء , 5 بيضاء , 9 حمراء , 12 سوداء حتى نضمن الحصول على 6 كرات من نفس النوع على الأقل؟.
* إذا كانت اضغط على الصورة لمشاهدتها بالحجم الطبيعي أعداد صحيحة موجبة. أثبت أنه إذا وضع اضغط على الصورة لمشاهدتها بالحجم الطبيعي شيئا داخل N صندوقا فإنه إما الصندوق الأول به على الأقل اضغط على الصورة لمشاهدتها بالحجم الطبيعي من هذه الأشياء وإما الصندوق الثاني به على الأقل اضغط على الصورة لمشاهدتها بالحجم الطبيعي من هذه الأشياء وإما ...... وإما الصندوق رقم k به على الأقل اضغط على الصورة لمشاهدتها بالحجم الطبيعي من هذه الأشياء.
* لدينا A,B قرصين دائريين من البلاستيك. قسم كل واحد منهما إلى 200 قطاع دائري[م] متطابقة. لونت قطاعات القرص A بالأحمر والأزرق بالتساوي, بمعنى 100 قطاع عشوائية لونت بالأزرق والقطاعات المتبقية لونت بالأحمر, ولون القرص B عشوائيا باستخدام الأحمر والأزرق كذلك دون اعتبار لعدد الملونة بالأحمر أو الأزرق ووضع القرص B على A متطابقي المركز. اثبت أن هناك وضعا معين للقرص B بحيث تكون عدد القطاعات منه والمطابقة للتي تحتها مباشرة من القرص A لا يقل عن 100 قطاع.
* اثبت أنه من كل n+1 عددا من بين الأعداد 1,2,....,2n يوجد عددان أحدهما يقسم الآخر.
* سبعة من صيادي السمك اصطادوا ما مجموعه 100 سمكة وكل واحد منهم اصطاد عددا مختلفا عن باقي الصيادين برهن على أن ثلاثة من بين السبعة اصطادوا 50 سمكة على الأقل


ماسبق باللغة الانجليزية

Dirichlet principle Dirchillt or pigeonhole principle, if the bathroom was in the tower consisting of n from the dens of the live pigeon n +1 must be at least one of dens live by two white doves or Oktherhma is the principle in its self-evident.

The principle of pigeonhole principles calculations, which may be found in everyday life may be subjected to the position or experience from which the result using this principle, for example, when the number of students in your class 25 students, three of them at least were born in the month Nevshotry that your conclusion, Madam, it is also obvious, However, the codification of the principle of strictly dovecote and the expansion will contribute to the solution of non-obvious issues in the countdown and numeracy Altoavi in general, and we'll display some of them, but first start with the sport of pigeonhole principle.
Pigeonhole principle: states that if you have n +1 and the same thing we want to be n the subject, one of these positions contains at least two or more.
Another version of the pigeonhole principle: if we have kn +1 thing we want to be n the subject, one of these positions contains at least k +1, or something more.
Example 1:
Proved that any groups of n people there at least two of them have the same issue of the knowledge (of friends) within the assembly, here, take into account that the person who is a friend of the person x y means that y x. friend
N has been established to resolve all into the subject we have a single number k of the figures
0, 1, 2, ......., n -2, n -1
To gather the placement of persons who have a k friends. For example, a number 3 position in which those who will meet every one of them 3 friends.
Let us look first to be zero: if there is at least one person in this position, it means he does not know anyone and therefore do not know and therefore a place where no one is special because everyone will know who so divided the people n the subject. If the zero position, the n free people deployed to the rest of the positions.
If in both cases n Sitozaa person is subject to the pigeonhole principle one of those places where two or more, and this shows that at least two people have the same number of friends.
Example 2:
If given an integer n, there proved to be valid m, k, and so
Multiplier of the number n.
Solution: Take the following totals, which the n
The rest of the apportionment of each and every one of these Almojtmie n is one of the numbers
If one of these groups, the rest is zero, because of complications Ignh n and we needed. If there is no such principle is the total dovecote, a total of n within the previous assembled at least have the same rest. If the difference, while
Accept the division of n and therefore the number of multiplier n.
Example 3: the bag 6 and 8 blue pens, red and 11 black, what is the least number of pens to be withdrawn at random from the bag in order to ensure that it is within at least 5 pens of one color?
Solution: Use the second version of the pigeonhole principle. If we pull out a set of pens were distributed to the three colored boxes according to color pencils, so we put all the Registry of the Fund in the corresponding color. If we pigeonhole principle, according to count the number 4 * 3 +1 hardly any 13
What if the required number of pens that should be withdrawn at random from the bag in order to ensure we get at least 9 pens of one color?
In this case, n = 3, k = 8, but noted that there is a limit to the upper blue pens, which is 6 more than this number (ie, 2) would not be necessary, must be excluded from the calculation. If the lowest possible number of pens is withdrawn
8 * 3 +1- (8-2) = 25-2 = 23
Another way:
The worst possibility is that the pens would be withdrawn in the largest possible blue pencils or blue pens 6. Assuming such a possibility, then we look to apply the funds of others and the second version of the pigeonhole principle. If we have to withdraw these funds for the 8 * 2 +1 of the pens. If the total amount of the minimum number of pens is withdrawn Total
(8 * 2 +1) +6 = 23
Third version of the pigeonhole principle
If the function [m] so that (where the mean number of elements of X), there are at least two elements a, b of X so.
A clear relationship between this version and the first, if we consider the group X as a set of the bathroom and the Y is a group nests dovecote and the function f is to be allocated to each pigeon x den mainly from the pigeonhole.
Issues
* How to be the lowest number pulled from the balls in the group consisting of 3 green, 5 white, 9 red, 12 black in order to ensure access to 6 balls of the same type, at least?.
* If the number of false positive. Proved to be nothing if the fund within the N either the first box, at least, of these things, or the Fund at least two of these things, or ...... Or the Fund by the number k of at least these things.
* We have A, B tablets of the plastic ring. Section of each and every one of them to the circular sector 200 [m] are identical. Lownet disk sectors A red and blue equally, in the sense of the 100 random colored blue and the remaining sectors of the colored in red, the color of the disk B using random red and blue as well as without regard to the number of red or blue color and the development of disk A to B Mttabki Center. Proved that there is a particular tablet B so that the number of sectors, and conformity to those directly below it from the CD A not less than 100 sector.
* Proved that every number n +1 from among the numbers 1,2 ,...., 2n there are two issues, one divides the other.
* Seven of the fishermen Astedua a total of 100 fish and each one of them caught a different number from the rest of fishermen demonstrated that three of the seven Astedua at least 50 fish