مرحله 1

سلام ، خوبین؟ خوش می گذره؟

همون طور که می دونید مرحله ۱ نزدیکه. بهترین کار توی این ایام امتحان گرفتن مرحله ۱ ها از خودتونه. چون مرحله ۱ ، تقریبا بلافاصله بعد از امتحانات ترم اوله ، بهتره از همین الان شروع کنین تا قبل از مرحله ۱ ، حداقل ۵ تا مرحله ۱ رو داده باشین. اگه سال اولی هستین، این چند سال اخیر رو سوالاش رو نبینید و امتحان ندین تا سال دیگه که براتون مهمتره سوال داشته باشین که امتحان بدین. پس جو گیر نشین همه مرحله ۱ ها رو بدین که سال دیگه ندونین چه کار کنین!

مثل امتحان وقت بذارین و توی اون وقت سوالات رو حل کنید. تفریحی و پراکنده سوال حل نکنید. بعد از امتحان حتما جواب های صحیح رو چک کنید و اگه از کتاب استفاده می کنید ، جواب های صحیح سوالات رو بخونید. ( حتی سوالاتی که حل کردین، چون ممکنه یه ایده جدید یاد بگیرین. )

انتشارات خوشخوان برای مرحله ۱ ها کتاب داره، ولی نمی دونم آخرین نسخه اش الان تا چه سالی رو داره. اما می تونید سوالات رو از اینترنت بگیرین ، کلیدش رو هم توی سایت باشگاه ، همین وبلاگ یا وبلاگهای دیگه پیدا کنید.

همین دیگه ، موفق باشین! امتحان هم ساده خواهد بود ، اصلا نگران نباشید! ( برنامه نویسی هم نمی خواد!!! )

پ.ن. : الان از توی کتابخونه باشگاه پست می زنم و سرعت اینترنتش کمه!!  اگه کسی سایتی پیدا کرد که سوالات مرحله اول رو داشته باشه ، تو قسمت نظرات لینکش رو بده.

جواب ها

سلام به همگی.

-تو جواب ها بیشتر ایده های کلی رو نوشتم تا خودتون رو بقیه اش فکر کنید. البته نکات جزیی خیلی مهمه و بخش مهمی از راه حله. بیشتر جوب زدن ها هم تو همین نکات جزیی رخ می ده که معمولا وقتی جواب رو می نویسید  معلوم میشه.

-اینا جواب هاییه که به ذهن من رسیده و ممکنه جواب های بهتر و قشنگ تری هم وجود داشته باشه. اگه کسی خواست می تونه جواب های خودش رو تو نظرات بنویسه.

اینم جواب ها:

۱- افراز متوازن:

اول یه لم مهم رو ثابت کنید: صورت لم همان صورت مساله است با این تفاوت که از شما خواسته اند وزنه ها را به دو دسته تقسیم کنید به طوریکه اختلاف آنها ۲ به توان k باشد. k را به شما می‌دهند و می دانید ۲ به توان k از همه وزنه ها مقدارش اکیدا بیشتر است. باید ثابت کنید تعداد راه های افراز وزنه ها با این شرایط صفر یا توانی از دو است.

این لم را می توانید با استقرا روی k و حالت بندی روی تعداد وزنه هایی که وزنشان ۲ به توان k-1 است(در گام استقرا) ثابت کنید.

مساله اصلی را نیز می توان با استقرا روی وزن بزرگترین وزنه و حالت بندی روی تعداد این وزنه ها و استفاده از لم بالا اثبات کرد.

۲- سپید و سیاه:

یک راه‌حل منطقی این است که ثابت کنید تا وقتی حداقل دو خانه سیاه داریم می توان تعداد خانه های سیاه را کم کرد. برای این کار دو خانه سیاه را در نظر بگیرید که فاصله شان از همه کمتر است. با این فرض می توان نتیجه گرفت که در زیر مستطیلی که این دوخانه در گوشه های قطری‌اش هسند هیچ خانه سیاه دیگری نیست. حالا با حالت بندی روی طول اضلاع این مستطیل سعی کنید تعداد خانه های سیاه را کاهش دهید. به این نکته هم دقت کنید که m و n (طول اضلاع جدول اصلی) هر دو حداقل ۳ هستند.

۳- گراف یابی:

ثابت کنید تعداد پرسش ها حداقل (C(2, n است. یعنی حالتی وجود دارد که مملی مجبور است به ازای هر جفت از راس ها از ففلی یک سوال بپرسد. (اگر ففلی به ازای هر سوال که مملی می پرسد بگوید فاصله آن دو راس بی نهایت است، یعنی آن دو به هم هیچ مسیری ندارند، مملی مجبور است همه جفت ها را از ففلی بپرسد).

۴- ماتریس کم تنوع:

کافی است که از روی یک ماتریس a*a با تنوع p و یک ماتریس b*b با تنوع q، یک ماتریس (ab)*(ab) با تنوع p.q بسازید.

موفق باشید.

خداحافظ!

سوال.

به نام خدا

سلام به همه رفقا. عید قربان با کمی تاخیر مبارک! عید غدیر هم پیشاپیش مبارک!

آقا با اینکه تو بخش نظرات پست قبلی کلی بحث شد و من خودم شخصا اعمال نفوذ کردم ولی بازم طرفداران سوال های مرحله دو (طی یک نقشه حساب شده)، نظرسنجی رو به نفع خودشون تموم کردند! به هرحال چون اینجا دموکراسی کامله! ما هم به رای اکثریت احترام می ذاریم و تو این پست جندتا سوال می ذارم. (البته قرار بود حسام سوال بذاره اما به خاطر مشکلاتی نشد).

اما قبل از اینکه سوال ها رو بذارم چندتا نکته می گم:

- من خودم به نظرم الان سوال تئوری نمی‌ذاشتیم بهتر بود. چندتا دلیل هم دارم. اول اینکه به خاطر تغییرات المپیاد کامپیوتر سبک سوالات معلوم نیست چی جوری باشه. دوم اینکه سوال هایی که ما می ذاریم اکثرا از همون منابعیه که در دسترس همه هست (مثل کتاب های شوروی و وست و استراتژی و ..)، به جز اونایی که تو دوره دیدیم و ممکنه برای شما جدید باشه(این سوال هایی هم که در ادامه می‌نویسم ماله دوره تابستونیه خودمونه). سوم اینکه من تو آرشیو وبلاگ یه نگاه کردم دیدم کلی سوال تئوری وجود داره که می تونید از اون ها هم استفاده کنید. خب همین چندتا دلیل بسه دیگه!(D:).

- با این اوصاف چون ملت خواستند سوال بذاریم من ۴تا سوال می ذارم. این سوال هایی که خواهم نوشت مال امتحان های تئوری تابستون پارسال هستند که طراحاشون آقای زادی مقدم و آقای مهینی بودن.

- من پیشنهاد می کنم تا چند روز کسی در مورد جواب سوال ها تو بخش نظرات چیزی ننویسه، بعدش رو جواب ها بحث می کنیم. البته در مورد خود سوال ها یا چیزای دیگه اگه خواستید می تونید نظر بدید.

اینم سوال ها:

۱-افراز متوازن:

تعدادی عدد طبیعی که هر یک توانی از دو هستند به ما داده اند. می دانیم که از هر توان دو حداکثر دوتا به ما داده شده است. مثلا ممکن است به ما اعداد ۱و۱و۲و۴و۸و۳۲و۳۲ را بدهند. ثابت کنید تعداد روش‌های افراز این اعداد به دو دسته برابر یا صفر یا توانی از دو است. مثلا اعداد بالا را تنها به شکل (۸و۳۲) و (۱و۱و۲و۴و۳۲) می‌توان به دو دسته برابر افراز کرد.

۲-سپید و سیاه:

خانه های یک جدول m*n را با رنگهای سفید و سیاه رنگ کرده‌اند. ما در هر مرحله می‌توانیم یک زیر مستطیل این جدول را به شرطی که (این زیر مستطیل) شامل لااقل دو خانه سیاه باشد، انتخاب کرده و رنگ کل خانه های این زیرمستطیل را عوض کنیم. ثابت کنید که اگر m و n هر دو از ۲ بیشتر باشند، با تعدادی از این حرکات می توان به جدولی برسیم که حداکثر یک خانه سیاه دارد.

۳-گراف یابی:

ففلی یک گراف ساده n-راسی روی کاغذ کشیده است و به مملی نشانش نمی دهد. مملی در هر لحظه دو راس را انتخاب می کند و ففلی فاصله آن ها را به مملی می گوید. کمترین تعداد سوال که مملی باید بپرسد تا از شکل گراف آگاه شود بر حسب n چند است؟

۴- ماتریس کم تنوع:

یک ماتریس n*n که با اعداد ۱ تا n*n پرشده است داریم. رتبه یک درایه در این ماتریس برابر تعداد اعداد بزرگتر از درایه در کل سطر و ستونش می باشد. بنابراین رتبه هر درایه عددی بین ۰ تا 2-2n است. تعداد رتبه های مختلف که در این ماتریس مشاهده می شود برابر تنوع آن است. کترین تنوع در بین همه‌ی ماتریس‌های n*n با درایه های متفاوت را (T(N بنامید. ثابت کنید:

T(ab)

موفق باشید.

خداحافظ!