روی یک میز 12 نفری ، 12 کارت با نام مهمانها گذاشته شده است . مهمان ها آمدند و نشستند اما نه به ترتیبی که معین شده بود . ثابت کنید که می توان میز را طوری چرخاند که حداقل دو نفر از مهمانها جلو کارت هم نام خود قرار بگیرند.
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 07:42:11 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-27 07:49:23 -0500 امیر شکریسلام :)
برای آسانی کار:
هر فرد رو شماره گذاری کرده و کارت ها نیز شماره ای که به فرد نسبت داده شده می نویسیم
من برای $n$ نفر اثبات می کنم :) البته یه الگوریتم ارائه میدم ها !
اول میز رو جوری میچرخونیم که کارت نفر اول بیوفته جلوی نفر اول( خب می بینیم کسی جلوش کارت خودش نیس؟ اگه بود که هیچی ) به کارت نفر $n$ نگاه می کنیم مثلا یه عددی است که $n$ نیس پس این عدد رو ذخیره می کنیم . دقیقا همین کارو به ترتیب از نفر اول تا نفر$1-n$ و اگر دو نفر با کارت ها خوشان یافت شد الگوریتم پایان می یابد.
پس اگر الگوریتم کار کرد تا عمل آخر :
(به شکل زیر دقت کنید )
حال با توجه به اینکه فرد $n$ ام هیچ گاه کارت $n$ جلویش نبوده پس در عمل آخر نیز جز کارت $n$ در دستش بوده پس فرض می کنیم در عمل آخر کارت $X$ در دستش بوده است با توجه به اینکه در دو عمل متفاوت نمی تواند دو کارت دست نفر $n$ ام مشابه باشد و در همه اعمال نفر $n$ ام کارت $n$ را در دست نداشته پس حتما طبق اصل لانه کبوتری (n-2 لانه و n-1 کبوتر) پس در عمل آخر $X$ همان $n$ است :) پس دو نفر پیدا شد که کارت خودشان در دستشان است .(یکم جمله سنگین بود !)
