المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۹

هفت مهره‌ی سیاه و سفید به ترتیب زیر در یک ردیف قرار دارند: مرتضی و ابوالفضل با هم بازی می‌کنند. هر کس در نوبت‌ش یکی از مهره‌های کناری ردیف را برای خود برمی‌دارد. هر دو نفر دوست دارند مهره‌های سیاه بیش‌تری در انتها داشته باشند. ابوالفضل بازی را آغاز می‌کند. پس از هفت مرحله بازی تمام می‌شود و ابوالفضل چهار مهره و مرتضی سه مهره خواهد داشت. اگر هر دو نفر به به‌ترین شکل ممکن بازی کنند، در انتها ابوالفضل چند مهره‌ی سفید خواهد داشت؟

  1. ۱
  2. ۲
  3. ۳
  4. ۰
  5. ۴

راهنمایی

می‌توانید طوری به عنوان ابوالفضل بازی کنید که حداقل یک توپ سیاه بردارید؟

راهنمایی

اگر زوج توپ در ردیف وجود داشته باشند و فردی که نوبتش است، بخواهد تمام توپ‌های با جایگاه فرد را بردارد، آیا می‌تواند؟ جایگاه زوج را چطور؟

راهنمایی

پس از آنکه ابوالفضل توپ اول را برداشت،‌آیا در شرایط راهنمایی پیشین قرار نمی‌گیریم؟

پاسخ

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

ابتدا ثابت می‌کنیم ابوالفضل می‌تواند دست کم یک توپ سیاه در انتها داشته باشد. او توپ سمت چپ را برمی‌دارد. حال مرتضی هر توپی بردارد، یک توپ سیاه قابل برداشتن برای ابوالفضل می‌شود.

حال ثابت می‌کنیم مرتضی می‌تواند دست کم دو توپ سیاه در انتها داشته باشد. پس از برداشتن نخستین توپ توسّط ابوالفضل، مرتضی توپ‌ها را در ذهن خود به طور یک در میان در دو دسته‌ی $A$ و $B$ می‌گذارد. یکی از دو دسته شامل دو توپ سیاه است. بدون از دست دادن کلّیت مسئله فرض کنید $A$ چنین باشد. مرتضی هم‌واره می‌تواند یک توپ از دسته‌ی $A$ بردارد و ابوالفضل مجبور است از دسته‌ی $B$ بردارد. پس در انتها تمام توپ‌های دسته‌ی $A$ برای مرتضی خواهد شد و او دو توپ سیاه خواهد داشت.

با توجه به دو حکم بالا، اگر هر دو نفر بهینه بازی کنند، در انتها دو توپ سیاه در اختیار مرتضی و یک توپ سیاه در اختیار ابوالفضل خواهد بود. پس ابوالفضل سه توپ سفید خواهد داشت.


ابزار صفحه