زرنگی

علی می‌خواهد یکی از دیوارهای اتاقش را رنگ‌آمیزی کند. او همچنین می‌خواهد برادر کوچک‌ترش، حامد، را هم سرگرم کند. بنابراین علی بازی «بازه‌رنگی» را طراحی کرده است تا با یک تیر، دو نشان بزند. در ابتدای بازی او دیوار را به تعدادی قسمت مساوی تقسیم می‌کند. سپس در هر مرحله از بازی، یک یا چند قسمت متوالی از دیوار انتخاب می‌شود و حامد آن قسمت‌ها را رنگ‌آمیزی می‌کند. از آن جا که حامد بسیار باهوش است، بازه‌ی انتخاب شده برای رنگ آمیزی در هر مرحله، باید به صورت تصادفی انتخاب شود. در غیر این صورت حامد به نقشه‌ی علی پی می‌برد و دیگر بازی را ادامه نمی‌دهد.

حال علی می‌خواهد شانس خود برای رنگ‌آمیزی کامل دیوار را اندازه گیری کند. او می‌خواهد بداند اگر بازی را تا $k$ مرحله ادامه دهد، در چند حالت از $(\frac{n(n+1)}{2})^k$ حالت از انتخاب بازه‌ها، تمام قسمت‌ها حداقل یک بار رنگ‌آمیزی می‌شوند؟ اگر دیوار به $n$ قسمت تقسیم شده باشد، این عدد را با $f(n, k)$ نشان می‌دهیم. برای مثال مقدار $f(2, 2)$ برابر ٧ است. به علی کمک کنید و به سوالات زیر پاسخ دهید.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 229939$ محاسبه شده‌اند.

$5$- الف ($11$ نمره) : باقی‌مانده‌ی $f(101, 2)^2$ (به توان دو توجه کنید) بر $\Delta$ چند است؟

$5$- ب ($11$ نمره) : باقی‌مانده‌ی $f(19, 19)$ بر $\Delta$ چند است؟

$5$- ج ($11$ نمره) : باقی‌مانده‌ی $f(101, 202)$ بر $\Delta$ چند است؟

• سوال قبل
• سوال بعد