المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۱:سوال ۲۱

سوال ۲۱

یک جدول ‎$12 \times 12$‎ داریم که در گوشه‌ی بالای سمت راست و پایینِ سمت چپ آن حرف ‎$O$‎ قرار دارد و گوشه‌ی بالای سمت چپ و همچنین پایینِ سمت راست آن با حرف ‎$X$‎ پر شده است. در قدم اول در خانه‌های مجاورِ خانه‌های شامل ‎$O$‎ ، حرف ‎$O$‎ قرار می‌دهیم و در قدم بعد در خانه‌های مجاور خانه‌های شامل ‎$X$‎، حرف ‎$X$‎ را می‌نویسیم (اگر این خانه قبلاً با حرف دیگری پر شده بود، حرف قبلی را پاک و حرف جدید را جایگزین می‌کنیم). این کار را متناوباً تکرار می‌کنیم. اگر در هر قدم تعداد ‎$O$‎ها در جدول را با ‎$K$‎ نشان دهیم، حداکثر ‎$K$‎ چقدر است؟ (دو خانه را که یک ضلع مشترک دارند مجاور می‌نامیم‎(.‎

  1. ۶۵
  2. ۷۲
  3. ۹۴
  4. ۱۱۲
  5. ۱۲۴

پاسخ

گزینه (۳) درست است.

خانه‌های هاشورخورده نشانگر $O$ و سایر خانه‌ها نشانگر $X$ می‌باشند. پس از مراحلی وضعیت جدول به شکل مقابل می‌باشد که ۹۴ خانه از آن $O$ می‌باشد و تا آن مرحله هرگز تعداد $O$ ها به بیش از ۹۴ نمی‌رسد. پس از این مرحله یک در میان وضعیت وضعیت جدول به همین شکل می‌شود. پس هرگز تعداد $O$ ها بیش از ۹۴ نخواهد رسید.


ابزار صفحه