سوال.

به نام خدا

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

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

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

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

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

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

اینم سوال ها:

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

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

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

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

۳-گراف یابی:

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

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

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

T(ab)

موفق باشید.

خداحافظ!