ریاضیات | اصل لانه کبوتری

[Ms.Azar]

تعاریف و مفاهیم ریاضی: اصل لانه کبوتری​

​

اصل لانه کبوتری (Pigeonhole Principle)​

اگر N+1 یا تعدادی بیشتر کبوتر را در N لانه قرار دهیم، آن وقت لانه ای باید شامل دو یا تعدادی بیشتر کبوتر باشد. به ابهام موجود در عبارت " لانه ای باید شامل.." و "دو یا تعدادی بیشتر..." توجه کنید. این موضوع در حقیقت وجه تمایز اصل لانه کبوتری است که بعضی وقتها به کمک آنها می توانیم به نتیجه گیری هایی کاملا دور از انتظار برسیم، حتی مواقعی که به نظر می رسد اطلاعاتمان کافی...​

لطفا برای مشاهده کامل مطالب در انجمن ثبت نام کنید.

 

[Ms.Azar]

مسئله:
کیسه ای شامل مهره هایی به دو رنگ سیاه و سفید است. کمترین تعداد مهره هایی که باید بدون نگاه کردن از این کیسه بیرون بیاوریم تا مطمئن باشیم در میان آنها حتما دو مهره همرنگ وجود دارد چندتاست؟

راه حل مسئله:
می توانیم سه مهره از کیسه بیرون بیاوریم. اگر در میان آنها از هر رنگ بیش از یک مهره وجود نداشته باشد، آن وقت روی هم بیش از دو مهره بیرون نیاورده ایم. این نتیجه گیری واضح است و با اینکه سه مهره بیرون آورده ایم تناقض دارد. از طرف دیگر روشن است که بیرون آوردن دو مهره کافی نیست. در اینجا مهره ها نقش کبوتر ها را دارند و رنگهای سیاه و سفید نقش لانه ها را.​

 

[Ms.Azar]

مسئه :
یک میلیون درخت کاج در جنگلی روئیده است. می دانیم روی هیچ درخت کاجی بیش از 600000 برگ وجود ندارد. ثابت کنید در این جنگل دو درخت کاج تعداد برگهایشان یکی است.

راه حل مسئله:
یک میلیون کبوتر (درخت کاج) وجود دارد و متاسفانه 600001 لانه که از 0 تا 600000 شماره گذاری شده اند. هر کبوتر (درخت کاج) را در لانه ای قرار می دهیم که شماره اش تعداد برگهای آن درخت است. چون کبوترها بیشتر از لانه ها هستند در لانه ای باید دست کم دو کبوتر (درخت کاج) باشند. اگر در هیچ لانه ای بیش از یکی نباشد، آن وقت بیش از 600001 کبوتر وجود ندارد. اما اینکه دو کبوتر در یک لانه باشد، معنایش این است که تعداد برگهایشان یکی است.

توجه کنید که صورتهای این مسائل هم همان ابهام لانه کبوتری را در خود...​

لطفا برای مشاهده کامل مطالب در انجمن ثبت نام کنید.