چكيده
حل مسائل متنوع
چكيده:
اصل لانه كبوتر بسيار روشن است و بسيار ساده به نظر ميرسد، گويي داراي اهميت زيادي نيست، ولي در عمل اين اصل داراي اهميت و قدرت بسيار زيادي است، زيرا تعميمهاي آن حاوي نتايجي عميق در نظريه تركيباتي و نظريه اعداد است. وقتي ميگوئيم در هر گروه سه نفري از مردم حداقل دو نفر، هم جنساند در واقع اصل لانه كبوتر را به كار گرفتهايم. فرض كنيم به تازگي در دانشكدهاي، يك گروه علوم كامپيوتر تاسيس يافته كه براي 10 عضو هيئت علمي آن فقط 9 دفتركار موجود باشد. آنگاه باز هم ايده نهايي در پشت اين ادعاي بديهي كه حداقل از يك دفتركار بيشتر از يك نفر است استفاده ميكنند، اصل لانه كبوتر است. اگر به جاي 10 نفر 19 عضو هيئت علمي وجود داشته باشد، آنگاه حداقل از يك دفتركار بيشتر از دو نفر استفاده ميكنند. همينطور، اگر در دانشكدهاي حداقل 367 دانشجو وجود داشته باشند، باز آشكار است S حداقل دو نفر از آنها روز تولدشان يكي است. ميگويند كه سرانسان داراي حداكثر 999 و 99 تار مو است. از اين رو در شهري S جمعيت آن بيشتر از 4 ميليون باشد، حداقل 41 نفر وجود دارند كه تعداد موهاي سرشان يكي است (سر طاس مو ندارد). مثالهاي زيادي نظير اين را ميتوانيم نقل كنيم.
ايده اساسي حاكم بر همهي اين موارد حقيقت سادهاي مشهور به اصل لانهكبوتر دير بلكه است.
كه عبارت است از:
فرض كنيد k و n دو عدد طبيعياند. اگر بخواهيم بيشتر
اثبات: فرض كنيم دنباله مورد بحث ai (I=1,2,…,n2+1) باشد فرض كنيم ti عبارت باشد از تعداد جملههاي واقع در طولانيترين زير دنباله افزايشي كه با ai شروع ميشود. اگر به ازاي iاي داشته باشيم ti=n+1 آنگاه كار تمام است. فرض كنيم كه به ازاي هر I داشته باشيم . قرار ميدهيم {j=ti:ai}= HJ كه در آن n و …2و1 = j . بدينسان n لانه كبوتر H1 و H2 و…Hn را داريم S بناست (n2+1) عدد ti را بين آنها پخش كنيم. از اين رو بنابر اصل لانهي كبوتر تعميم يافته، لانهاي…
منابع
حسين غفاري
ترجمه: دكتر محمدعلي رضواني
دكتر بيژن شمس
دكتر محمدعلي رضواني
تأليف: و.ئ.بالاكريشنمان
ترجمه: علي عميدي