سرزمین ‎«میبلز» یک جدول نامتناهی در نامتناهی است که در ابتدا ‎$n$‎ مار گرسنه در ‎$n$‎ تا از خانه‌های آن، به صورت تصادفی، طوری قرار گرفته‌اند که فاصله‌ی هر دوتای آن‌ها متناهی است.

می‌دانیم هر مار در طی هر روز (منظور از روز، از صبح علی‌الطّلوع تا عصر و منظور از شبانه‌روز، یک روز به‌علاوه‌ی شبِ آن است) در یکی از خانه‌های جدول قرار دارد و بسته به شرایط محیط، هر شب به یکی از خانه‌های مجاور‎)‎مجاور ضلعی، حداکثر ‎۴‎‎ خانه) نقل مکان می‌کند. شدّت گرسنگی در مارها به حدّی است که هر مار با دیدن یک سیب در یکی از خانه‌های جدول، تمام تلاش خود را(مستقل از سایر مارها) به‌کار می‌برد تا به خانه‌ای که در آن سیب قرار دارد، برسد‎!‎ از آن‌جا که مارها قادر به دیدن تمامی خانه‌های جدول هستند، می‌توان نتیجه گرفت که وجود یک سیب در یکی از خانه‌های جدول باعث می‌شود هیچ ماری ثابت نمانده و همواره هر ماری تلاش کند به سیب نزدیک شود. امّا پس از خورده شدن سیب توسّط یکی از مارها (در صورت وجود)، تا قرار گرفتن سیب بعدی در خانه‌ای از جدول همه‌ی مارها بی‌انگیزه سر جای خود می‌مانند‎!‎ می‌دانیم اگر در ابتدای یک روز، دو مار هم‌زمان در یک خانه‌ی جدول قرار بگیرند، هر دوی آن‌ها (به دلیل رقابت شدید و جای تنگ‎(!‎ نابود می‌شوند؛ و البته اگر سیبی در آن خانه قرار داشته باشد، آن سیب نیز خورده می‌شود.

شاهزاده‌ی سرزمین میبلز به تازگی یک بال‌گرد(هلی‌کوپتر) خریده است که با استفاده از آن قادر است در ابتدای هر روزی که هیچ سیبی روی زمین نیست، یک سیب در یکی از خانه‌های جدول قرار بدهد. بدیهی‌ست که با این‌کار ممکن است بعضی از مارها در مسیر حرکت به سمت سیب هم‌زمان وارد یک خانه شده و نابود شوند. البتّه نمی‌توان در خانه‌ای که در آن مار قرار دارد، در همان روز سیب قرار دارد چرا که ممکن است مارِ آن خانه به هلی‌کوپتر حمله کند‎!‎

از شما خواسته شده تا با توجّه به شرایط خاص هر قسمت، با ارائه‌ی یک روش مناسب (که برای تمام نحوه‌های قرارگیری مارها در ابتدای کار درست کار کند) به شاهزاده کمک کنید تا با هدر دادن کم‌ترین تعداد سیب، بتواند تمام مارهای آن قسمت را در زمان متناهی نابود کند. دقّت کنید که اگر در پایان کار (هنگامی‌که تمامی مارها نابود شدند) سیبی دست‌نخورده روی جدول مانده باشد، می‌توانیم آن سیب را برداریم و بداهتاً هزینه‌ی مصرف شده برای آن را نیز پس بگیریم. به بیان دیگر، هزینه‌ی یک روش، تعداد سیب‌هایی است که توسّط مارها خورده می‌شود و نه تعداد سیب‌هایی که روی جدول قرار داده می‌شود (به اضافه‌ی هزینه‌ی حفر چاه‌ها در قسمت ب).

‎الف) در این قسمت، نحوه‌ی حرکت هر مار بدین صورت است که با دیدن یک سیب، در ابتدای هر شب، اگر در ستونی که سیب در آن قرار دارد نباشد، سعی می‌کند در همان سطری که هست، یک واحد به سمت چپ یا راست برود تا به ستونِ سیب برسد. امّا اگر در ستونِ سیب قرار داشت، مستقیماً به سمت سیب حرکت می‌کند. بدیهی‌ست که در این رویه، مسیر حرکت هر یک از مارها به صورت یک‌تا تعیین می‌شود.

هم‌چنین می‌دانیم در یکی از خانه‌های جدول (به صورت تصادفی؛ ما آن را تعیین نمی‌کنیم) یک چاه قرار دارد که هر ماری به محض ورود به آن، نابود می‌شود‎!‎ می‌دانیم در ابتدا هیچ ماری در خانه‌ی چاه نیست و از طرف دیگر، ما هم هرگز اجازه نداریم در خانه‌ی چاه، سیب قرار بدهیم.

با این شروط، کم‌ترین هزینه‌ی لازم برای نابود کردن تمامی مارها (چه از طریق برخورد، چه از طریق افتادن در چاه) چه‌قدر است؟ روش نابود کردن مارها با این تعداد را توضیح داده و اثبات کنید که این مقدار سیب در حالت کلّی کمینه است. مجدّداً دقّت کنید که در این قسمت (و قسمت بعد) اگر در پایان کار سیبی روی جدول باقی بماند، هزینه‌ی ‎(سیب‌هایِ)‎ روش برابر است با تعداد سیب‌های استفاده شده منهای یک (برای سیبی که در پایان سالم باقی می‌ماند).

‎ب) در این قسمت نحوه‌ی حرکت مارها اندکی پیچیده‌تر است‎!‎ اگر مار در ستون یا سطرِ سیب قرار داشته باشد، مشابه قسمت قبل، در همان امتداد به سمت سیب حرکت می‌کند. امّا اگر در سطر و ستونی غیر از سطر و ستون سیب قرار داشته باشد، در هر حرکت صرفاً یک واحد به سیب نزدیک(فاصله‌‎ی دو خانه، حداقل تعداد شبانه‌روز لازم برای رسیدن از یکی به دیگری توسّط یک مار است؛ برای مثال دو خانه‌ی مجاور ضلعی فاصله‌شان برابر یک و دو خانه‌ی مجاور رأسی که فقط در یک رأس مشترک باشند، فاصله‌شان دو واحد است‎(.‎ می‌شود. برای مثال اگر سیبی در خانه‌ی بالاچپِ یک مار قرار داشته باشد، آن مار در حرکت اوّل ممکن است به سمت بالا و یا به سمت چپ حرکت(دقّت کنید که حرکت هر مار در این قسمت کاملاً تصادفی است امّا شما باید در روش‌تان فرض کنید که هر مار به‌ترین حرکت برای خودش (که بدترین حرکت برای شما در راستای نابود کردن مارها است) را انجام می‌دهد. به عبارت دیگر، به‌تر است فرض کنید مارها به‌صورت هوشمندانه (و البتّه در چارچوب قوانین) در تلاش برای حفظ بقا هستند‎.‎) کند؛ حال آن‌که حرکت دوم‌ش (چون با سیب، هم‌سطر یا هم‌ستون می‌شود) یک‌تاست.

از سوی دیگر، در این قسمت، ما می‌توانیم همان‌گونه که در یک خانه‌ی خالی سیب می‌گذاریم، یک خانه‌ی خالی را نیز تبدیل به چاه کنیم‎!‎ بالطّبع می‌توان چاه‌ها را در وسط کار نیز احداث کرد، امّا به‌دلیل عدم امکان کنترل هیجان مارها، این کار فقط زمانی امکان‌پذیر است که هیچ سیبی روی زمان نباشد. بعداً اضافه شد:هم‌چنین به‌دلیل امکان ریزش زمین، دو چاه نمی‌توانند مجاور را‎ٔسی(حداکثر ‎۸‎‎ خانه) باشند. زمان حفر یک چاه ناچیز فرض می‌شود امّا هزینه‌ی حفر هر چاه، مساوی هزینه‌ی خورده‌شدن یک سیب و برابر ‎۱‎ سکّه‌ی طلا می‌باشد. بدیهی‌ست که حفر چاه در خانه‌ای که در آن مار یا سیب قرار دارد امکان پذیر نبوده و نیز امکان قرار دادن سیب در خانه‌ی چاه مقدور نیست.

با این تفاسیر، روشی ارائه دهید که بتوانیم با صرف حداکثر ‎$n$‎ سکّه‌ی طلا، تمامی مارها را نابود کنیم.

• سوال بعد