سوال ۴
در مغازه‌ی آقا جلال، کاشی‌هایی به شکل 
فروخته می‌شود. یک جدول $8 \times8$ داریم. می‌خواهیم تعدادی کاشی بخریم و آن‌ها را طوری در جدول قرار دهیم که کاشی‌کاری معتبر باشد. یک کاشی‌کاری معتبر است اگر همهی شرایط زیر را داشته باشد:
- هیچ دو کاشی‌ای هم‌پوشانی نداشته باشند.
- خانه‌های پایین-چپ و بالا-راست جدول حتماً کاشی‌کاری شده باشند.
- تنها با حرکت روی خانه‌های کاشی‌کاری شده‌ی جدول، بتوان از خانه‌ی پایین-چپ جدول شروع کرد، در هر مرحله به یک خانه‌ی مجاور ضلعی رفت، و در انتها به خانه‌ی بالا-راست جدول رسید.
با توجه به قیمت بالای کاشی‌های مغازه‌ی آقا جلال، می‌خواهیم تعداد کاشی‌هایی که می‌خریم کمینه باشد. به چند طریق می‌توان جدول را به صورت معتبر و با کم‌ترین تعداد کاشی ممکن کاشی‌کاری کرد؟ لازم به ذکر است که دو کاشی‌کاری متفاوتند اگر و تنها اگر یک خانه از جدول وجود داشته باشد که فقط در یکی از این دو حالت کاشی‌کاری شده باشد. در شکل زیر، یک نمونه کاشی‌کاری معتبر نمایش داده شده است. توجه کنید که تعداد کاشی‌ها در این نمونه لزوماً کمینه نیست.
- ۲۲۴
- ۲۵۶
- ۱۲۸
- ۹۶
- ۱۹۲
راهنمایی
بدون در نظر گرفتن کاشی‌ها، اگر از هر خانه بتوانیم به خانه‌های مجاور ضلعی آن خانه برویم، کوتاه‌ترین مسیر شامل چند خانه خواهد بود؟ بنابراین حداقل تعداد کاشی‌های لازم چند تاست؟
راهنمایی
با توجه به کمینه بودن تعداد کاشی‌ها، در هر مربع $2 \times 2$ در جدول داده شده حداکثر چند خانه پوشیده می‌شود؟
راهنمایی
نشان دهید هر کاشی در یک مسیر بهینه، دقیقا معادل با یک مربع $2 \times 2$ مستقل در جدول است.
راهنمایی
با توجه به بهینه بودن مسیر، آیا همهی دوران‌های کاشی داده شده مورد استفاده قرار می‌گیرد؟
راهنمایی
سعی کنید کاشی‌ها را با مربع‌های $2 \times 2$ مستقل جایگزین کنید و مسئله را برای مربع‌ها حل کنید. سپس برای حل مسئله‌ی اصلی از آن استفاده کنید.
راهنمایی
برای حل مسئله‌ی مربع‌های $2 \times 2$، با در نظر داشتن کمینه بودن مسیر، هر مربع نسبت به مربع قبل از آن در مسیر در چه وضعیتی قرار می‌گیرد؟ با توجه به تعداد حرکت‌های بالا و راست مورد نیاز، هر یک از این وضعیت‌ها، چند بار می‌تواند در مسیر ظاهر شود؟ برای مثال دو مربع متوالی از مسیر می‌توانند در وضعیت زیر نسبت به هم قرار بگیرند:
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
