هرمز (۲۰ نمره)
روباهی نامرئی داخل یکی از خانههای یک جدول $1 \times 1405$ قرار دارد. هرمز میخواهد روباه را شکار کند، ولی از موقعیت آن آگاه نیست.
در هر مرحله، هرمز به یکی از خانههای جدول شلیک میکند. اگر روباه در آن خانه باشد، شکار میشود. در غیر این صورت، روباه به خانهی مجاوری فرار میکند که فاصلهاش را از خانهای که در این مرحله به آن شلیک شده بیشتر میکند. اگر روباه داخل یکی از خانههای ابتدا یا انتهای جدول باشد، در جای خود ثابت میماند.
هرمز حداقل چند شلیک لازم دارد تا همواره بتواند روباه را شکار کند؟
پاسخ
فرض کنید در هر یک از $1405$ خانهی جدول یک روباه قرار دارد و هر کدام با شلیک هرمز مشابه آنچه در سوال گفته شده فرار میکنند. اطمینان هرمز از شکار شدن روباه نامرئی در سوال معادل این است که تمام این $1405$ روباه شکار شوند. کمترین تعداد شلیک برای این که تمام این روباهها شکار شوند $470$ است.
خانهها و روباههای ساکن هر یک را به ترتیب از چپ به راست از $1$ تا $1405$ نامگذاری میکنیم. هرمز برای این که تمام روباهها را در $470$ حرکت شکار کند، ابتدا به خانهی $936$ شلیک میکند. بعد از آن به خانهی $934$ شلیک میکند و روباه $935$ در آن شکار میشود. با ادامهی همین روند، به خانههای زوج به ترتیب نزولی (یعنی $932, 930, \ldots, 2$) شلیک میکند. بعد از این $468$ شلیک، تمام روباههای $469$ تا $936$ شکار شدهاند. تا این مرحله، روباههای $1$ تا $468$ در هر شلیک یک خانه به سمت چپ فرار کردهاند یا در صورتی که در خانهی $1$ بودهاند همان جا ماندهاند؛ پس اکنون همه در خانهی $1$ هستند. در گام بعد، هرمز به خانهی $1$ شلیک میکند و تمام این روباهها شکار میشوند. بعد از این حرکت، به طریق مشابه روباههای $937$ تا $1405$ همگی در خانهی $1405$ قرار دارند و هرمز با یک شلیک به آن خانه تمام آنها را شکار میکند. بدین ترتیب با $470$ حرکت تمام روباهها شکار شدهاند.
حالا اثبات میکنیم این تعداد شلیک برای شکار تمام روباهها لازم است. در هر زمان یک خانه از جدول را امن مینامیم اگر روباهی در آن نباشد. ادعا میکنیم با هر شلیک، تعداد خانههای امن حداکثر سه تا افزایش مییابد.
خانهی $x$ در سمت چپ شلیک که $x > 1$ و قبل از شلیک ناامن بوده را در نظر بگیرید. بعد از شلیک، روباههایی که در آن بودند به خانهی سمت چپ آن فرار میکنند و $x - 1$ قطعا ناامن خواهد بود. بدین صورت تناظر یک به یکی میان خانههای ناامن قبل و بعد شلیک ایجاد میشود و در سمت چپ خانهای که به آن شلیک شده، حداکثر یک خانهی ناامن کم میشود. به طریق مشابه در سمت راست شلیک هم همین اتقاق رخ میدهد. خود خانهای که به آن شلیک شده هم امن میشود که میتواند خانههای امن را یکی بیشتر کند.
هرمز حتما باید به هر دو خانهی ابتدا و انتهای جدول شلیک کند زیرا روباههای آنها هرگز حرکت نمیکنند. طبق آنجه دربارهی افزایش تعداد خانههای امن گفته شد، شلیک به آنها حداکثر دو تا به تعداد خانههای امن میافزاید. همچنین اگر قبل از شلیک آخر بیش از یک خانهی ناامن باقی مانده باشد، هرمز نخواهد توانست همهی خانهها را امن کند. بنابراین شلیک آخر حداکثر یک خانهی امن اضافه میکند، شلیک دیگری وجود دارد که به ابتدا یا انتهای جدول است و حداکثر دو خانهی امن اضافه میکند، و سایر شلیکها هم حداکثر سه خانهی امن اضافه میکنند. با این حساب، حداقل شلیک ها برای رسیدن از $0$ به $1405$ خانهی امن، $\lceil\frac{1405}{3}\rceil + 1 = 470$ تاست.