سلطان در نقطه‌ی ۰ از محور اعداد صحیح قرار گرفته است و گرفتار ۹ غول خطرناک با شماره‌های ۱ تا ۹ شده است. غول‌ها دو نوع هستند: دسته‌ی نخست، غول‌های راست‌گرا که دستور می‌دهند سلطان ۲ واحد به راست برود و دسته‌ی دوم غول‌های چپ‌گرا که دستور می‌دهند سلطان ۱ واحد به چپ برود.

کار در ۹ مرحله انجام می‌شود. در مرحله‌ی $i$ ام، غول شماره‌ی $i$، دستور مورد نظر را (بر اساس راست‌گرا یا چپ‌گرا بودنش) به سلطان می‌دهد. سلطان می‌تواند به دستور غول عمل کند یا این که غول را بکشد و جابه‌جا نشود. اگر سلطان یکی از غول‌ها را بکشد، خسته می‌شود و ۲ غول بعدی را نمی‌تواند بکشد. در صورتی که در انتها، سلطان در خانه‌ی ۰ مختصات باشد، آزاد می‌شود و در غیر این صورت، زندانی می‌ماند. سلطان تنها می‌داند که $k$ تا از غول‌ها راست‌گرا هستند و $9-k$ غول دیگر، چپ‌گرا هستند، اما شماره‌ی غول‌ها را نمی‌داند و طبیعتا از ابتدا نمی‌داند که در مرحله‌ی $i$ ام چه غولی دستور خواهد داد. به ازای چند عدد صحیح $k$ با شرط $0\leq k \leq 9$ ، سلطان الگوریتمی دارد که بتواند به طور تضمینی آزاد شود؟

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

• سوال بعد
• سوال قبل