اصل لانه کبوتری

دراین مقاله بعد ازگفتن اصل لانه کبوتری و حالت کلی ترآن سعی می کنیم با هم یک مسئله جالب حل کنیم اولین بار"پیتر دیریکله" ریاضیدان آلمانی قرن نوزدهم ازاین اصل که به اصل دیر یکله هم معروفه،استفاده کرد این اصل خیلی ساده است ولی با همین اصل می توان مسئله های زیادی را حل کرد .
اصل لانه کبوتری :اگر۱+ n کبوتربخواهند در n لانه وارد شوند. حداقل در یک لانه بیش از یک کبوتروجود دارد. مثلا اگر ۳کبوتر وارد ۲لانه بشوند حتما دریکی ازلانه ها حداقل ۲ کبوتر وجود دارد. طبق این اصل می توانیم بگوییم :۱- در بین سه نفر حتما ۲نفر با جنسیت یکسان وجود دارد (۲ زن و ۱مرد، یا ۱ زن و ۲مرد، یا ۳ زن ویا۳ مرد)۲-دربین ۸ نفرحتما دو نفرهستند که در یک روزهفته به دنیا آمده اند و دربین ۳۶۷نفرحتما دو نفرهستند که دریک روز سال متولد شده اند و مثال هایی ازاین دست .
حالا وقت آن است که کمی به حالت کلی تراین اصل فکرکنیم .
اصل لانه کبوتری: n و k دوعدد طبیعی هستند .اگربخواهیم بیشتراز ۱kn+ شی را در nجعبه قرار دهیم حداقل یک جعبه وجود دارد که درآن حداقل ۱k+ شی قرارگرفته باشد.
اگربه درستی این اصل شک دارید و فکرمی کنید ممکن است درهیچ جعبه ای بیش ازk شی نباشد،کافی است یک باربا هم اشیا داخل جعبه ها را بشماریم! شما فکرمی کنید هیچ جعبه ای شامل ۱+k شی و یا بیشترنیست. این به این معنا ست که درهرجعبه حداکثر k شی وجود دارد .ازطرفی ما n جعبه داشتیم پس حداکثرkn شی درجعبه ها وجود دارد،در حالی که ما می دانیم دقیقا ۱nk+ شی داشتیم پس می توانیم یگوییم باید جعبه ای با بیش از k شی وجود داشته باشد .
مثلا اگر ۷ عدد طبیعی داشته باشیم می توانیم مطمئن باشیم حداقل ۴ تا از آنها زوج است یا۴ تا از آنها فرد است.(در این حالت۳k= و۲=n ،جعبه اول جعبه ای است که درآن اعداد زوج می ریزیم و جعبه دو م جعبه ای است که درآن اعداد فرد می ریزیم .حداقل در یکی ازجعبه ها بیش از۱+k یا ۴ شی وجود دارد.)
حالا دیگرمی توانیم مسئله خود را مطرح کنیم . این مسئله مربوط به یک مهمانی است . با توجه به اصل لانه کبوتری که دربالا گفته شد ،ببینید ادعای نویسنده درست است با نه؟
دریک مهمانی هرکسی که وارد می شود با تعدادی ازمهمان ها دست می دهد البته بدیهی است که هیچ کس با خودش دست نمی دهد ،درضمن هیچ دو نفری با هم بیش از یک باردست نمی دهند .دراین مهمانی بعد ازآمدن همه ی مهمان ها هر کسی در یک برگه می نویسد که با چند نفر دست داده است. حالا من ادعا می کنم که حتما دو نفرهستند که یک عدد را نوشته اند . یعنی دو نفر هستند که با تعداد مساوی از افراد دست داده اند !حالا نظر شما چیست ؟ کمی فکرکنید ، اگرنظری ندارید می توانید امتحان کنید !کم کم بیایید با هم ارتباط بین مسئله مهمانی و اصل لانه کبوتری را پیدا کنیم .
ببینیم چه عدد هایی می توانند نوشته شده باشند . هرکسی حد اکثربا۱- n نفردست داده (با همه مهمان ها به جزخودش) و حداقل عددهای گزارش شده برابرصفراست (حالتی که با هیچ کس دست نداده )یعنی عدد های نوشته شده می توانند از بین عددهای ۰و۱و۲و......و۱-n باشند . حالا فرض کنید که ۱-n تا جعبه داریم روی ۲-n تا ازآنها به ترتیب اعداد ۱تا۲-n نوشته شده(روی اولی عدد۱و روی دومی عدد۲و ......) و روی ۱-n ام عبارت ۰یا ۱-n نوسته شده .
حالا n برگه داریم که روی هر یک ، عددی بین صفر تا ۱-n نوشته شده (برگه هایی که هر یک از مهمان ها تعداد دست دادن هایشان را نوشته اند .)و۱-n جعبه . طبق اصل لانه کبوتری می دانیم که حتما جعبه ای وجود دارد که در آ ن حداقل دو برگه وجو د دارد . اگر این جعبه یکی از۲-n جعبه ی اول باشد یعنی دو نفراعداد مشابهی را نوشته اند و با تعداد برابری از مهمان ها دست داده اند .
اگر در جعبه ۱-n ام دو برگه وجود داشته باشد و روی دو برگه یک عدد نوشته شده باشد ،(روی هر دو صفر باشد و یا روی هر دو ۱-n ) باز هم مسئله درست است . فقط حالتی می ماند که درجعبه ی آخردو برگه باشد و روی یکی صفر و روی یکی ۱-n نوشته شده باشد .
در این حالت چه باید کرد ؟ ادعا می کنیم چنین حالتی هیچ گاه پیش نمی آید . اگراین حالت اتفاق بیفتد یعنی مهمان Aوجود دارد که با هیچ کس دست نداده است و درعین حال مهمان Bوجود دارد که با همه دست داده واین امکان ندارد زیراBبا Aدست نداده است . به عبارت دیگر امکان نداد یکی ازمهمان ها با همه دست داده باشد و دیگری با هیچ کس دست نداده باشد .
پس ما توانستیم ادعای خود ار اثبات نماییم. یعنی دو نفردرمهمانی هستند که با تعداد مساوی از افراد دست داده اند.

نویسنده :آمنه ابراهیم زاده
راستی اگر خواستید درباره اصل لانه کبوتری مسئله های جالب دیگری ببینید ، می توانید به کتاب های زیرمراجه کنید :
۱- استراتژی های حال مسئله
۲ -اصول و فنون ترکیبات

منبع : انجمن ریاضیدانان جوان