ابوموسی (۱۸ نمره)
تنب کوچک و تنب بزرگ باهم روی یک جدول $1\times 1405$ بازی میکنند. در ابتدای بازی، تمام خانههای جدول خالی هستند.
در هر مرحله، تنب کوچک یک مستطیل $1\times 2$ خالی از جدول را انتخاب میکند و تنب بزرگ یکی از دو خانهی آن را پر میکند. این کار آنقدر ادامه پیدا میکند تا دیگر تنب کوچک نتواند مستطیلی انتخاب کند. تنب کوچک میخواهد در انتها تعداد خانههای پرشده کمینه شود و تنب بزرگ میخواهد تعداد این خانهها بیشینه شود.
اگر هر دو برای رسیدن به هدفشان به بهترین شکل ممکن بازی کنند، در نهایت چه تعداد از خانهها پر خواهد بود؟
پاسخ
خانههای جدول را به ترتیب از چپ به راست با شمارههای $1$ تا $1405$ شمارهگذاری میکنیم و برای هر دو نفر، یک استراتژی برای رسیدن به هدفشان ارائه میدهیم؛
تنب بزرگ برای پر کردن خانهها به ترتیب اولویت زیر را دارد:
- خانههای $3k$ اُم (خانههای شمارهی $3, 6, 9, \ldots$)
- خانههای $3k+1$ اُم (خانههای شمارهی $1, 4, 7, \ldots$)
- خانههای $3k+2$ اُم (خانههای شمارهی $2, 5, 8, \ldots$)
با پیروی از این اولویتدهی، میتوان نشان داد که در نهایت، داخل هر سه خانهی متوالی به فرم $\langle 3k+1, 3k+2, 3k+3 \rangle$، حداقل دو خانه پر خواهند شد و در مجموع حداقل $\lfloor\frac{2 \times 1405}{3}\rfloor = 936$ خانهی پرشده خواهیم داشت.
تنب کوچک نیز برای رنگ کردن جدول، یک روش استقرایی ارائه میدهد که در آن $f(n)$ را برابر حداکثر خانههای پرشده در یک جدول $1\times n$ درنظر میگیریم:
- در ابتدا مستطیل $\langle 2, 3 \rangle$ را انتخاب میکند.
- اگر تنب بزرگ خانهی $3$ را پر کرد، تنب کوچک مستطیل $\langle 1, 2 \rangle$ را انتخاب میکند و طبق فرض استقرا $f(n) = f(n-3) + 2$ خواهد بود.
- اگر تنب بزرگ خانهی $2$ را پر کرد، طبق فرض استقرا $f(n) = f(n-2) + 1$ خواهد بود.
از آنجا که تنب بزرگ هدفش بیشینه کردن خانههای پرشده است، نتیجه میشود که: $$f(n) = \max(f(n-3) + 2, f(n-2) + 1).$$ با حل کردن این معادله، به مقدار $f(1405) = 936$ میرسیم.