تحقیق اصل لانه كبوتر 12 ص
دسته بندي :
دانش آموزی و دانشجویی »
دانلود تحقیق
لینک دانلود و خرید پایین توضیحات
دسته بندی : وورد
نوع فایل : word (..DOC) ( قابل ويرايش و آماده پرينت )
تعداد صفحه : 12 صفحه
قسمتی از متن word (..DOC) :
1
چكيده:
اصل لانه كبوتر بسيار روشن است و بسيار ساده به نظر ميرسد، گويي داراي اهميت زيادي نيست، ولي در عمل اين اصل داراي اهميت و قدرت بسيار زيادي است، زيرا تعميمهاي آن حاوي نتايجي عميق در نظريه تركيباتي و نظريه اعداد است. وقتي ميگوئيم در هر گروه سه نفري از مردم حداقل دو نفر، هم جنساند در واقع اصل لانه كبوتر را به كار گرفتهايم. فرض كنيم به تازگي در دانشكدهاي، يك گروه علوم كامپيوتر تاسيس يافته كه براي 10 عضو هيئت علمي آن فقط 9 دفتركار موجود باشد. آنگاه باز هم ايده نهايي در پشت اين ادعاي بديهي كه حداقل از يك دفتركار بيشتر از يك نفر است استفاده ميكنند، اصل لانه كبوتر است. اگر به جاي 10 نفر 19 عضو هيئت علمي وجود داشته باشد، آنگاه حداقل از يك دفتركار بيشتر از دو نفر استفاده ميكنند. همينطور، اگر در دانشكدهاي حداقل 367 دانشجو وجود داشته باشند، باز آشكار است S حداقل دو نفر از آنها روز تولدشان يكي است. ميگويند كه سرانسان داراي حداكثر 999 و 99 تار مو است. از اين رو در شهري S جمعيت آن بيشتر از 4 ميليون باشد، حداقل 41 نفر وجود دارند كه تعداد موهاي سرشان يكي است (سر طاس مو ندارد). مثالهاي زيادي نظير اين را ميتوانيم نقل كنيم.
3
ايده اساسي حاكم بر همهي اين موارد حقيقت سادهاي مشهور به اصل لانهكبوتر دير بلكه است.
كه عبارت است از:
فرض كنيد k و n دو عدد طبيعياند. اگر بخواهيم بيشتر از nk+1 شي را در n جعبه قرار دهيم، حداقل يك جعبه وجود دارد كه در آن حداقل k+1 شي قرار گرفته باشد. در حالت خاص، اگر حداقل n+1 شي را در n جعبه قرار دهيم، جعبهاي وجود دارد كه در آن حداقل دو شي قرار گرفته باشد.
هفده نفر در جلسهاي حضور دارند. آنها درباره سه موضوع بحث ميكنند، هر دو نفر آنها درباره يك و فقط يك موضوع بحث ميكنند. ثابت كنيد يك گروه حداقل سه نفري وجود دارد كه افراد آن با هم راجع به يك موضوع بحث كرده باشند.
حل: ميتوانيم 17 نفر را 17 نقطه در نظر بگيريم كه هر دوتايي به توسط يك بال به هم وصل شدهاند. بالي را كه X و Y را به هم متصل ميكند، آبي ميكنيم اگر آن دو درباره موضوع (1) بحث كرده باشند و قرمز ميكنيم اگر راجع به موضوع (2) بحث كرده باشند و به رنگ زرد در ميآوريم. اگر آن دو درباره موضوع (3) با هم به بحث پرداخته باشند. بنابراين هر كدام از 16 بالي كه از A گذشتهاند با يكي از سهرنگ آبي، قرمز يا زرد رنگ شده است. از آنجايي كه 1+3×5=16، طبق اصل لانه كبوتري حداقل 1+5 رأس يافت مي
3
شود، كه با يك رنگ به A متصل شده باشند. بدون اينكه به كليت مساله لطمه بخورد فرض ميكنيم يالهاي AG,AF,AE,AD,AC,AB با رنگ آبي، رنگآميزي شده باشند. حال 6 رأس G,F,E,D,C,B را در نظر بگيريد كه با 15 يال به هم متصل شدهاند. اگر هر كدام از اين يالها (مثلاً BC) به رنگ آبي باشد. آنگاه اين يالها با رنگهاي قرمز يا زرد خواهيم داشت. و اين به اين معني است كه حداقل سه نفر وجود دارند كه با هم راجع به يك موضوع بحث كرده باشند.
فرض كنيم {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 را ميشمارد يا برعكس.
4
اكبر در طول تعطيل چهارهفتهاي خود هر روز حداقل يك دور تنيس بازي ميكند. ولي در طي اين مدت جمعاً بيش از 40 دور بازي نخواهد كرد. ثابت كنيد كه توزيع دفعات دورهاي بازي او در طي چهارهفته هر چه باشد، تعدادي از روزهاي متوالي وجود دارد كه طي آنها دقيقاً 15 دور بازي ميكند؟
حل:
براي ، فرض كنيد xi، تعداد كل دورهايي باشد كه اكبر از آغاز تعطيلات تا پايان روز I بازي كرده است. پس:
و
اينك 28 عدد متمايز x1 و x2 و... و x28 عدد متمايز 15+x1 ،15+x2 ،....،15+x28 داريم.
اين 56 عدد ميتوانند تنها 55 مقدار مختلف اختيار كنند، بنابراين حداقل دو تا از آنها بايد مساوي بوده و نتيجه ميگيريم كه رابطه باشرط 15+x=xi وجود دارد. لذا از شروع (1+j)ام تا آخر روز I اكبر دقيقاً 15 دور بازي خواهد كرد.
كيسهاي حاوي دقيقاً 5 مهره قرمز،8 مهره آبي، 10 مهره سفيد و 12 مهره سبز و 7 مهره زرد است. مطلوب است تعيين تعداد مهرههايي كه بايد انتخاب شوند تا مطمئن شويم كه: