المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۵

دو نفر این بازی را انجام می‌دهند: آنها در یک جدول $۱\times n$(یک سطر با $n$ خانه) به نوبت مهره می‌گذارند. هر خانه‌ی جدول گنجایش یک مهره را دارد و در ابتدا جدول خالی است. نفر اول در هر حرکت یک مهره‌ی سفید و نفر دوم در هر حرکت یک مهره‌ی سیاه در یک خانه خالی می‌گذارند. وقتی مهره‌ای — مثل $A$ — در جدول قرار می‌گیرد، اگر مهره‌ای همرنگ $A$ — مثل $B$ — در جدول باشد و تمام خانه‌های بین $A$ و $B$ با مهره‌هایی با رنگی مخالف رنگ $A$ پر شده باشند، تمام مهره‌‌های بین $A$ و $B$٬ همرنگ $A$ می‌شوند. با اضافه کردن $A$ به جدول ممکن است دو مهره مانند $B$ در جدول (در دو طرف $A$) پیدا شوند که شرایط گفته شده را داشته باشند، که در این صورت عمل مذکور را در هر دو مورد انجام می‌دهیم.

بعد از $n$ حرکت، تمام خانه‌های جدول پر می‌شوند و بازی تمام می‌شود. در این زمان اگر تعداد مهره‌های سفید درون جدول بیشتر باشد، نفر اول می‌برد، اگر تعداد مهره‌های سیاه بیشتر باشد، نفر دوم می‌برد، و گرنه مساوی می‌شوند. برای $n$های بزرگ‌تر از ۱۰، کدام جملات زیر درست‌اند؟

۱) برای $n$های فرد نفر اول راهکار برد دارد.

۲) برای $n$های فرد نفر دوم راهکار برد دارد.

۳) برای $n$های زوج نفر اول راهکار برد دارد.

۴) برای $n$های زوج نفر دوم راهکار برد دارد.

۵) برای $n$های زوج نفر اول راهکار نباختن دارد.

۶) برای $n$های زوج نفر دوم راهکار نباختن دارد.

  1. ۱ و ۳ و ۵
  2. ۲ و ۴ و ۶
  3. ۱ و ۴ و ۶
  4. ۲ و ۳ و ۵
  5. ۱ و ۵ و ۶

پاسخ

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

برای $n$های فرد نفر اول راه‌کار برد دارد به این صورت که هر دفعه در نوبت خود سمت راست‌ترین خانه‌ی خالی جدول را پر می کند ثابت می‌کنیم نفر دوم هیچ وقت نمی‌تواند مهره‌های سفید را سیاه کند زیرا هیچ‌وقت یک مهره‌ی سیاه در سمت راست یک مهره‌ی سفید قرار نمی‌گیرد چون همیشه سمت راست‌ترین خانه‌ی خالی را پر می‌کنیم. پس اگر یک مهره‌ی سیاه در سمت راست مهره‌ای که الان قرار می‌دهیم باشد آن مهره هم سفید می‌شود ( زیرا سمت راست مهره‌های سیاه حتما مهره‌ی سفید است) نفر دوم بهترین عملکرد خود را داشته باشد نفر اول حداقل یک مهره بیش‌تر از او می‌گذارد.

برای $n$های زوج هرکدام از بازیکن‌ها راه‌کار نباختن دارد. هر دو به روش مشابه بالا سفید از سمت راست و سیاه از سمت چپ شروع به پر کردن می‌کند در نتیجه هرکدام حداقل به اندازه‌ی $n/2$ از جدول را می‌پوشانند و نفر مقابل نمی‌تواند ببرد. در نتیجه گزینه ه درست است.


ابزار صفحه