المپدیا

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

ابزار کاربر

ابزار سایت


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

معین حریص (۲۰ نمره)

پس از حل مشکل تولد (در مسئله‌ی قبل)، مصطفی برای این که جشن تولد جذابی داشته باشد، یک بازی بین خود، امیر و معین برگزار می‌کند. پیش از شروع تولد، مصطفی $17^{3}$ عدد شکلات خریداری کرده و آن را درون یک مکعب $17 \times 17 \times 17 $ چیده است (در هر خانه دقیقا یک شکلات). شکلات واقع در سطر $x$ ستون $y$ و ار تفاع $z$ را با $(x,y,z)$ نشان می‌دهيم. بازی به این صورت است که در آغاز کار امیر شکلات $(1, 1, 1)$ را خورده و بازی شروع می‌شود. سپس مصطفی، معین و امیر به نوبت بازی می‌کنند.

مصطفی در نوبت خود می‌تواند شکلات سمت راست يا سمت چپی آخرین شکلات خورده شده را بخورد؛ یعنی اگر $(z,y,x)$ آخرین شکلات خورده شده باشد، می‌تواند $(x+1,y,z)$ یا $(x-1,y,z)$ را بخورد.

معین می‌تواند شکلات جلو يا عقبی آخرین شکلات خورده شده را بخورد؛ یعنی اگر $(z,y,x)$ آخرین شکلات خورده شده باشد، می‌تواند $(x,y+1,z)$ یا $(x,y-1,z)$ را بخورد.

امیر می‌تواند شکلات بالا یا پایینی آخرین شکلات خورده شده را بخورد؛ یعنی اگر $(z,y,x)$ آخرین شکلات خورده شده باشد، می‌تواند $(x,y,z+1)$ یا $(x,y,z-1)$ را بخورد.

اگر کسی نتواند در نوبت خود شکلاتی بخورد. می‌بازد و بازی تمام می‌شود.

الف) مصطفی برای این که دوست دارد تحت هر شرایطی امیر ببازد، با معین تبانی می کند و این دو سعی می کنند به نحوی بازی کنند که امیر ببازد. آیا این دو نفر می‌توانند طوری بازی کنند که امیر هر طور بازی کند بازنده باشد؟

ب) امیر که از این موضوع خبر دار می شود، معین را راضی می‌کند که با او همکاری کند. آیا این دو می‌توانند طوری بازی کنند که مصطفی هر طور بازی کند، بازنده باشد؟

پاسخ

قسمت الف)

بله. مصطفی و معین می‌توانند طوری بازی کنند که امیر هر طوری بازی کند، بازنده شود. استراتژی آن دو به شرح زیر است:

این دو همیشه وارد خانه‌هایی می‌شوند که هم $x$ و هم $y$ آن‌ها کمتر مساوی ۲ می‌باشد و هیچ‌گاه وارد خانه‌ای نمی‌شوند که در آن $x = 1$ و $y = 2$ باشد. در واقع می‌توانیم فرض کنیم که بازی در یک مکعب $2 \times 2 \times 17$ که یکی از ستون‌های آن حذف شده است، انجام می‌شود. حال هر کدام از سطوح افقی یک ترومینو می‌باشد. مصطفی و معین طوری بازی می‌کنند که همواره وقتی نوبت به امیر می‌رسد، هر سه خانه‌ی ترومینوی فعلی پر شده باشد و همچنین ترومینوهایی که در ارتفاع کمتر قرار دارند نیز کاملا پر شده باشند. بدین ترتیب وقتی نوبت به امیر می‌رسد، او مجبور است که رو به بالا حرکت کند. سپس مصطفی شکلات خانه‌ی وسط ترومینوی فعلی را خورده و پس از آن معین به گوشه‌ی دیگر ترومینوی فعلی می‌رود. واضح است که پس از این دو حرکت تمام شکلات‌های ترومینوی فعلی خورده شده‌اند و خب امیر مجبور است دوباره به سمت بالا حرکت کند.

مشاهده: امیر بدون پایین آمدن، حداکثر ۱۶ بار می‌تواند به سمت بالا حرکت کند.

بنابر این امیر بازنده است چون مصطفی و معین همواره طبق استراتژی بالا می‌توانند حرکت کنند.

قسمت ب)

خیر. مصطفی می‌تواند طوری بازی کند که فارغ از شیوه‌ی بازی دو نفر دیگر، برنده شود. استراتژی او به شکل زیر است:

مصطفی کاری می‌کند که هیچ‌گاه وارد خانه‌ای با $x > 2$ نشویم. یعنی می‌توانیم فرض کنیم که بازی داخل مکعبی $2 \times 17 \times 17$ انجام می‌شود. حال خانه‌های جدول را رنگ می‌کنیم. در رنگ‌آمیزی ما، خانه $(x, y, z)$ سیاه می‌شود اگر و تنها اگر $y + z$ زوج باشد.

مشاهده‌۱: خانه‌ی $(1, y, z)$ سیاه است اگر و تنها اگر خانه‌ی $(2, y, z)$ سیاه باشد.

مشاهده‌۲: همواره وقتی نوبت حرکت مصطفی و معین است، جمع $y + z$ زوج می‌باشد و وقتی نوبت حرکت امیر می‌باشد، جمع $y + z$ فرد می‌باشد (چرا؟).

با توجه به استراتژی اتخاذ شده، حرکت مصطفی همواره یکتا خواهد بود (از $(1, y, z)$ به $(2, y, z)$ و باالعکس). حال بر اساس مشاهده‌۱، خانه‌های سیاهی که با هم در یک وجه اشتراک دارند را یک جفت در نظر می‌گیریم.

لم: ادعا می‌کنیم که همواره مصطفی می‌تواند بر اساس استراتژی فوق حرکت کند.

اثبات: از برهان خلف استفاده می‌کنیم و فرض می‌کنیم مصطفی دیگر نتواند استراتژی خود را پیاده کند. فرض کنیم خانه‌ی فعلی که در آن هستیم A باشد و جفت خانه‌ی فعلی ما B باشد. می‌‌دانیم که B پیش‌تر دیده شده است وگرنه می‌توانستیم حرکت انجام دهیم. طبق مشاهده‌۲ خانه‌ي B یا توسط خود مصطفی دیده شده است و یا توسط معین. اگر B قبلا توسط مصطفی دیده شده باشد، پس خانه A نیز باید توسط امیر دیده شده باشد. اگر B قبلا توسط معین دیده شده باشد نیز پس از آن مصطفی خانه‌ی A را دیده است. پس به تناقض رسیدیم و بنابراین حکم لم ثابت شد.

حال که مصطفی همواره می‌تواند حرکت انجام دهد، پس بازنده یا امیر است و یا معین.


ابزار صفحه