المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۷

خانه‌های یک جدول ‎$m\times n$‎ به رنگ‌های سیاه و سفید رنگ شده‌اند و در یکی از خانه‌ها، یک مهره قرار دارد. در هر حرکت می‌توانیم مهره را یک خانه به بالا، پایین، چپ یا راست حرکت دهیم، با این شرط که مهره به هر خانه‌ای که وارد شود، رنگ آن خانه را عوض می‌کند (از سفید به سیاه و بالعکس). به ازای کدام‌یک از گزینه‌های زیر، می‌توان به گونه‌ای خانه‌ها را رنگ کرد و مکان اولیه مهره را مشخص نمود که با انجام تعدادی حرکت نتوان تمامی خانه‌ها را هم‌رنگ کرد؟

  1. $n=m=4$
  2. $n=3$‎ و ‎$m=16$
  3. $n=5$‎ و $m=7$
  4. برای $n$‎ و ‎$m$ بزرگ‌تر از ۲ این نوع رنگ‌آمیزی وجود دارد.
  5. برای $n$‎ و ‎$m$ بزرگ‌تر از ٬۲هم‌رنگ کردن خانه‌ها همواره عملی است‎.

پاسخ

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

اگر بخواهیم رنگ خانه‌ای عوض شود از خانه‌ی مجاور آن به آن وارد شده و از آن خارج می‌شویم و اگر خانه‌ای خانه‌ی گذر باشد و نخواهیم رنگ آن عوض شود به آن وارد شده و پس از خروج از آن دوباره به آن خانه برگشته و خروج از آن را تکرار می‌کنیم.


ابزار صفحه