المپیاد کامپیوتر

سلام
قبل از همه عنوان رو خوب نگاه کنید اول شاید خیلی پرت باشه اما از زمانی که من این پست رو میزنم(2-3 ساعتی اینور اونور)
4.5 روز دیگه و 108 ساعت دیگه یعنی 6480 دقیقه دیگه دقیقاً 388800 ثانیه دیگه جوابا رو سایت باشگاه میزارند حتیاگه همه
سؤالا رو درست دقیق جواب بدی تا این زمان احتمال قبولیت بیشتر از 10%-15% نیست.(پس همونطور که روزبه گفت به فکر لباس نباشید)
اگر هم قبول شدید یا نشدید فرقی نمی کنه چون به قول معروف اونایی که تا طلای جهانیش هم رفتن
" چیزهایی رو که با المپیاد میشه بدست آورد بدونه المپیاد هم بدست میان."
                                                    فعلاً یا حق
                                                                            لحظه ها را باید ساخت
                                                              راه را همین امروز باید رفت
                                                              زندگی را زندگی باید کرد
                                                              خدا را همین نزدیکی باید یافت
                                                                                                                                                          قربانتان فرید

این هم چندتا کتاب برای برو بچ ریاضی ولی به راحتی ترکیبیات توشون پیدا می شه .(سؤالات جمع آوری شدست بی نظیره)
1و2 انگلیش         3و4 پرشن                                      1
                                                                           2
                                                                           3
                                                                           4

بسم الله
الان قصد دارم براتون فقط درباره کتابای المپیاد کامپیوتر مرحله اول حرف بزنم خوب از قدیمیا که بپرسی واسه مرحله اول فقط یه ذره هوش زیر اتمی با ده تا انگشت سالم برای شمردن کافیه حالا واسه شروع بهترین کتاب رو میگم:
1.ترکیبیات علیرضا علیپور
انتشارات فاطمی از همه بهتره این کتاب دارای مطالب زیادی که همون فصل اول
از همه بهتره بحث های 3و4 فصل اولش با لانه کبوتری وشمول برای مرحله اول
بس این کتاب رو طوری که خودش گفته با معلومات دوره راهنمایی هم می شه خوند.

2.الفبای المپیاد ریاضی وکامپیوتر مرتضی محمدآبادی انتشارات دانش پژوهان جوان این کتاب دو ویرایش داره که
برای مرحله اول همون فصل اولش کافیه بقیش به درد مرحله دوم می خوره.

3.المپیاد کامپیوتر 6نفر نوشتن
قلم چی چاپش کرده جدید مخصوص مرحله اول خیلی هم سادس واسه شروع از این
بهتر نمی شه همه چیز رو گفته اگه بخونید مرحله اول رو کم نمی آرید.

4.المپیادهای کامپیوتر در ایران(مرحله اول) رسول حاجی زاده خوشخوان مهمترین و مؤثرترین کتاب برای قبولی همینه کل
سؤالات سالهای 74-84 با جواب تشریحی رو داره کسی که اینو بخونه اگه خنگ
نباشه 100% قبوله اما من توصه می کنم موقع حل تا وقتی به جواب نرسیدی پاسخ
نامه رو نگاه نکن مخصوص هفته قبل امتحانه.
تو پست بعدی با ریاضی ومراحل دیگه کامپیوتر میام پیشتون.
                                                                                                     قربانتان فرید

یا الله
من سال دوم هستم (ریاضی) .از بچه های سمپاد شهرستان های غربی کشور ام.
عشق المپیاد از نوع های کام وریاضی و متفرقاتش هستم .
مرحله اول کام رو آوردم تو ریاضی م به آزمون نرسیدم و گر نه الاندوتاشو حال می کردم تو راند 2 خوب نمی دونم شاید قبول نشم ولی
باز ارزششو داره کمش65میآرم آخرش 130می آرم دیسگه خدا میدونه.
یه نفر هم گفته بود یه تقدیرنامه فرستادن خونمون اونا یه مؤسسات هستن که در عوض یه پول حسابی می خوان چندتا جزوه بفرستن برات اما شما گولشون رو نخورید. به درد نمی خوره.(خودم تجربش رو دارم اینا رو برای همه می فرستن مهم نیست که قبول شی یا نه.)
فردا یا هفته آینده چندتا منبع قابل دسترس رو از مقدمات تا  المپیادبراتون مینویسم.
                                                                                                                       قربانتان فرید

المپیاد ریاضی لنینگراد یک مجموعه سؤال عالی که یکی ازطلاهای ریاضی دانش آموزی ودانشجویی ایان وجهان رمز موفقیت در مبحث شیرین ترکیبیات رو این کتاب می دونه برای راحتی دانلود تو 3 قسمت گذاشتم                                
                                                                                                                            قربانتان فرید
                                                                                       1
                                                                                       2
                                                                                       3   
                                                                                     یا حق

اونایی که امیدی به مرحله 2 کام ندارند میتونن سال دیگه ریاضی بخونن این هم از مرحله 2 ریاضی از76تا86
                                                                                     کلیک
                                                                    ناامید نشید ولی پشیمونم نشید.
                                                                                 یا حق

چند تا سؤال آبدار واسه مخ های المپیادی(البته به ریاضیات نیاز نداره!!)

1-       نردبان
طنابی یک قایق از یک طرف در آب آویزان شده است. اندازه ی نردبان به گونه
ای است که فقط تا سطح آب است. اگر بر اثر جزر و مد ارتفاع آب 4 فوت بالا
بیاید و فاصله ی دو پله ی نردبان 8 اینچ باشد به نظر شما چند پله از
نردبان به زیر آب خواهد رفت؟

2-       ساعت خورشیدی یک گاه شمار با حداقل حرکت است. گاه شماری که بیشترین حرکت را دارد چیست؟

3-       سه
نفر وارد هتل می شوند و 30 دلار به مدیر هتل می دهند و هر کدام وارد اتاق
هایشان می شوند. مدیر هتل می فهمد که 5 دلار از انان اضافه گرفته است، پس
5 دلار را به پادو می دهد که به آنان برگرداند. پادو می بیند که تقسیم
کردن 5 دلار بین 3 نفر سخت است و لذا 2 دلار در جیبش قرار می دهد و به هر
نفر یک دلار بر میگرداند. حالا هر نفر که در ابتدا 10 دلار داده بود 9
دلار داده است و مجموعا 27 دلار می شود 29 دلار. به نظر شما آن یک دلار چه
شده است؟

4-       دو
مرد و دو زن در یک طرف رودخانه ای قرار دارند. آنها می خواهند از رودخانه
عبور کنند. یک قایق در آن جا قرار دارد اما متأسفانه آن قایق ظرفیت دو  نفر
را دارد. یک زن می تواند در 5 دقیقه و زن دیگر در 10 دقیقه، یک مرد در 20
دقیقه و مرد دیگر در 25 دقیقه از رودخانه عبور کند( یعنی این که اگر دو زن
با هم از رودخانه عبور کنند بایستی زمان حداقل را زمان فردی در نظر گرفت
که کندتر می رود یعنی 10 دقیقه و اگر دو مرد از رودخانه عبور کنند 25
دقیقه طول خواهد کشید). به نظر شما آن ها چگونه می توانند در عرض 1 ساعت
از رودخانه عبور کنند؟

5-       چگونه می توانید اعداد یک تا 9 را در یک جدول 3 در 3 قرار دهید به طوری که از هر طرف جمعشان 15 شود؟

6-       فرض
کنید اداره ی تاکسیرانی نیاز به رانندگانی بیشتر داشته باشد، در حالی که
آموزش راننده ی حرفه ای که با مناطق مختلف شهر آشنا باشد، یک سال وقت لازم
دارد. چطور می توان مشکل اتحادیه را خیلی زود حل کرد؟

این کتاب رو از رضا دوست بسیار گرامیم گرفتم آدرسش: http://www.olampyad-best.blogfa.com 
                                                                                                                            میتونید با یک کلیک دانلود کنید.
یک شایعاتی هست درباره مرحله دوم که کفش 97 است اما هیچ اعتباری نداره تازشم می گن که به قبولی ها زنگ زدن ولی باور نکنید.
                                                              البته کف همین دوروبر 100-95 هست.
                                                                                   تا بعد
                                                                                   یا حق

سؤالها  http://www.mmehraban.blogfa.com/post-17.aspx
جوابها :

روز1
1)
این سوال یک حکم ضعیف داشت زیرا می توان ثابت کرد می توان |n\2 | خانه انتخاب کرد که هر کدام حداکثر 1 بار آمده باشد
ابتدا عدد یک را از ستون اول انتخاب می کنیم سپس عدد 2 را در این ستون در نظرگرفته و سراغ سطری می رویم که شامل عدد یک انتخابی و این عدد 2 در این ستون نباشد سپس عدد 2 را در آن انتخاب می کنیم
به همین ترتیب در هر مرحله تمام اعدادی را که قبلا انتخاب کردیم انتخاب میکنیم و مثلا اگر عدد بعدی که می خواهیم انتخاب کنیم k باشد آنگاه تمام ستون هایی را که قبلا از آنها عدد انتخاب کردیم را انتخاب کرده و تمام سطرهای شامل این k ها را در نظر می گیریم و عدد k را از سطری غیر از این سطر ها و سطرهایی که قبلا از آنها عدد انتخاب کردیم انتخاب می کنیم بدین ترتیب هم اعداد متمایزند و هم هیچکدام در هیچ سطر یا ستونی نیستند زیرا همیشه ما ستونی داریم که عدد بعدی را از آن انتخاب کنیم زیرا تعداد اعدادی که ما قبلا انتخاب کردیم حد اکثر 1-|n\2 | تا هست و عدد بعدی حداکثر در 1-|n\2 | تا سطر متمایز دیگر آمده و چون می دانیم n بزرگتر است از 2-|n\2 |2 پس همواره سطری برای انتخاب ما وجود دارد

2)
الف)این قسمت سوال بر خلاف قسمت قبلی بسیار بدیهی است به این صورت عمل می کنیم که خانه بالا و سمت چپ را به صورت مارپیچ با خانه های 1*1 ادغام میکنیم
ب) دو دنباله a ها و b ها را در نظر بگیرید اولی فقط 1 و2 دومی بیشتر از 2می دانیم تعداد این ها برابر است زیرا در هر مرحله یک شکل از مجمه n به توان 2 شکل کم می شود و در نهایت یکی می مونه پس در نهایت n به توان 2 منهای یک تا عضو a ها و همین قدر b ها دارند
یک های موجود در مجموعه a ها را حذف و به همین مقدار از مجموعه b ها یک کم می کنیم سپس :
برهان خلف :بنابر قضیه کوشی شوارتز اگر a ها به توان 2 را در تعدادشان ضرب کنیم بزرگتر مساوی مجموعشان به توان 2 است و چون همه a ها برابر 2 است پس حالت تساوی رخ می دهدولی اگر همین کار را برای b ها بکنیم حالت تساوی رخ نمی دهد زیرا در بینشان اعداد برابر وجود ندارد و چون مجموع b ها و a ها برابر است پس توان دوم a ها کوچکتر است از توان دوم b ها و چون می دانیم تهدادشان برابر است پس با استفاده از 2 ها و 1 ها به طور یکتا می توان این دنباله را تشکیل داد که تعداد 2 ها و 1 ها در آن همواره ثابت است.
این کلیت اثبات است اما نواقصی دارد که به دلیل طولانی بودن در اینجا نمی گنجد.

3)
از انتها به ابتدا رنگ آمیزی را بررسی میکنیم در ابتدا یک جدول n درn داربم می دانیم آخرین رنگ یا یک سط یا یک ستون را شامل می شود پس این ستون یا سطر را از جدول برداشته و بقیه را بررسی می کنیم حال یک جدول n-1 درn داریم در هر مرحله از آخر به ترتیب به اول رنگ ها را به این ترتیب از جدول جدا می کنیم چون می دانیم در هر مرحله یکی از ستون یا زا سطر کم میشود و این کار زمانی تمام می شود که یا ستون یا سطر برابر صفر گردد پس حداکتر ما 2n-1 رنگ می توانیم استفاده کنیم

4)
الگوریتم این سوال به این صورت است : ابتدا به خانه اول می رویم و در آنجا می مانیم تا یک شبکه را دوبار ببینیم سپس به سالن بعدی می رویم اگر شبکه ای که در آنجا می بینیم را قبلا دیده ایم به سالن بعد می رویم وگر نه در آنجا میمانیم تا یک شبکه را ببینیم که قبلا دیده ایم اثبات درست بودن این الگوریتم هم ساده است
روز2
5)
باید ثابت کنیم شکل مورد نظر یک ستاره است که یک شهر در مرکز قرار دارد و اگر d برابر 2k باشد شاخه های این ستاره هر کدام k تا شهر را شامل می شود و اگر d برابر 2k+1 باشد یک شاخه شامل k-1 راس و بقیه شامل K+1 راس هستند و صورت کلی این تعداد برابر است با n -1 منهای کف d\2 سپس حاص این عبارت تقسیم بر سقف d\2 سپس حاصل کف این عبارت به علاوه یک

6) n کلمه زبان پیشوند آزاد را در نظر می گیریم و برای هر کلمه ابتدا تمام حروف آن را نوشته سپس مجددا حروف آن را از آخرین حرف به اوین حرف دنبال آن می نویسیم و به سادگی ثابت می شود که این کامه هم پیشوند و هم پسوند آزاد است بنابراین چون وزن آن برابر 2x است پس حکم ثابت می شود

7)این سوال انصافا سخت ترین و قشنگترین سوال این دوره بود اما به دلیل سختی تایپ آن نمی توانم به صورت کامل اثبات را بنویسم
و تنه ابه صورت کلی راه حل بسنده می کنم
به این صورت عمل می کنیم که n زیر مجموعه 3 عضوی را در نظر می گیریم و درجه هر عدد را تعداد تکرار آن در این زیر مجموعه ها می نامیم سپس اعداد را به ترتیب از تعداد درجه کم به تعداد درجه زیاد مرتب می کنیم در هر مرحله از درجه کمتر شروع می کنیم و به ترتیب اعداد را از درجه کمتر به بیشتر بررسی می کنیم در هر مرحله یک عدد باقیمانده را که درجه آن از بقیه کمتر است را برمی داریم و رنگ می کنیم اگر هیچ زیر مجموعه ای نسازد که سه عضو آن رنگ شده در غیر این صورت آن را رنگ نمی کنیم و به سراغ عدد بعد ی می رویم و با استفاده از این نکته که مجموع درجات برابر 3n است و این که اگر عددی رنگ نشده به معنای آن است که حداقل یک زیر مجموعه 3 عضوی تکمیل شده که 2 عضو قبلی آن را رنگ کردیم و همچنین اینکه در هر مرحله میانکین درجات اعدادی که بررسی کردیم کوچکتر یا مساوی 3 است می توان نتیجه گرفت که حکم درست است

8)
الف ) باید تمام حالات ممکن برای قرار گیری دایره های a و bو c وd را در نظر بگیرید با این کار حکم ثابت می شود
ب)به استقرا ثابت می کنیم که حکم ثابت است برای پایه استقرا که واضح است حال فرض کنید برای n درست است می خواهیم برای n+1 ثابت کنیم فردی را در نظر بگیرید که با بیشترین تعدا افراد آشناست آن فرد را از گروه حذف می کنیم بنا بر فرض استقرا برای بقیه افراد می توان این دایره ها را رسم کردحال فردی را که حذف کردیم وارد این جمع کرده و تمام کسانی که این فرد با آنها دوست است را وارد دایره این فرد می کنیم توجه کنید که در این کار تمام دایره هایی را که یکی از این افراد در آنهاست و تمام دایره هایی که درون دایره تمام این افراد است را با آنها وا رد دایره فرد ی میکنیم که حذف کردیم اگر کسی باشد که با این فرد دوست نیست ولی با یکی از دوستان این فرد دوست است و وارد دایره این نفر شده آنگاه بنا بر قسمت الف چون می دانیم یک راس وجود دارد که با یکی از دوستان فردی که حذف کردیم دوست است اما با آن دوست نیست می توان نتیجه گرفت که همان فردی که با فردی که حذف کردیم دوست است و با کسی دیگری هم دوست است تعداد دوستانش از راسی که حذف کردیم بیشتر بوده پس به تناقض می رسیم و حکم درست است .
البته اینها در واقع قسمتی از راه حل اصلی است و بقیه راه حل با همت خود خاننده به راحتی کامل می شود امسال سطح سوالات از پارسال سخت تر بود و کف هم احتمالا تا 100 برسه امید وارم همه خوب داده باشین لطفا اگر ایرادی در این جواب ها هست یا جایی جوب زده شده حتما بگید ممنون میشم لطفا هر کسی هم میاد بگه خودش و مدرسش چیکار کردن تا دوستان دیگر تغریبا از کف قطعی مطلع شوند امید وارم همه این امتحانو خوب داده باشین و قبول بشین البته بنا بر اصل لانه کبوتری این دعا رو تنها برای تعداد خاصی باید بکنم در پایان هم به قول آریو دی ... و به قول دوستان مینی المپیاد یا حق

به نام او
امروز سر آغاز سال جدید برای المپیاد کامپیوتر البته راند 2 تموم شد خودم فکر نکنم قبول شم اما برای بقیه منویسم چه اونایی که میرن تو دوره چه سال اولی ها منو فرید صدا بزنید با هر کس که بیاد همکاری میکنم امیدوارم همتون به اون جایی که می خواید برسید تو پیوند ها بهترین ها رو گذاشتم حتمآ نگا کنید راستی برای همکاری با من تماس بگیرید.    faridtoo2008@gmail.com
تو پست بعد سؤال و جواب راند 2 بی اعتباره ولی یه نیگا بندازید از دوستم مهربان گرفتم.