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