اختصاصی از
فی فوو دانلود مقاله اصل لانه کبوتر دانلود با لینک مستقیم و پر سرعت .
مشخصات این فایل
عنوان: اصل لانه کبوتر
فرمت فایل: word( قابل ویرایش)
تعداد صفحات: 19
این مقاله درمورد اصل لانه کبوتر می باشد.
خلاصه آنچه در مقاله اصل لانه کبوتر می خوانید :
7. فرض کنید{a5 و .....a2 وa1}=A مجموعه‌ای از 5 عدد صحیح و مثبت باشد. نشان دهید که برای هر جایگشت مانند{ai5 و...وai1}=B از مجموعه A حاصل ضرب
(ai1-a1) (ai2-a2)…(ai5-a5)
عددی زوج است.
حل:
ضرب n عدد زوج است، هرگاه حداقل یکی از اعداد زوج باشد، بنابراین یکی از (aij-aj) عدد زوج است. یعنی aj و aij یا هردو زوج‌اند و یا هردو فردند. طبق اصل لانه کبوتری، حداقل 3 عضو از مجموعه A دارای زوجیت یکسان هستند.
به عنوان مثال، a1 و a2 و a3 از مجموعه A را در نظر می‌گیریم که هر سه فردند یا زوج. لذا روشن است که Q {a13 و a12 و a11} {a3 و a2 و a1} (زیرا مجموعه A بایست حداقل دارای 6 عضو {a13,a12,ali,a3,a2,a1} باشد). به عبارتی دیگر مجموعه {a1,a2,a3,a11,a12,a13}=c حداقل دو عضو برابر دارد. فرض کنید a11= a3. بنابراین a1-a3=a1-a11 در نتیجه a1-a11 عددی زوج است.
8. برای تمام اعداد طبیعی و p ثابت کنید R+ R (p,q) R .
اثبات:
فرض کنیم . طبق قضیه رمزی (برای تمام اعداد طبیعی2 q و p، عدد R(p.q) با شرط ذکر شده، وجود دارد.) و برای اثبات قضیه کافی است که نشان دهیم که اگر دسته نقطهی nتایی را با دو رنگ قرمز و آبی رنگ کنیم، آن‌گاه یک دسته‌ی نقطه‌ای pتایی با یک دسته نقطهی qتایی قرمز وجود دارد. سه نقطهی nتایی را با kn نشان می‌دهیم.
یک رأس ثابت V در Kn را در نظر بگیرید. از v، 1-n یال در kn عبور کرده است:
طبق تعمیم یافته اصل لانه کبوتری R(P-1,q) یال گذرنده از v وجود دارد که با آبی رنگ شده‌اند یا R(P,q-1) گذرنده v وجود دارند که با قرمز رنگ شده‌اند. فرض می‌کنیم حالت اول درست باشد. فرض کنید x مجموعه نقاطی باشد که این R(P,q-1) به v وصل شده‌اند. از آن‌جا که طبق تعریف مجموعه‌ی x شامل یک دسته‌ی نقطه (p-1)تایی آبی باشد، آن‌گاه مجموعه {v} x یک دسته نقطه qتایی آبی است.
9. 6 مهره قرمز، 5 مهره سفید و 7 مهره آبی در یک کیسه داریم. مطلوب است تعیین کمترین تعداد مهره‌هایی که باید انتخاب شوند تا مطمئن شویم S حداقل 3 مهره قرمز یا حداقل 4 مهره سفید یا حداقل 5 مهره آبی انتخاب شده است؟
حل:
اگر x و y و z به ترتیب تعداد مهره‌هایی به رنگ قرمز و سفید و آبی باشند که بناست انتخاب شوند، آن‌گاه اگر x=2 و y=3 و z=4، آن‌گاه جواب 9 است، بنابراین وضعیت مطلوب پیش نمی‌آید بدین‌سان باید حداقل 10 مهره انتخاب کنیم. (پاسخ 10 مهره)
که نتیجه می‌دهد
پس می‌توان B را برابر {aj و ...ai-2 وaih} در نظر گرفت.
10. هر دنباله مرکب از (n2+1) عدد صحیح متمایز شامل زیر دنبالهای با حداقل (n+1) جمله است که یا دنبالهای افزایشی است یا دنبالهای کاهشی.
اثبات: فرض کنیم دنباله مورد بحث 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 را بین آنها پخش کنیم. از این رو بنابر اصل لانه‌ی کبوتر تعمیم یافته، لانه‌ای مانند Hr شامل بیش از kتا از این اعداد که در آن k مقدار گردشده نقصانی است، وجود دارد.
بنابراین حداقل (n+1) تا از اعداد ti با هم برابرند. اینک این را ثابت می‌کنیم که (n+1) عدد واقع در دنباله مفروض که متناظر با این اعداد واقع در لانه Hrاند دنبالهای کاهشی تشکیل می‌دهند. فرض کنیم در Hr باشند یا یا زیرا عناصر مورد بحث متمایزند. فرض کنیم . حال ، مستلزم این است که زیر دنبالهای به طول r وجود داشته باشد که با aj شروع شود. از این‌رو، نتیجه می‌گیریم که زیر دنبالهای به طول (Rh) وجود دارد که با ai شروع می‌شود. این یک تناقص است زیرا با توجه به اینکه ai عنصری از Hr است نمی‌توان زیر دنبالهای به طول (r+1) داشت که با ai شروع شود. بدین‌سان وقتی باید . از این رو، هر (n+1) عنصر دلخواه در Hr زیر دنبالهای اکیداً کاهشی بدست خواهد داد.
بخشی از فهرست مطالب مقاله اصل لانه کبوتر
چکیده
حل مسائل متنوع
منابع
دانلود با لینک مستقیم
دانلود مقاله اصل لانه کبوتر 
