۱۳۹۱ سکو در یک ردیف قرار دارند و یک خرگوش نامرئی روی یکی از سکوها نشسته است. میخواهیم این خرگوش را شکار کنیم. در هر مرحله میتوانیم به یکی از این سکوها شلیک کنیم. اگر خرگوش روی سکویی که به آن شلیک شده نشسته باشد، شکار میشود؛ در غیر این صورت به علت ترس از صدای تیراندازی، روی یکی از دو سکوی مجاورش (در صورت وجود) میپرد. روشی برای تیراندازیها ارائه دهید که مطمئن باشیم بعد از حداکثر ۱۰۰۰۰ شلیک، خرگوش حتما شکار میشود.
پاسخ
سکوها را از چپ به راست به ترتیب با اعداد $1$ تا $1391$ شماره گذاری میکنیم.
نکته: با هر بار شلیک ما زوجیت سکوای که خرگوش در آن است تغییر میکند.
حال الگوریتم زیر را اجرا میکنیم:
در بخش اول به ترتیب به سکوهای $1$ تا $1391$ شلیک میکنیم. سپس در بخش دوم دوباره به ترتیب به سکوهای $1$ تا $1391$ شلیک میکنیم.
اثبات کارآمدی الگوریتم: روی سکو اولیهای خرگوش حالت بندی میکنیم.
در آخر تعداد حرکات ما $ 2 \times 1391 = 2782 $ و کمتر $10000$ خواهد بود.