آرمیتا و باران مشغول یک بازی روی تختهسیاه هستند. در ابتدا، باران یک عدد طبیعیِ دلخواه را انتخاب میکند و آن را روی تختهسیاه مینویسد. سپس آرمیتا بازی را شروع میکند و بعد از هر یک، نوبت به شخصِ دیگر میرسد. آرمیتا در هر نوبتش میتواند بهمقدارِ a یا 2a از عددِ روی تخته کم کند و عدد حاصل را بهجای آن برروی تخته بنویسد. باران هم در هر حرکت میتواند به مقدارِ b یا 2b از عدد روی تخته کم کند و عدد حاصل را جایگزینِ عدد روی تخته کند. نهایتا، کسی که عددی کمتر از صفر روی تخته بنویسد، بَرندهی بازی است. اگر هر دو نفر بهینه عمل کنند، بهازای چند مورد از حالتهای زیر برای مقدارِ a و b، آرمیتا میتواند همواره طوری بازی کند که برندهی بازی باشد؟ لازم به ذکر است که بهینه عمل کردنِ باران، شامل انتخابِ او در تعیینِ عدد اولیهی نوشتهشده روی تختهسیاه نیز میشود.
(a=10,b=4), (a=20,b=35), (a=30,b=15), (a=40,b=40)
پاسخ
گزینه (3) درست است.
اگر a<2b باشد، باران در حرکت ابتدایی خود 2a را روی تخته مینویسد. با انجام این کار، آرمیتا در حرکت اول نمیتواند برندهی بازی باشد، چرا که عدد نوشته شده را میتواند یا به صفر برساند یا به a. در هر دوی این حالات، با توجه به اینکه a<2b، باران در حرکت بعد عدد را منفی میکند و بازی را میبرد. برعکس، اگر 2b≤a باشد، هر عددی که باران روی تخته بنویسد، باز هم آرمیتا بازی را میبرد. در این حالت، الگوریتم آرمیتا به شکل زیر میتواند باشد تا بازی را ببرد:
- اگر عدد روی تخته از 2a کمتر بود، از آن 2a کم کن و بازی را ببر.
- در غیر این صورت، از عدد روی تخته a واحد کم کن.
در حرکت بعدی از حالت دوم الگوریتم آرمیتا، باران نمیتواند بازی را ببرد، چرا که 2a≤k بنابراین a≤k−a و چون 2b≤a، عدد جدید روی تخته از 2b بیشتر است و باران نمیتواند در این حرکت بازی را ببرد.