ابوموسی (۱۸ نمره)

خانه‌های جدول را به ترتیب از چپ به راست با شماره‌های $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$ می‌رسیم.