اصل لانه کبوتری
تعاریف و مفاهیم ریاضی: اصل لانه کبوتری
اصل لانه کبوتری (Pigeonhole Principle)
اگر N+1 یا تعدادی بیشتر کبوتر را در N لانه قرار دهیم، آن وقت لانه ای باید شامل دو یا تعدادی بیشتر کبوتر باشد. به ابهام موجود در عبارت " لانه ای باید شامل.." و "دو یا تعدادی بیشتر..." توجه کنید. این موضوع در حقیقت وجه تمایز اصل لانه کبوتری است که بعضی وقتها به کمک آنها می توانیم به نتیجه گیری هایی کاملا دور از انتظار برسیم، حتی مواقعی که به نظر می رسد اطلاعاتمان کافی نباشد.
اثبات این اصل کاملا ساده است و در آن فقط از شمارش معمولی کبوترها در لانه هایشان استفاده می شود. فرض کنید در هیچ یک از لانه ها بیش از یک کبوتر نباشد. در این صورت روی هم بیش از N کبوتر وجود ندارد و این نتیجه با این فرض که تعداد کبوتر ها N +1 است تناقض دارد بنابراین اصل لانه کبوتری با استفاده از روش اثبات با رسیدن به تناقض، ثابت می شود.
ممکن است بپرسید مسئله زیر چه ربطی به کبوتر ها دارد؟
مسئله:
کیسه ای شامل مهره هایی به دو رنگ سیاه و سفید است. کمترین تعداد مهره هایی که باید بدون نگاه کردن از این کیسه بیرون بیاوریم تا مطمئن باشیم در میان آنها حتما دو مهره همرنگ وجود دارد چندتاست؟
راه حل مسئله:
می توانیم سه مهره از کیسه بیرون بیاوریم. اگر در میان آنها از هر رنگ بیش از یک مهره وجود نداشته باشد، آن وقت روی هم بیش از دو مهره بیرون نیاورده ایم. این نتیجه گیری واضح است و با اینکه سه مهره بیرون آورده ایم تناقض دارد. از طرف دیگر روشن است که بیرون آوردن دو مهره کافی نیست. در اینجا مهره ها نقش کبوتر ها را دارند و رنگهای سیاه و سفید نقش لانه ها را.
مسئه :
یک میلیون درخت کاج در جنگلی روئیده است. می دانیم روی هیچ درخت کاجی بیش از 600000 برگ وجود ندارد. ثابت کنید در این جنگل دو درخت کاج تعداد برگهایشان یکی است.
راه حل مسئله:
یک میلیون کبوتر (درخت کاج) وجود دارد و متاسفانه 600001 لانه که از 0 تا 600000 شماره گذاری شده اند. هر کبوتر (درخت کاج) را در لانه ای قرار می دهیم که شماره اش تعداد برگهای آن درخت است. چون کبوترها بیشتر از لانه ها هستند در لانه ای باید دست کم دو کبوتر (درخت کاج) باشند. اگر در هیچ لانه ای بیش از یکی نباشد، آن وقت بیش از 600001 کبوتر وجود ندارد. اما اینکه دو کبوتر در یک لانه باشد، معنایش این است که تعداد برگهایشان یکی است.
توجه کنید که صورتهای این مسائل هم همان ابهام لانه کبوتری را در خود دارند. درست همین جور مسئله ها هستند که میتوان در بیشتر موارد آنها را با استفاده از اصل لانه کبوتتری حل کرد.
+ نوشته شده در دوشنبه بیست و یکم تیر ۱۳۹۵ ساعت 23:23 توسط ح.محمدی
|
