المپدیا

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

ابزار کاربر

ابزار سایت


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

بازی

دو نفر این بازی را با تعدادی سنگ‌ریزه انجام می‌دهند: در ابتدا٬ $n$ سنگ‌ریزه موجود است ($1 \lt n$). با توجه به قاعده‌ی زیر٬ دو نفر به ترتیب٬ یک در میان٬ از این سنگ‌ریزه‌ها برمی‌دارند. قاعده‌ی بازی به این صورت است که در اولین حرکت٬ بازی‌کن می‌تواند به هر تعدادی که بخواهد از این سنگ‌ریزه‌ها بردارد؛ ولی باید حداقل یک٬ و حداکثر $n -1$ سنگ‌ریزه بردارد. پس از آن هر بازی‌کن در نوبت خودش٬ می‌تواند حداقل یک٬ و حداکثر به اندازه‌ی تعدادی که بازی‌کن دیگر در حرکت قبل برداشته٬ سنگ‌ریزه بردارد. برای مثال٬ اگر بازی‌کن اول٬ در اولین حرکت‌اش ۲ سنگ‌ریزه بردارد٬ در حرکت بعد٬ بازی‌کن دوم می‌تواند ۱ یا ۲ سنگ‌ریزه بردارد.

برنده‌ی بازی کسی خواهد بود که آخرین سنگ‌ریزه را بردارد.

الف) ثابت کنید اگر $n=6$ باشد٬ نفر اول (کسی که بازی را شروع کرده است) می‌تواند طوری بازی کند که همواره برنده شود؛ یعنی نفر اول می‌تواند به گونه‌ای بازی کند که اگر نفر دوم در هر مرحله بهترین حرکتی که می‌تواند را انجام دهد٬ نفر اول برنده شود.

ب) ثابت کنید که در حالت کلی اگر $n$ توانی از دو باشد٬ نفر دوم می‌تواند طوری بازی کند که همواره برنده شود٬ و در غیر این صورت نفر اول می‌تواند برنده شود.

پاسخ

با استقرا روی $n$ حکم را ثابت می کنیم. حکم برای $n=1$ درست است. اگر $n$ توانی از دو نباشد، نفر اول می تواند مقداری کمتر از نصف $n$ کم کند تا به یک توان دو برسد. و چون مقدار کم شده از مقدار مانده کمتر است، نفر دوم نمی تواند کل را یک جا بردارد و بنابراین می توانیم او را مانند نفر اول فرض کنیم و هر کار که کرد طبق استراتژی نفر دوم که طبق فرض استقرا وجود دارد بازی کنیم و ببریم.

اما اگر $n=2^k$ باشد، اگر نفر اول $2^{k-1}$ یا بیشتر بردارد که ما باقیمانده را برداشته و می بریم. اما در غیر این صورت ما استراتژی بردی که طبق فرض استقرا برای $2^{k-1}$ داشتیم را به کار می گیریم تا نفر اول کسی باشد که تعداد سنگ ها را از $2^{k-1}$ کمتر می کند. مسلما تا وقتی تعداد سنگ ها از $2^{k-1}$ بیشتر است نفر اول نمی تواند طی یک مرحله تعداد سنگ ها را به صفر برساند زیرا با حرکت اول او، تعداد مجاز برای برداشتن از $2^{k-1}$ کمتر شده است. پس روزی می رسد که نفر اول تعداد سنگ ها را از $2^{k-1}$ کمتر می کند. در این مرحله ما می توانیم فرض کنیم که از ابتدا تعداد سنگ ها $2^{k-1}$ بوده و نفر اول طی یک حرکت این وضعیت را به وجود آورده است. ( چون نفر اول بیشتر مساوی حالت مفروض ما سنگ برداشته، تعداد سنگ مجاز برای ما مشکلی ایجاد نمی کند ) حال ما استراتژی $2^{k-1}$ را دنبال می کنیم تا برنده بازی شویم.


ابزار صفحه