جواب ها

سلام به همگی.

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

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

اینم جواب ها:

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

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

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

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

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

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

۳- گراف یابی:

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

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

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

موفق باشید.

خداحافظ!