ضدعفونی زمین (۲۰ نمره)
زاریچ که زندگی خود را وقف شکست ویروس کرونا کرده است، یک ربات برای ضدعفونی کردن زمین اتاق ساخته است. زمین اتاقی که ربات در آن قرار دارد از بالا به صورت جدولی مربع‌شکل دیده می‌شود. ربات در ابتدا روی خانه‌ی گوشه‌ی پایین-چپ جدول قرار دارد. در برخی خانه‌های جدول وسایل قرار دارد و آن خانه‌ها مسدود است. ربات ابتدا رو به بالای جدول قرار دارد و همواره به‌صورت زیر حرکت می‌کند:
- اگر ربات مقابل دیوار قرار نداشت و خانه‌ی مقابل ربات مسدود نبود، ربات یک خانه به جلو حرکت می‌کند.
- در غیر این صورت، ربات ۹۰ درجه در جهت ساعت‌گرد می‌چرخد.
این ربات در حین حرکت، روی هر خانه‌ای از جدول که برود، آن را ضدعفونی می‌کند. هدف زاریچ آن است که همه‌ی خانه‌های قطر اصلی جدول حداقل یک بار توسط ربات پیموده و ضدعفونی شوند. قطر اصلی مجموعه‌ای از خانه‌های جدول است که از خانه‌ی بالا-چپ جدول شروع می‌شود و تا خانه‌ی پایین-راست جدول ادامه می‌یابد. امکان دست‌یابی به هدف زاریچ به این بستگی دارد که چه خانه‌هایی از جدول مسدود باشند. اگر در یک جدول، ربات (با شروع از خانه‌ی پایین-چپ و جهت اولیه‌ی رو به بالا، و حرکت طبق قواعد گفته شده) همه‌ی خانه‌های قطر اصلی را حداقل یک بار ضدعفونی کند، آن جدول را مطلوب می‌نامیم. بالطبع، هیچ یک از خانه‌های قطر اصلی و یا خانه‌ی شروع ربات در یک جدول مطلوب مسدود نیست. مثلا در شکل زیر، یک نمونه از جدول $5\times 5$ را می‌بینیم که مطلوب نیست. در این جدول، خانه‌های قطر اصلی با دایره، خانه‌های مسدود با رنگ سیاه، و خانه‌های ضدعفونی‌شده با رنگ خاکستری مشخص شده‌اند. همان‌طور که مشخص است، در این جدول ربات تنها ۲ خانه از ۵ خانه‌ی قطر اصلی را ضدعفونی می‌کند.
الف) یک نمونه جدول مطلوب $5\times 5$ بکشید. (۵ نمره)
ب) آیا جدول مطلوب ۱۳۹۹×۱۳۹۹ داریم؟ در صورت وجود، آن را توصیف کنید، و در غیر این صورت، ثابت کنید که وجود ندارد. (۱۵ نمره)
پاسخ