الف) مستطیل را به مربع های $3\times 3 $ تقسیم می‌کنیم و خانه ی وسط هر مربع را رنگ میزنیم. خانه ی وسط، تمام 9 خانه ی مجاور راسی مربع خود و خانه ی خودش را ارضا می‌کند.(هم طول هم عرض مضرب ۳ هستند.)

هزینه: $ \frac{1401 \times 300}{9} \times (2+1)$ که در آن هر مربع دقیقا یک خانه ی وسط دارد و برای رنگ زدن هر خانه ی وسط مربع ها ۲ تا برای نقاش و یکی هم برای خود آن خانه رنگ میزنیم

ب)

در هر مرحله از نقشه چیدن برای نقاشی و قبل از آوردن نقاش ها یکی از اینکارهارا در ذهنمان میکنیم:

۱. یک زیرمستطیل $n\times m $را میخواهیم یک ردیف بیشتر کنیم یعنی آن را به $(n+1)\times m $تبدیل کنیم. میتوان دید که برای اینکار حداکثر $m+2$ خانه ی مجاور راسی که توسط زیرمستطیل قبلی ارضا نشده بود، ارضا میشود. برای اینکار هم m هزینه میکنیم.

۲. نمیخواهیم زیرمستطیلی را بزرگتر کنیم (یک زیرمستطیل جدید بسازیم در نتیجه برای اینکار نیاز به نقاش داریم):

اضافه کردن هر خانه حداکثر ۸ خانه سفید را ارضا میکند و اگر خود خانه ی رنگ شده هم در نظر بگیریم ۹ تا. هزینه ی اینکار ۲ تا برای آوردن نقاش و ۱ هم برای خود خانه است. پس هزینه ی اینکار برابر ۳ است.

در تمامی حالات بالا حداکثر خانه ای که ارضا میکنیم تقسیم بر هزینه ای که میدهیم بزرگتر مساوی ۳ است. پس حداقل باید به تعداد خانه ها تقسیم بر۳ هزینه کنیم

برای قسمت ب

به یک خانه می‌گوییم ارضا شده اگر سیاه باشد و یا یک مجاور رأسی سیاه داشته باشد

میشه دید که در هر روز تعداد خانه‌هایی که ارضا می‌شوند حداکثر ۳ برابر هزینه‌ای است که میکنیم.

باید اثبات کنیم:

$$ 3(nm+2)\geq (n+2)(m+2) $$ $$ 3nm+6\geq nm+2n+2m+4 $$ $$ 2nm-2n-2m+2\geq 0 $$ $$ nm-n-m+1\geq0 $$ $$ (n-1)(m-1)\geq0 $$

و این نامساوی برای $n\geq1$ و $m\geq1$ برقراره.

هم‌چنین می‌تونید مشاهده کنید که همون طور که برای قسمت الف به دست آوردیم حالت بهینه اینه که همیشه یکی از $n$ یا $m$ مساوی $1$ باشند.

پس در مجموع تعداد خانه‌های ارضا شده (کل خانه‌های جدول) کوچک‌تر مساوی سه برابر هزینه‌ای که کردیم است. پس باید حداقل ۱۴۰۱۰۰ سکه هزینه کنیم