چكيدهحل مسائل متنوعچكيده:اصل لانه كبوتر بسيار روشن است و بسيار ساده به نظر ميرسد، گويي داراي اهميت زيادي نيست، ولي در عمل اين اصل داراي اهميت و قدرت بسيار زيادي است، زيرا تعميمهاي آن حاوي نتايجي عميق در نظريه تركيباتي و نظريه اعداد است. وقتي ميگوئيم در هر گروه سه نفري از مردم حداقل دو نفر، هم جنساند در واقع اصل لانه كبوتر را به كار گرفتهايم. فرض كنيم به تازگي در دانشكدهاي، يك گروه علوم كامپيوتر تاسيس يافته كه براي 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را بين آنها پخش كنيم. از اين رو بنابر اصل لانهي كبوتر تعميم يافته، لانهاي...منابعحسين غفاريترجمه: دكتر محمدعلي رضوانيدكتر بيژن شمسدكتر محمدعلي رضوانيتأليف: و.ئ.بالاكريشنمانترجمه: علي عميدي
دانلود پایان نامه اصل لانه كبوتر 8ص
چكيدهحل مسائل متنوعچكيده:اصل لانه كبوتر بسيار روشن است و بسيار ساده به نظر ميرسد، گويي داراي اهميت زيادي نيست، ولي در عمل اين اصل داراي اهميت و قدرت بسيار زيادي است، زيرا تعميمهاي آن حاوي نتايجي عميق در نظريه تركيباتي و نظريه اعداد است. وقتي ميگوئيم در هر گروه سه نفري از مردم حداقل دو نفر، هم جنساند در واقع اصل لانه كبوتر را به كار گرفتهايم. فرض كنيم به تازگي در دانشكدهاي، يك گروه علوم كامپيوتر تاسيس يافته كه براي 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را بين آنها پخش كنيم. از اين رو بنابر اصل لانهي كبوتر تعميم يافته، لانهاي...منابعحسين غفاريترجمه: دكتر محمدعلي رضوانيدكتر بيژن شمسدكتر محمدعلي رضوانيتأليف: و.ئ.بالاكريشنمانترجمه: علي عميدي