صفحه ۳۷
+
به نام خدا
از ره مرو به عشوه دنیا که این عجوز مکاره می نشیند و محتاله می رود
نه این که فقط المپیاد این طوری باشه نه، خیلی چیز ها ی دیگه هم تو دنیا هستند که انسان رو تحت تاثیر جو خودشون قرار می دهند. اصلا المپیاد خیلی آدم رو جوگیر می کنه و وقتی تموم بشه آدم تازه این رو می فهمه، البته منکر خوبیهاش نیستم، ولی نحوه ی برخورد با المپیاد مهمه.(من می خوام یه جور ها یی نصیحتی رو بهتون بکنم که خودم اصلا نمی تونم ادعا بکنم که تونستم به این نصیحت عملکنم، ولی خوب مگه اگه کسی مشهد نرفته باشه و یکی دیگه ازش بپرسه که مشهد از کدوم طرفه، نبایدجوابش رو بده؟ البته شما از من سوالی نکردید، ولی…)
ببینید، اصلا خوب نیست که اینقدر به فکر نمره و قبولی و این چیز ها باشیم، می دونم، طبیعیه، اما برایما ها طبیعیه، برای بزرگان، این نگرانی ها بی معنی حتی یه جورایی احتمالا بده. ظاهرا امام خمینی جمله ای داره شبیه این که:
انسان مامور( و مسؤول) به (انجام) وظیفه است، نه مامور به نتیجه.
می خوام بگم که من فکر می کنم انسانی که داره سعی می کنه به ایده ال ها ی اخلاقی نزدیک بشه، نباید نتیجه ی کارش براش مهم باشه، بلکه باید تلاشش براش مهم باشه. آره ، یعنی ممکنه یه نفر طلا هم بشه و از تلاش خودش راضی نباشه یا طلا نشه و از تلاش خودش راضی باشه. به نظر من اولی باید ناراحت و دومی باید خوشحال باشه، اون وقته که دیگه آدم این طوری نیست که تا یه امتحان میده، تحت تاثیر اون جو اضطراب داشته باشه و از قبولیش کلی خوشحال بشه و از عدم قبولیش بر عکس. اون وقته که آدم کم کم سعی میکنه انگیزه ها ی خودش رو درست کنه و خدایی کنه و این طوری رشد می کنه. خود امام خمینی رو از مادرم شنیدم که می گفت توی هواپیما که بوده و از فرانسه به ایران میومده، یه خبرنگار اومده ازش پرسیده که شما چه حسی دارید، می دونید، گفته هیچ حس خاصی ندارم، آدم وقتی می تونه این طوری بشه که براش نتیجه ی کار مهم نباشه ، تلاش هم اکنون اش مهم باشه، اینکه از پس وظیفه ی که الان داره چه جوری بر میاد، اصلا بابا، ما داریم الان زندگی می کنیم، و بهتره به فکر الان مون باشیم و سعی کنیم از اینلحظه مون برای رشد کردن استفاده کنیم. همون طور که تولستوی توی “3 پرسش” می گه بهترین زمان الانه،و به قول حافظ
ساقیا عشرت امروز به فردا مفکن
یا ز دیوان قضا خط امانی به من آر
حالا هرکس این عشرت عاشقانه را اشتباه می فهمه، چه کنم که
در نظر بازی ما بیخبران حیرانند
یا حق!
۱۳۸۵/۰۳/۰۱ · ۱۸:۱۵
چشم ها را باید شست جور دیگر باید دید
بهنامخدا
نگار من که به مکتب نرفت و خطننوشت به غمزه مساله آموز صد مدرّس شد
راستش چی بگم؟ من واقعن تعجّب میکنم که وحید اینجوری با قضیه برخورد کرده.منظورم
پست قبلیه.آخه ما وقتی این وبلاگ رو زدیم خیلی دلمون می خاست که بتونیم یه جوری بچه ها رو از اینجو المپیاد بکشیم بیرون. اصلن دلمون میخاست بیشتر یه وبلاگ باشه مربوطبه علوم کامپیوتر نه المپیاد کامپیوتر . امّا خوب مخاطبهای ما المپیادی ها بودند و خودمونهم
المپیادی بودیم و اصلن المپیاد پدیده خوبی برای پیشرفت علوم کامپیوتر بود ولیالمپیاد مثل کنکور نیست که بگی باید این کتابها رو بخونی و این کارها رو بکنی تا طلا بشی.
اوّل من یه چیزی بگم:
اون چیزی که توی المپیاد کامپیوتر مهمّه توانایی حل مساله است. حالا اگه یه سری کتاب هم هست برایه اینه که این توانایی رو در ما تقویت کنه. ما باید یاد بگیریم که اولن درست استدلال منطقی کنیم، دوم اینکه بتونیم ایده های قشنگ بزنیم و مساله حل کنیم ، سوم اینکه بتونیم باز بان منطقی و استدلالهای درست راه حلمون رو برای دیگران بگیم(که البته این و مورد اول تقریبن یکی هستند) و چهارم هدف المپیاد جهانیه که البته جدیدن انگارهدف المپیاد کشوری هم شده و اون، اینه که بتونی الگوریتمت رو با یه برنامه(++C) خوب پیاده سازی کنی، یعنی برنامه نویس خوبی بشی، کدزن خوبی بشی( که البته من به شخصه این یکی رو به اندازه اون بقیه دوست ندارم و با ارزش نمیدونم اما فعلن که برای طلا شدن مهمه)
خلاصه این که الآن باید سعی کنید فکرتون قوی بشه. حتّی گاهی بهتره برای این که فکرتون باز بشه و قوی بشه، یه مدّتدرس نخونید، اصلن تو همین دوره طلا (انتخاب تیم) شاید من بیشتر از وحید و افشین به فکر درس خوندن بودم، ولی شاید همین زیاد به فکر
بودن، از دلایل مهم قبول نشدنم بود. همین وحید به من میگفت بی خیال، داریم زندگیمون رو میکنیم وخوب حالا یه خرده برنامه هم مینویسیم دیگه،
درستش هم همینه¡،
نه که کم درس بخونید ها،
ولی با لذّت درس بخونید.
المپیاد چیزیه که خوندنش لذّت بخشه، نه مثل یه سری از درسهای مدرسه زجر آور.همین افشین سال اوّل که بود خیلی برای المپیاد میخوند، ولی فکر کنم این کار رو کاملن با لذّت انجام میداد.البته راستش من خودم این رو هم یه جورایی قبول ندارم، یعنی خوب کار بلید برای خدا باشه، نه برای لذت بردن. البته کار برای خدا هم لذت خاص خودش رو داره.
بگذریم که این مورد جای بحث زیادی داره. البته هین رو بگم که من ادعا نمیکنم المپیاد خوندن وبقیه کارهام کاملن برای خداست، ولی ای کاش این طور بشود.
منابعی که وحید گفته، تؤوری هاش که بد نیست، البتّه اون ها هم میدونید، لازم نیست همش خونده بشه
مثلن لازم نیست همcreativهمclrsبخونید، یا اصلن لازم نیست که حتما تمام سوالهای یک فصل استراتژی رو حل کنید( همونطور که من تقریبن سوالهای هیچ فصلیش رو کامل حل نکردم) مهم اینه که یاد بگیرید کهمثلن چه جوری از ناوردایی، اکسترمال، یا رنگ آمیزی استفاده کنید.
منابع عملیش رو هم واقعن در سطح خیلی بالایی گفته، شماسعیکنیدCیاد بگیرید( و بعد همC++)اصلن دوره دومهای امسال که فقط 10% عملی داشت، همون جا هم کلی بهتونC++یاد میدن ولی بعدش هم 6 ماه وقت دارید تا برای امتحانهای (کاملن عملی) عید آماده بشید.
بعد هم ازUSACOشروع کنید دیگه، سایت خوبیه. بغدن میتونید مثلنSGUرو هم شروع کنید ولی بقیه اش رو خیلی نمی پسندم، یعنی اصلن یک یدو تاش رو اصلن نرفتم ببینم چی هستچون بیشتر همین ها رو توصیه میکردن. STLیه چیزیه که بهCاضافه شده تا شدهC++( البتّه شاید فقطSTLنباشه که اضافه شده)
چیز خوبیه، ولی کلّن اگه بتونیدCوSTLرو از یه کسی که خوب بلده یاد بگیرید، راحت تره تا اینکه کتاب بخونید. البتّه وحید خیلی راحت کتابهایی مثل استروستراپ یا مثلنSTL DOC( یعنیSTL DOCUMENTATIONیعنی همون آموزش و راهنمایSTL)رو میفهمه که البتّه فکر کنم اکثرن مثل من ترجیح میدن از یکی یاد بگیرن.
آهان در مورد درس خوندن یه چیزی بگم که در مواردی واقعن شما باید یه چیزایی روبخونید و به معلوماتتون اضافه بشه، مثل یه بخش ها یی ازCREATIVکه البتّه اگه این ها رو خودتون بخونیدو روشون تسلّط داشته باشید خیلی خوبه، ولی توی دوره تابستان کاملن درس میدن ولی خوب دیگه اون موقع وقت حل کردن سوال هاش رو ندارید.
خوب دیگه، فقط بدونید( که احتمالن خودتون خواهید فهمید) که یه وقت هایی برای موفّقیت در المپیاد کامپیوتر، حتّی لازمه که درس نخونید. ضمنن اگه درس خوندید هم جدّی بخونید:D
چون ممکنه مثل من یه دفعه ببینید یک سری ، خیلی کمتر از شما وقت و اعصاب صرف کردن و قوی تر شدن. سعی کنید بیشتروقتبگذارید، نهاعصاب.
یاحق
۱۳۸۵/۰۳/۰۱ · ۱۵:۱۲
چی بخونیم؟
سلام ملت چطورین؟ خوبید سلامتید؟ و همچنان هم که بنظر میرسه همتون زنده‌اید، خوب دیگه چیکار میشه کرد همیشه زندگی وفق مراد آدم نمیشه...
بخاطر اصرار زیاد شما گفتیم بیایم یه چیزی بنویسیم وگرنه افسار شاززز را بر پشتش مینداختیم و یه یک ماهی میذاشتیم واسه خودش بدوئه. اما خوب این مرام نمیذاره آدم راحت باشه. به هر حال گفتم امروز یکم در مورد این اول‌های بنده‌خدا بنویسیم. اگه تا آخر پیغام موضوع دیگه‌ای هم به ذهنم رسید مینویسم.
از اونجایی که من نمیدونم هر کردوم از اولایی که اینجا نظر میدن، چی و چقدر خوندن برای همین کلا مینویسم برای اینکه المپیاد کامپیوتر خونده باشید چیکار کنید. حالا هر کی هر مقدارش رو خونده بقیش رو بخونه. البته همینجا ذکر کنم که فرض بر اینه که یه نفر با هوش خوب بتونه تا دوره‌ی تابستون هم بدونه هیچ خوندنی بیاد. ولی خب یه آمار گیری نشون میده که این حرف حداکثر شامل یکی دو نفر میشه. البته واقعا برای قبول شدن مرحله دوم اصلا لازم نیست همه‌ی این چیزهایی که میگم رو بخونید. ولی اگه بخونید میتونید فرض کنید که احتمال قبول شدنتون منفی نیست
تئوری:
1-PTC: فصل اول
2-الفبا: فصل استقرا
3-استراتژی: لانه‌ی کبوتری-ناوردایی-اکسترمال.
4-وست: فصل اول
5-استراتژی: رنگ‌آمیزی- بازی‌ها
6-creative: استقرا
7-وست: فصل 2
8-creative: فصل 3 (تا ص55 هم کافیه)-فصل 4 تا قبل از AVL- فصل 5
9-وست: فصل 3
10-creative: بقیه‌ی 4-فصل 6-فصل 7
11-CLRS:تا قبل از گرافش
12-وست: 4ویه مقداری 5
13-CLRS: گرافش
عملی:
1-کتاب "آموزش زبان برنامه‌نویسی C" نوشته ریچی و کرنیگان، و مثل همیشه ترجمه‌ی قلزم
2-چندتا مسئله‌ی اوایل "مسئله‌های الگوریتمی"در حد 10 تا)
3- کلا واسه‌ی cpp هم کتاب استروستراپ مسلما بهترین کتابه، البته باید حوصله داشته باشید مخصوصا اولاش.
4- باز هم بدیهیه که واسه‌ی STL هیچ چیزی بهتر از stl_doc نیست که لینکش رو گذاشم اون کنار.
5- سایت رابی جونD: رو تموم کنید(منظورم usaco هست)
6- سایت sgu(البته این سایت با من مشکل شخصی داره!)
7- سایت pku(سایت بدی نیست ولی به‌هیچ‌وجه خوب هم نیست)
8- مسائل BOI و CEOI
البته توجه کنید که کتابی مثل جلوه‌های ترکیبیات درسش مهم نیست ولی اگه خیلی پایه‌اید میتونید هر موضوعی که از تو استراتژی میخونید سوال‌هاش رو توی جلوه‌ها هم حل کنید. مثلا بعد از شماره‌ی 10 سوالای تئوریه "مسئله‌های الگوریتمی" خیلی خوبه. یا مثلا کتابهایی مثل "لنین‌گراد" و "شوروی" واسه‌ی قبل از مرحله 2(حدودای عید) خیلی خوبن.
البته کلا توجه دارید که وقتی میگم اینا رو بخونید یعنی مسئله‌هاش رو هم حل کنیدD:
همونجور که گفتم اصلا لازم نیست واسه‌ی مرحله 2 همه‌ی اینا رو خونده باشید(خودم همین حالا هم شک دارم همش رو خونده باشم)من خودم سال دوم که بودیم تا قبل از مرحله 2 فقط تا قسمت 7 خونده بودم. ولی در کل اگه به این ترتیب بخونید میتونید مطمئن باشید که احتمال قبول شدنتون بالای صفره. اگه احیانا اسم کتابی رو کامل بخواید توی پیغام‌های قبلیمون گفتیم، توی آرشیو موضوعی هم هست. غیر از اینها یک سری چیزها مثل مسائل هندسی توی عملی هست، که اینا یک سری نکتن که توی دوره‌ها یهتون یاد خواهند داد.
خوب این از اولا. اگه چیزی رو جا انداخته باشم ویرایش میکنم. واسه‌ی امسالی‌ها هم همونجور که افشین گفت غیر از حدود 10% عملی چهارتا درس تئوری دارید. 1-گراف 2-ترکیبیات 3- الگوریتم و مبانی 4-cpp. که این درس‌ها کاملا بستگی به معلمش داره مخصوصا ترکیبیات. ولی:
برای گراف: احتمالا تا آخر فصل 2 میگن. فصل 3 غیر از قسمت آخرش. و مقادیر متنوعی از 4و5.(البته اینا که گفتم از edition1)
برای ترکیبیات: قراره هیچ حرفی از ترکیبیات نزنیم، فقط اینقدر بگم که احتمال زیاد مقادیر کاملا متنوعی از کتاب "ونلینت" رو بهتون میگن. کلا واسه‌ی ترکیبیات نگران نباشید، هرچی توی دوره بهتون گفتن بخونید کافیه.
برای الگوریتم: بخش orderها از creative و CLRS خوبه و بقیش تمرین. مثلا از "مسئله‌های الگوریتمی"
برای cpp: همون چیزهایی که درس میدن کافیه. خیلی حال دارید قسمت‌های مرتبط توی استروستراپ.
همین دیگه، زیادی مرام گذاشتم از مخم overflow کرد.(البته مطمئن نیستم اصلا مخی هست یا نه) در ضمن خواستم به اونهایی که انشاالله میان دوره بگم که به احتمال زیاد در کلاس‌های گراف با پیدایش شاززز آشنا میشید(البته اگه معلم همچنان مورتی باشه)
خب دیگه فعلا خوش باشید و حال کنید با امتحانا(مخصوصا عربی)
یا حق
۱۳۸۵/۰۳/۰۱ · ۰۹:۰۵
مرحله ۲ تموم شد!!!
خوب مرحله 2 هم تموم شد رفت!قبل مرحله 2 (و بطّبع کمی بعدش) همونطور که گفته بودیم وبلاگ ما کاملنرنگ و بوی مرحله 2 گرفته بود. مسه شما ها دیگه. ولی خوب الان دیگه خیلی چیزا فرق میکنه
اونایی که اوّلی ان به جز سوال حل کردن، بد نیست که شروع کنن یه کمی الگوریتم یاد بگیرن.مثلن فصله 4 کتاب کریتیو(Creative) خیلی خوبه واسه این کار! از الگوریتم های استقرا ایی خیلی ساده شروعکرده. دوّمی ها هم خوبه حدّه اقل فصل 4 کریتیو رو بخونن!
(از این بگزریم که هر گونه اطَلاعاتی که قراره نیاز داشته باشین، تو دوره تابستون درس داده میشه) فصل هایه دیگه از کریتیو هم بد نیست، خوبه! به نظره من که تا فصل 7 اشو بخونین...(با اینکه تو دوره اکثرشو درس خواهند داد، ولی خوب این کار 2 تا خوبی داره! یکی اینکهمساله هایه کریتیو مساله هایه خوبی ان و به آدم دید الگوریتمی میدن(و بعضی هاشونم سختن!!!) خوبیه دومش اینه که وقتی تو دوره دارن اینا رو درس میدنشما(ایشالا که همتون قبول شین!) میگیرین راحت سر کلاس میخوابین!)
بگزریم
به جز کریتیو ، بد نیست سوال هایه دوره هایه سال هایه پیش رو گیر بیارین و حلشون کنین دیگه! اوضاع داره قرو قاتی میشه! بزارین دقیق تر به قضیه نگاه کنیمD:
تو دوره یه سری امتحان تئوری برگزار میشه و یه سری امتحان درسی. امتحان های تئوری رو که باید زور بزنین هلشون کنین دیگه (گفتم که سوالهای سالهای پیش رو پیدا کنین حل کنین، کلّن سوال حل کنین دیگه...)
امتحان های درسی اینان:گراف، الگوریتم، ترکیبیات
اینو بگم که امتحان های درسی معمولن ساده ان(معمولن)
برای درس گرافتون میتونین کتاب آشنایی با نظریه گراف(وست) رو بخونین
خوبیه این کتاب مساله هایه جالبشه! حل کردنه مساله هاش باعث میشه دید خوبی پیدا کنین کلّن!(مساله حل کردنتون به دنبالش قوی میشه)
واسه درسه الگوریتم که کریتیو رو گفتم...
ترکیبیات هم درگیرش نشین بهتره ! همون تو دوره میان یه سری شرّو ور درس میدن بهتون (بستگی به معلّمش داره که چی درس بدن) و اصلن کلّن صحبت نمیکنیم اینجا در مورده ترکیبیات! فمیدین؟
اینا که قسمته تئوری قضیه بود، کلّن تو دوره تابستون درصد امتحان هایه تئوری خیلی بیشتر از عملی هست.(پارسال توری 90 درصد بود! و عملی فقط 10 درصد!!!) ظاهرن همیشه قراره اینجوری باشه...
تو دوره خودشون ++C (زبونی که قراره باهاش برنامه بنویسین)یاد میدن. البتّه بد نیست اگه خودتون از قبل بلد باشین و تمرین کرده باشین.بازم میگم : خوب دقت کنین که تو دوره پارسال عملی فقط 10 درصد تأثیر داشت!
برای تمرین کردن عملی هم میتونین برین تو این سایت هایی که ما لینکشو گزاشتیم اون گوشه!بهترینشون واسه شروع به نظره من همون USACO هست!
خوب دیگه، سرم درد گرفت!
خوش باشین. قبله اینکه برم دوست دارم از یکی از دوستایه عزیزم که الان داره تو دانشگاه تورنتو درس میخونه و 2 تا مدال نقره کشوری داره یه چیزی بگم:
المپیاد فقط یه پوئنه! واسه اینکه یه سری کار ها رو راحت تر کنه، فقط همین!و هر چیزی که ما فکر میکنیم از المپیاد خوندن به دست میاد، میشه بدونه اینکه هیچ ربطی به قضیه المپیاد پیدا کنه، به دست اورد...
موفق باشین دوستان
یا حق
۱۳۸۵/۰۲/۲۴ · ۱۶:۵۴
مرحله ۲ اولا
بقیه‌ی دنباله‌ها رو میشه فرض کرد که f_0 همه بیشتر از صفره, چون اگه اینجوری نباشه کافیه همه‌ی دنباله رو در ۱- ضرب کرد و رابطه‌ی آینه‌ای بودن یا نبودن همچنان برقرار میماند. حالا خود اینها میشن دو دسته:
دسته‌ی اول: اونهایی هستن که f_1 کمتر از صفره. برای اینها کافیه f_1 و f_-1 رو در نظر بگیرید و به تناقض برسونید.
دسته‌ی دوم: اونهایی که f_1 بزرگتر از صفره. برای اینها کافیه اولین i رو در نظر بگیرید که منفی شده. باز دو حالت پیش میاد:
اولین i بعد از ۱ و -۱ باشه: اگه فرمولش رو بنویسید میبینید که مجبور میشه دنباله شامل یکدونه صفر باشه. و ما چند خط بالاتر ثابت کردیم که با شروع از ۰ به یک دنباله‌ی آینه‌ای میرسیم که البته نسبت به جایگاه ۰ آینه‌ای هستن. برای همین دنباله‌ی ما از f_0 نمیتونه آینه‌ای بشه.
اولین i خود ۱ و -۱ باشه: که در این صورت اگه فرمول رو بنویسید می‌رسید به f_1= - f_-1 که نتیچه میده i=2*j و با استقرا ثابت میشه که این هم حالتی از جوابه.
و اینجوری ثابت میشه دنباله‌هایی که یا f_0=0 با f_1=2*f_j هست جواب مسئله است.
۲) این جور سوال‌ها که بر میگردن به روابط بازگشتی بهشون میگن dynamic. مثلا توی این سوال وقتی میخوایم c_i,j رو حساب کنیم, باید ببینیم که چطور مسئله‌ی حل از i تا j رو به حل یه تعداد r تا k تبدیل کنیم. البته باید همیشه توجه کنید که توی دور نیفتیم, یعنی از حل i,j دوباره نرسیم به خود i,j. البته در این سوال‌ها یک سری حالت اولیه هم در نظر گرفته میشه که جوابشون بدیهی تلقی میشه, مثلا در این سوال c_i,i صفر در نظر گرفته میشه. در این سوال هم کافیه توجه کنیم که در حالت بهینه برای حل i,j ما آخرین حرکتمان جوش دادن دو تکه میله هست که یکی شامل میله‌های از i تا k هست و اون یکی شامل از k تا j که k میتونه از i+1 تا j-1 باشه. پس c_i,j مساوی خواهد بود با مینیمم
c_i,k + c_k+1,j + w_i,k + w_k+1,j
که در اون k از i+1 تا j-1 هست و w_x,y هم به معنای جمع وزن میله‌های از x تا y هست.
برای حساب کردن c_1,n هم کافیه یه جدولn*n بکشید که در اون درایه‌ی x,y نشون‌دهنده‌ی c_x,y باشه و حالا اول همه‌ی اونهایی رو بدست بیارید که y-x=1 هست. بعد اونهایی که y-x=2 هست, همیونجور ادامه بدید تا اونهایی که مساوی n هست.
۳) بیاید برای هر شهر یک تابع f در نظر بگیرید که f شهر a میشه اون مجاوریش که اگه جاده‌ی بین a و اون مجاور رو حذف کنیم, زیر کشور اون مجاوره بیشتر از 2n/3 بشه. واضحه که f یه نفر بیشتر از یه شهر نیست. حالا سوال اینه که آیا شهری هست که f نداشته باشه؟ (چون اگه همه‌ی رئوس f داشته باشند که بدیهیه مسئله جواب نداره و اگه یه راس بدون f پیدا بشه, کافیه که اون یالی رو حذف کنیم که زیر کشور تشکیل شده‌ی دارای مجاورش ماکزیمم راس را داشته باشد)
خوب حالا برهان خلف میزنیم, اگه همه f داشته باشند, کافیه یه راس a رو در نظر بگیریم. حالا میریم سراغ f_a و بعد سراغ f_f_a و همینطور ادامه میدیم و هر دفعه میریم به f راسی که داخلش هستیم. این مثل حرکت روی جاده‌ها میمونه. ار اونجایی که توی جاده‌هامون دور نداریم(بین هر دو شهر دقیقا یک مسیر وجود داره) و تعداد راس‌ها هم متناهیه, پس یه زمانی از جاده‌ای که اومدیم دوباره برمی‌گردیم. خوب این یعنی هر ور جاده 2n/3 شهر داره که تناقضه
این یه روش استقرا داره که میگه اگه طی مراحلمون به n(طول جایگشت) رسیدیم که در مرحله‌ی بعدی n به اول جایگشت میاد و ازگردونه حذف میشه و بقیه هم طبق استقرا حل میشند. و اگه هم هیچوقت n نیاد که خوب مسلما هیچوقت عددی که در اول جایگشت هست هم استفاده نخواهد شد برای همین هیچ عیبی نداره اگه جای n رو با اون عدده عوض شده فرض کنیم. و حالا هم با استقرا باز به نقره‌ای خواهیم رسید.
این سوال یه روش با حال هم داره که میاد میگه به هر حایگشت یک عدد در مبنای ۲ میدیم. اینجوری که اگر عدد سمت راست ۱ بود, بیت سمت راست رو میذاریم ۱ وگرنه ۰. برای بقیه هم همینطور, اگه نفر i ام از سمت راست جایگشت برابر با i بود, بیت i ام از راست ۱ وگرنه ۰ است. حالا نکته اینجان که با یک عملیات روی جایگشت اگر نفر سمت راست ۱ بوده باشد که عدد ما هیچ تغییری نمی‌کند وگرنه عددمان بزرگ می‌شود(خودتان اثبات کنید) و چون عددمان از ۲ به توان n نمیتواند بیشتر شود لذا زمانی محبور است به جایگشت نقره‌ای برسد.
۵)خب این با قضیه‌ی هال که بدیهیه. بدونه اون هم با استقرا میشه گفت. اون جعبه‌ای که یدونه داره که واضحه باید از اون جعبه همون مهرهه انتخاب بشه, حالا فرض کنید اسم اون جعبه a باشه و مهره‌ی داخل اون b باشه. حالا که ما b رو انتخاب کردیم, باید ببینیم که کدوم جعبه b داشته(اگه هیچ کس دیگه‌ای نباشه که خوب رسیدیم به حالتی که از همه دقیقا ۲ تا داریم و با روشی شبیه به همین حله.) میایم اون جعبه‌ای که b رو داشت در نظر میگیریم و فرض میکنیم که b از توش حذف شده. حالا مثل اینه که رسیده باشیم به حالت فرض استقرا و همینطور ادامه میدیم تا تموم بشه.
۱۳۸۵/۰۲/۱۷ · ۲۴:۵۶
مرحله ۲ روز دوم
۶) این روشی که گغته برای یه خونه عددش میشه فلان, مثل اینه که عدد هر خونه بشه جمع همه‌ی اعداد سطرش بعلاوه‌ی جمع همه‌ی اعداد ستونش.(توجه کنید که جمع در Z2 میشه همون xor هست). که البته چون خودش دوبار حساب میشه, خودش تاثیر نداره. حالا فرض کنید به جدول داریم که جمع اعداد ستون i میشه a و جمع اعداد ستون j میشه b. (توجه کنید که a و b یا ۰ یا ۱ هستن) عدد سطر k ام ستون i می شه جمع اعداد سطر k و a. عدد سطر k ام ستون j می شه جمع اعداد سطر k و b. حالا اگر a=b بود این دو عدد مساوی وگرنه مخالف همدیگه می شند. پس اگه یه جدول اصلاحپذیر باشه اعداد ستون i ام یا همه مساوی یا همه مخالف اعداد ستون j ام هستند. (همچنین برای سطرها) حالا میخوایم ثابت کنیم جمع اعداد هر ستون مساویه. فرض کنید ستون i بشه a. اونهایی که مساویه ستونه‌هن که هیچ. اونهایی که مخالفه‌شن جمعشون میشه (n-a) که چون n زوجه (n-a) هم میشه همون a. پس جمع اعداد همه‌ی ستون‌ها یکسانه(و سطرها هم یکسانه). خوب حالا که جمعشون یکسانه برگردیم به ۴-۵ خط بالاتر. نتیجه میگیریم که همه‌ی ستون‌ها با هم مساویند(و همه‌ی سطرها هم). چون همه‌ی ستون‌ها مثل همند اگر خانه‌ی (i,j) یک باشه اونوقت سطر i و در نتیجه همه‌ی سطور ۱ میشوند. پس یا همه‌ی اعداد ۱ هستند و یا همه ۰. اگه همه ۰ باشند که خوب مستقیما مرحله‌ی بعدی به خودمون میرسیم. اما اگه همه ۱ باشند مرحله‌ی بعد به همه ۰ میرسیم و هیچوقت دیگه به همه ۱ نمیرسیم. پس جواب سؤال میشه تنها یک جدول و اون هم همه ۰.
۷) این سؤالیه که مسلما چندین راه داره ولی یه راهه خیلی آسون و کوتاهش اینه: بیاین ۲نفر ۲نفر دسته بندیشون کنید(نفر ۱۳۸۵ تنها میمونه). حالا نفر اول هر دسته میاد رنگ کلاه نفر دوم رو مینویسه و نفر دوم هم معکوس رنگ نفر اول رو مینویسه. اینجوری اگه رنگشون برابر بوده, نفر اول وگرنه اگه مخالف باشه نفر دوم درست گفته. اینجوری نزدیک به ۵۰٪ افراد درست خواهند گفت.
۸) از طرز سوال بدیهیه که با خیابان‌های موازی محورها نمیشه و با مورب‌ها میشه.
اینکه چرا موازی‌ها نمیشن: فرض کنید اگه مثلا خونه‌ی شهردار سمت راست یه خیابان عمودی باشه و اول کار به سمت پایین بره (بقیه هم به همین صورته), اونوقت همیشه یا سمت راست خیابان‌های عمودیه یا سمت بالای خیابان‌های افقیه. و برای همین همیشه یا داره به سمت پایین میاد یا به سمت چپ و هرگز به خودش نمیرسه. البته این رو میشه با استقرا روی تعداد چهارراه‌های رفته اثبات کرد.
اینکه جرا مورب‌ها میشه: میشه با ۳ جاده حرکت پیچش به راست رو شبیه‌سازی کرد. یعنی در سمت راست یک جاده حرکت کنی و به سمت راست بپیچی ولی همچنان در سمت راست جاده بمانی. حالا که این حرکت رو داریم خیلی راحت میتونیم دور بزنیم و به خودمون برسیم.
۱۳۸۵/۰۲/۱۴ · ۱۰:۱۴
مرحله ۲ روز اول
۲) نقش رو تعریف میکنیم خطی که مینیمم مسیر رو از گوشه‌ی بالا سمت چپ به پایین سمت راست رو طی میکنه و البته از روی محیط قالیها میگذره. حالا فرض استقرا اینه که ما هر نقشی که کمتر از k تا قالی توشه میتونیم درست کنیم. حالا واسه k قالی میایم اون قالی رو در نظر میگیریم که بالا و سمت راستش خالیه ( مثلا میتونید از روی نقش اولین حرکت سمت راستمون رو دنبال کنید و به محض اینکه حرکت سمت پایین کردید این جا همون قالین). خوب حالا این قالیه رو حذف کنید و طبق استقرا بقیه رو بسازید و بعد هم اینو اضافه کنید.
۳) اول همه‌ی لامپ‌ها رو رندوم میبندیم به کلیدها. حالا دو حالت پیش میاد:
الف) یدونه لامپ روشن بشه: که بدیهیه: با ۱۰۰ حرکت خرابها رو درمیاریم و هر کلیدی رو با لامپ سالمه چک میکنیم اگر روشن شد که میفهمیم کلید درسته و لامپه نظیرش خراب بوده. اگر هم روشن نشه فقط میفهمیم که کلید خرابه. از این دومی ۵۰ بار اتفاق میفته که لامپ‌های نظیرشونرو میتونیم با اون کلید درسته چک کنیم و حله.
ب)هیچکی روشن نشه: که خوب پس یار هر کس دقیقا برعکسه خودش بوده. پس ۵۰ تای اول رو در خودشون یکی شیفت میدیم جلو(یعنی ۱ به ۲, ۲ به ۳, ... , تا ۵۰ به ۱). اگه کسی روشن نشد که تابلویه وگرنه یه دونه روشن میشه. حالا بوسیله‌ی این و شبیه به بالا حل میکنیم البته توجه داشته باشید که با تعیین هرکس وضعیت اون یار قبلیش هم معلوم میشه.
اینکه چرا میشه ۲۵۰ تا حداکثر, خودتون چک کنید.
۴) سوال هم ارزه با اینکه بگیم: دو رشته اگر حداکثر در ۲ بیت تفاوت داشته باشند باید کد متفاوتی براشون خرج بشه. که این اگر کدمون حداکثر k باشه غیر ممکن و اگر k+1 باشه حتما ممکنه. که مسئله مورد اول رو می‌خواد. کافیه بیاین یدونه رشته رو با همه‌ی کسانی که باهاش تو یه بیت تفاوت دارند رو در نظر بگیرید. این دو به توان k بعلاوه‌ی ۱ رشته میشه. که چون با k بیت کد حداکثر دو به توان k حالت میشه پوشوند لذا دو تا از این رشته‌ها کد یکسان دارند و نمیتوان بینشان تفاوت گذاشت.(در حقیقت نمی‌فهمیم که کدامیک از اینها منظور فرستنده بودند.)
اینها هم تقریبا حل-راهنمایی بودند و مقداریش رو باید خودتون ثابت کنید.
۱۳۸۵/۰۲/۱۳ · ۱۳:۵۷
۳ تا سوال
جواب 2) داریم استقرا میزنیم روی n. اگه یکی از بازه‌ها کاملا در یکی دیگه قرار داشته باشه، کافیه اون بزرگه رو حذف کنیم و سپس بنابر استقرا اون k-1 نقطه‌ی مناسب رو انتخاب کنیم. حالا چون یکی از نقاط داخل کوچیکه هست، پس از بزرگه هم یکی انتخاب شده و تموم. حالا فرض کنیم حالتی هست که هیچ بازه‌ای کاملا داخل دیگری نیست. میایم همه نقاط شروع بازه‌ها رو مرتب میکنیم. حالا زودترین شروع رو در نظر بگیرید. بیاید نقطه‌ی انتهای این بازه رو بعنوان یکی از نقاط انتخابیمون در نظر بگیرید. چون همه‌ی بازه‌هایی که بین شروع و پایان این بازه، باز شدن، بعد از پایان این بازه، بسته شده‌اند(وگرنه کاملا داخله بازه‌ی انتخابیه ما میومده)؛ لذا با انتخاب این نقطه‌ی خاص، از همه‌ی بازه‌هایی که قبل از بسته شدن اولین بازه، باز شده‌اند، یک نقطه انتخاب شده. پس حالا همین کار را ادامه میدهیم. یعنی باز اولین بازه‌ای رو در نظر میگیریم که بعد از تمام شدن اولی، شروع شده. و نقطه‌ی انتهایش را بعنوان یکی دیگر از نقاط انتخابی در نظر میگریم. و همینطور ادامه میدهیم. واضحه که همه‌ی بازه‌ها حداقل یک نقطه‌یشان انتخاب شده. حالا میمونه ثابت کنم تعداد نقاط حداکثر k-1 هست. این هم واضحه چون بازه‌هایی که ما نقاط انتهایشان رو انتخاب کرده بودیم، کاملا جدا از هم هستند، لذا اگر تعداد این بازه‌ها بیشتر از k-1 باشد، اونوقت توانسته بودیم که k تا بازه در نظر بگیریم که با هم هیچ اشتراکی ندارند و این با فرض مسئله در تناقضه.
جواب 3) یه گراف جهت‌دار وزندار می‌سازیم. اینطوری که به ازای هر حالت از چینش کتابها(حداکثر میشه دو به توان n در n فاکتوریل) یک راس میذاریم. و از راس a یک یال جهت‌دار به b با وزن i میذاریم اگر بوسیله‌ی swap_to_i بشه از حالت a به b رسید. توجه کنید که این گراف به ازای هر یال از a به b یک یال با همون وزن از b به a داره.(در حقیقت یه جورایی این رو میشه بصورت گراف بدون جهت دیدش ولی برای اثبات راحت‌تر اینجوری در نظر میگیریمش). حالا اعمال ما مثل طی کردن یک گشت توی این گراف میمونه. چون تعداد یال‌ها متناهیه زمانی ما از یک یال مجددا عبور خواهیم کرد(همینجا جهت‌دار بودنش کار رو راحت میکنه). پس یال e اولین یالی هست -مثلا با وزن i- که پس از طی چند عمل دوباره به خودش میرسه. بدیهیه که نه تنها e بلکه همه‌ی یالهای توی گذر بسته‌ی از e به e همینجوری هستن و چون یه یال توی این گذر هست که وزنش یکه(کافیه اینقدر طبق الگوریتم حرکت کنیم تا برسیم به 1 دیگه). فرض کنیم این یال 1 که بوسیله‌ی حرکات الگوریتممون توی یک گذر بستن، از a به b باشه. پس ما از a با شروع از یال 1 و طی چند حرکت میرسیم به خودش. این دقیقن مثل وقتی هست که ما از حالت اولیمون شروع کردیم به حرکت. نکته اینجان که ما اگه از راس فلان طی چند حرکت به خودش برسیم، از هر راس دیگه‌ای هم اون حرکات خاص رو انجام بدیم باز به خوده اون راسه میرسیم. بعبارت واضح‌تر حرکات ما مستقل از وضعیت کتابا هستن. لذا اگه یه راس بتونه با شروع از 1 برسه به خودش(که راس a الآن اینجوریه) راس شروع ما هم باید براش همین اتفاق بیفته.
خوب اینم از حل سوالا. کلی واستون مرام گذاشتما. آخه بجای اینکه برم بازی کنم دارم واسه شما چرت و پرت تایپ میکنم. البته اگه اینجوری که من نوشتم توی امتحان بنویسید 0.0000000001 هم نمیشید. من تقریبا بعنوان یه راهنمایی-حل نوشتمش.
۱۳۸۵/۰۲/۰۱ · ۰۹:۴۲