بخشی از مقاله
اصل لانه كبوتر
چكيده:
اصل لانه كبوتر بسيار روشن است و بسيار ساده به نظر مي‌رسد، گويي داراي اهميت زيادي نيست، ولي در عمل اين اصل داراي اهميت و قدرت بسيار زيادي است، زيرا تعميمهاي آن حاوي نتايجي عميق در نظريه تركيباتي و نظريه اعداد است. وقتي مي‌گوئيم در هر گروه سه نفري از مردم حداقل دو نفر، هم جنس‌اند در واقع اصل لانه كبوتر را به كار گرفته‌ايم. فرض كنيم به تازگي در دانشكده‌اي، يك گروه علوم كامپيوتر تاسيس يافته كه براي 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) به رنگ آبي باشد. آن‌گاه اين يال‌ها با رنگ‌هاي قرمز يا زرد خواهيم داشت. و اين به اين معني است كه حداقل سه نفر وجود دارند كه با هم راجع به يك موضوع بحث كرده باشند.
2. فرض كنيم {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 را مي‌شمارد يا برعكس.
3. اكبر در طول تعطيل چهار‌هفته‌اي خود هر روز حداقل يك دور تنيس بازي مي‌كند. ولي در طي اين مدت جمعاً بيش از 40 دور بازي نخواهد كرد. ثابت كنيد كه توزيع دفعات دورهاي بازي او در طي چهارهفته هر چه باشد، تعدادي از روزهاي متوالي وجود دارد كه طي آنها دقيقاً 15 دور بازي مي‌كند؟
حل:
براي ، فرض كنيد xi، تعداد كل دورهايي باشد كه اكبر از آغاز تعطيلات تا پايان روز I بازي كرده است. پس:
و
اينك 28 عدد متمايز x1 و x2 و... و x28 عدد متمايز 15+x1 ،15+x2 ،....،15+x28 داريم.
اين 56 عدد مي‌توانند تنها 55 مقدار مختلف اختيار كنند، بنابراين حداقل دو تا از آنها بايد مساوي بوده و نتيجه مي‌گيريم كه رابطه باشرط 15+x=xi وجود دارد. لذا از شروع (1+j)ام تا آخر روز I اكبر دقيقاً 15 دور بازي خواهد كرد.
4. كيسه‌اي حاوي دقيقاً 5 مهره قرمز،8 مهره آبي، 10 مهره سفيد و 12 مهره سبز و 7 مهره زرد است. مطلوب است تعيين تعداد مهره‌هايي كه بايد انتخاب شوند تا مطمئن شويم كه:
الف) حداقل 4 مهره همرنگ‌اند
ب) حداقل 7 مهره همرنگ‌اند
پ) حداقل 6 مهره همرنگ‌اند
ت) حداقل 9 مهره همرنگ‌اند
حل:
5 رنگ داخل كيسه وجود دارد. لذا 5 لانه كبوتر داريم:
ج الف) 16
ب) 30=1+4×6+5
پ) 26=1+4×5+5
ت) 37=1+2×8+7+8+5
5. 10 عدد طبيعي متمايز و كوچكتر از 107 مفروضند. نشان دهيد كه دو زيرمجموعه مجزا و غيرخالي اين 10 عدد يافت مي‌شود S مجموع اعضايشان يكسان است.
حل:
بزرگترين 10 عددي كه مي‌توانيم داشته باشيم 97، 98،....106 هستند كه مجموع آنها 1015 هست. بنابراين كافي است 1015 لانه كبوتر با شماره‌هاي 1 و2 و ...و 1015 را در نظر بگيريم. هر مجموعه 10 عضو شامل 1023=1-210 زيرمجموعه زيرتهي است، كه 1023 را تعداد كبوترها در نظر مي‌گيريم. لذا بنا به اصل لانه كبوتري، حداقل 2 زيرمجموعه با مجموع يكسان وجود دارند. اعداد متناظر را از 2 مجموعه حذف ميكنيم.
6. فرض كنيم فرد باشد. ثابت كنيد كه عدد صحيح مثبتي مانند n وجود دارد به طوري كه m عدد 1-2n را عادي مي‌كند؟
حل: 1+m عد صحيح مثبت 1-21، 1-22، 1-23، ....، 1-2m، 1-2m+1 را در نظر مي‌گيريم.
بنابراين اصل لانه كبوتر و الگوريتم تقسيم، اعدادي مانند وجود دارند به طوري كه
9= تعداد روز چهارم + روز پنجم
لذا حداقل دنبالهاي از دو روز متوالي چهارم و پنجم يافت شد كه مجموع ساعاتي كه دونده در آنها دويده 9 ساعت شود.
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 زير دنبالهاي اكيداً كاهشي بدست خواهد داد.
منابع
1. اصول و فنون تركيبات مترجمين: حسين ربيعي
حسين غفاري
2. رياضيات گسسته و تركيباتي رالف.پ.گريمالدي
ترجمه: دكتر محمد‌علي رضواني
دكتر بيژن شمس
3. رياضيات گسسته مقدماتي ترجمه: دكتر بيژن شمس
دكتر محمد‌علي رضواني
تأليف: و.ئ.بالاكريشنمان
4. رياضيات گسسته و تركيباتي از ديدگاه كاربردي (جلد اول) رالف گريمالدي
ترجمه: علي عميدي
