سایت مرجع دانلود پایان نامه -پشتیبانی 09199970560

پایان نامه:اصل لانه كبوتر

ارسال شده در ریاضی و آمار

در این پست می توانید متن کامل این پایان نامه را  با فرمت ورد word دانلود نمائید:اصل لانه كبوتر

 

چكيده:

اصل لانه كبوتر بسيار روشن است و بسيار ساده به نظر مي‌رسد، گويي داراي اهميت زيادي نيست، ولي در عمل اين اصل داراي اهميت و قدرت بسيار زيادي است، زيرا تعميمهاي آن حاوي نتايجي عميق در نظريه تركيباتي و نظريه اعداد است. وقتي مي‌گوئيم در هر گروه سه نفري از مردم حداقل دو نفر، هم جنس‌اند در واقع اصل لانه كبوتر را به كار گرفته‌ايم. فرض كنيم به تازگي در دانشكده‌اي، يك گروه علوم كامپيوتر تاسيس يافته كه براي 10 عضو هيئت علمي آن فقط 9 دفتر‌كار موجود باشد. آن‌گاه باز هم ايده نهايي در پشت اين ادعاي بديهي كه حداقل از يك دفتر‌كار بيشتر از يك نفر است استفاده مي‌كنند، اصل لانه كبوتر است. اگر به جاي 10 نفر 19 عضو هيئت علمي وجود داشته باشد، آن‌گاه حداقل از يك دفتر‌كار بيشتر از دو نفر استفاده مي‌كنند. همين‌طور، اگر در دانشكده‌اي حداقل 367 دانشجو وجود داشته باشند، باز آشكار است S حداقل دو نفر از آنها روز تولدشان يكي است. مي‌گويند كه سرانسان داراي حداكثر 999 و 99 تار مو است. از اين رو در شهري S جمعيت آن بيشتر از 4 ميليون باشد، حداقل 41 نفر وجود دارند كه تعداد موهاي سرشان يكي است (سر طاس مو ندارد). مثالهاي زيادي نظير اين را مي‌توانيم نقل كنيم.

ايده اساسي حاكم بر همه‌ي اين موارد حقيقت ساده‌اي مشهور به اصل لانه‌كبوتر دير بلكه است.

كه عبارت است از:

فرض كنيد ‌k و n دو عدد طبيعي‌اند. اگر بخواهيم بيشتر از nk+1 شي را در n جعبه قرار دهيم، حداقل يك جعبه وجود دارد كه در آن حداقل k+1 شي قرار گرفته باشد. در حالت خاص، اگر حداقل n+1 شي را در n جعبه قرار دهيم، جعبه‌اي وجود دارد كه در آن حداقل دو شي قرار گرفته باشد.

  1. هفده نفر در جلسه‌اي حضور دارند. آنها درباره سه موضوع بحث مي‌كنند، هر دو نفر آنها درباره يك و فقط يك موضوع بحث مي‌كنند. ثابت كنيد يك گروه حداقل سه نفري وجود دارد كه افراد آن با هم راجع به يك موضوع بحث كرده باشند.

حل: مي‌توانيم 17 نفر را 17 نقطه در نظر بگيريم كه هر دوتايي به توسط يك بال به هم وصل شده‌اند. بالي را كه X و Y را به هم متصل مي‌كند، آبي مي‌كنيم اگر آن دو درباره موضوع (1) بحث كرده باشند و قرمز مي‌كنيم اگر راجع به موضوع (2) بحث كرده باشند و به رنگ زرد در مي‌آوريم. اگر آن دو درباره موضوع (3) با هم به بحث پرداخته باشند. بنابراين هر كدام از 16 بالي كه از A گذشته‌اند با يكي از سه‌رنگ آبي،‌ قرمز يا زرد رنگ شده است. از آن‌جايي كه 1+3×5=16، طبق اصل لانه كبوتري حداقل 1+5 رأس يافت مي‌شود، كه با يك رنگ به A متصل شده باشند. بدون اينكه به كليت مساله لطمه بخورد فرض مي‌‌‌كنيم يال‌‌هاي AG,AF,AE,AD,AC,AB با رنگ آبي، رنگ‌آميزي شده باشند. حال 6 رأس G,F,E,D,C,B را در نظر بگيريد كه با 15 يال به هم متصل شده‌اند. اگر هر كدام از اين يال‌ها (مثلاً BC) به رنگ آبي باشد. آن‌گاه اين يال‌ها با رنگ‌هاي قرمز يا زرد خواهيم داشت. و اين به اين معني است كه حداقل سه نفر وجود دارند كه با هم راجع به يك موضوع بحث كرده باشند.

  1. فرض كنيم {n2 و …و 3و2و1}=X و فرض نمائيم S زير مجموعه‌اي (1+n) عنصري از x باشد. آن‌گاه حداقل دو عدد در S وجود دارند به طوري كه يكي ديگري را مي‌شمارد.

اثبات: هر عدد دلخواه r متعلق به S را مي‌توان به صورتS .2t= r نمايش داد كه در آن،T يك عدد صحيح نامنفي و S عدد فرد متعلق به X، به نام قسمت فرد (r) است. براي S حداكثر n انتخاب وجود دارد، زيرا n عدد فرد در X وجود دارد. اين n قسمت فرد را مي‌توان به عنوان n لانه كبوتر در نظر گرفت كه قرار است (1+n) عدد متعلق به S را بين اين لانه‌ها پخش كنيم. به عبارت ديگر، دو عدد مانند x و y در s وجود دارند كه قسمت فرد آنها يكي است. فرض كنيم s.2t=x و.2u.s=y آن‌گاه يا x عدد y را مي‌شمارد يا برعكس.

  1. اكبر در طول تعطيل چهار‌هفته‌اي خود هر روز حداقل يك دور تنيس بازي مي‌كند. ولي در طي اين مدت جمعاً بيش از 40 دور بازي نخواهد كرد. ثابت كنيد كه توزيع دفعات دورهاي بازي او در طي چهارهفته هر چه باشد، تعدادي از روزهاي متوالي وجود دارد كه طي آنها دقيقاً 15 دور بازي مي‌كند؟

(ممکن است هنگام انتقال از فایل ورد به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)

متن کامل را می توانید دانلود نمائید

چون فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به طور نمونه)

ولی در فایل دانلودی متن کامل پایان نامه

همراه با تمام ضمائم (پیوست ها) با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود است

فایل ها برای اینکه حجم آنها پایینتر شود وراحتتر دانلود شوند با فرمت rar یا zip فشرده شده و پسوردگذاری شده اند. پسورد همه فایل های این سایت یکسان است.

برای دریافت پسورد فایل اینجا کلیک کنید

اصل لانه كبوتر

 

مطالب مشابه را هم ببینید

141985615752731

فایل مورد نظر خودتان را پیدا نکردید ؟ نگران نباشید . این صفحه را نبندید ! سایت ما حاوی حجم عظیمی از پایان نامه ، تحقیق ، پروژه و مقالات دانشگاهی در رشته های مختلف است. مطالب مشابه را هم ببینید یا اینکه برای یافتن فایل مورد نظر کافیست از قسمت جستجو استفاده کنید. یا از منوی بالای سایت رشته مورد نظر خود را انتخاب کنید و همه فایل های رشته خودتان را ببینید فروش آرشیو پایان نامه روی دی وی دی

aca@

academicbooks@

پایان نامه:جغرافياي رياضي
دانلود پایان نامه:پروژه آمار و احتمالات
پایان نامه ارشد:تعاريف و ويژگي‌هاي بنيادي توابع مثلثاتي
پایان نامه ارشد:بررسی تاثیرآموزش برامنیت شغلی معلمان زن شهرستان لامرد
پایان نامه:ویژگی های افراد سیگاری و غیر سیگاری