سوال ۴
یک شش وجهی صورتی $1 \times 1 \times 2$ داریم که در یکی از گوشههای جدول ۴ × ۴ مانند شکل زیر قرار دارد. در هر گام میتوان آن را روی یکی از وجههایش غلتاند (به شرطی که از جدول بیرون نزند) و تمام خانههای زیر آن را به رنگ صورتی درآورد (یک خانه میتواند چندین بار رنگآمیزی شود). در ابتدا تمام خانههای جدول به جز خانهی زیرین شش وجهی سفید هستند. حداقل چند گام لازم داریم تا کل جدول را به رنگ صورتی درآوریم؟
- ۱۱
- ۱۰
- ۱۲
- ۹
- ۸
پاسخ
گزینهی ۴ درست است.
ابتدا یک مثال با ۹ حرکت ارائه میدهیم:
- دو حرکت به سمت راست
- دو حرکت به سمت پایین
- دو حرکت به سمت چپ
- یک حرکت به سمت بالا
- دو حرکت به سمت راست
واضح است که برای رنگ کردن ۱۵ خانه حداقل به ۸ حرکت نیاز داریم. همچنین اگر بخواهیم با دقیقاً ۸ حرکت جدول را رنگ کنیم، در حداکثر ۱ مرحله سطح ۱ × ۱ شش وجهی میتواند روی زمین قرار بگیرد. زیرا در غیر اینصورت حداکثر تعداد خانههای رنگ شده برابر با $6 \times 2 + 2 = 14$ میشود. همچنین بدون استفاده از سطح ۱ × ۱ نمیتوان کل جدول را طی کرد و در طی تمام مراحل نمیتوانیم خانهی تکراری رنگ کنیم. پس کافی است روی اینکه این سطح را در کدام حرکت استفاده کردهایم، حالتبندی کنیم. این حرکت در یکی از مراحل ۲ تا ۵ استفاده شده است که در تمامی این حالات پوشاندن سایر بخشهای جدول امکانپذیر نیست.