سه شنبه ۱۳ آذر ۱۴۰۳
پنجشنبه ۲۴ مرداد ۱۳۹۲ 26231 2 19

اگر N+1 یا تعدادی بیشتر کبوتر را در  N لانه  قرار دهیم، آن وقتلانه ای باید شامل دو یا تعدادی بیشتر کبوتر باشد.

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

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

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

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

ممکن است بپرسید مسئله زیر چه ربطی به کبوتر ها دارد؟

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

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

توجه کنید که صورتهای این مسائل هم همان ابهام لانه کبوتری را در خود دارند. درست همین جور مسئله ها هستند که میتوان در بیشتر موارد آنها را با استفاده از اصل لانه کبوتتری حل کرد.
 

آی هوش: گنجینه دانستنی ها و معماهای هوش و ریاضی

نظراتی که درج می شود، صرفا نظرات شخصی افراد است و لزوماً منعکس کننده دیدگاه های آی هوش نمی باشد.
آی هوش: مرجع مفاهیم هوش و ریاضی و انواع تست هوش، معمای ریاضی و معمای شطرنج
 
در زمینه‌ی انتشار نظرات مخاطبان، رعایت برخی موارد ضروری است:
 
-- لطفاً نظرات خود را با حروف فارسی تایپ کنید.
-- آی هوش مجاز به ویرایش ادبی نظرات مخاطبان است.
-- آی هوش از انتشار نظراتی که در آنها رعایت ادب نشده باشد معذور است.
-- نظرات پس از تأیید مدیر بخش مربوطه منتشر می‌شود.
 
 
 
 
  1. یکتا دوشنبه ۱۷ آذر ۱۳۹۳ --- ۲۱:۱۳:۰۰

    میشه بگیدکاربرد اینا توزندگی چیه؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟

    1. bnvgerwe چهارشنبه ۲۴ مرداد ۱۳۹۷ --- ۱۷:۰۲:۲۵

      این اصل توی نظریه اعداد کاربرد داره و خود نظریه اعداد هم توی رمزنگاری اطلاعات. شما خیلی راحت از بستر امن تلگرام استفاده می کنید اما نمی دونید که پشتش چه کارهایی انجام دادن.

نظر شما

پرطرفدارترین مطالب امروز

قواعد بخش پذیری بر اعداد  1 تا 20
طنز ریاضی: لطیفه های ریاضی!
زندگینامه ریاضیدانان: جان فوربز نش
طنز ریاضی: اثبات 5=2+2
بررسی تعلیم و تربیت از دیدگاه جان دیوئی
همه چیز درباره هوش مصنوعی به زبان ساده
زندگینامه ریاضیدانان: محمد خوارزمی
چرا ریاضی می‌خوانیم؟
طنز ریاضی: اثبات 2=1