المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۳۱

بازی یک‌نفره‌ی «کوئیدیچ» به شکل زیر انجام می‌شود: یک صفحه‌ی $4×4$ که همه‌ی ۱۶ خانه‌ی آن سفید هستند در اختیار داریم. در هر حرکت، یکی خانه را انتخاب می‌کنیم. با انتخاب هر خانه، رنگ آن خانه و همه‌ی خانه‌هایی که در بالا و سمت راست آن هستند عوض می‌شود (از سفید به سیاه یا از سیاه به سفید تغییر می‌یابد). مثلاً در شکل مقابل با انتخاب خانه‌ی دوم از ردیف سوم، رنگ بعضی از خانه‌ها سیاه شده است.

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

  1. ۶
  2. ۷
  3. ۸
  4. ۱۵
  5. ۱۶

پاسخ

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

اگر خانه‌های با مختصات $(1,4),(1,3),(1,2),(4,1),(3,1),(2,1)$ را به ترتیب انتخاب کنید صفحه شطرنجی خواهد شد. لازم به ذکر است که انتخاب هر یک از آن خانه‌ها الزامی است٬ زیرا خانه‌ای مانند $(2,1)$ را فقط انتخاب خودش می‌تواند تغییر دهد.


ابزار صفحه