جدول زیر را در نظر بگیرید: دو خانه را مجاور گوییم، اگر دارای یک ضلع مشترک باشند. ایلیچ در خانهی $A$ قرار دارد و میخواهد به خانهی $B$ برود. او در هر مرحله میتواند به یک خانهی مجاور برود. حمید میخواهد تعدادی از خانههای جدول را با خاشاک پر کند تا ایلیچ نتواند از آن خانهها برای عبور استفاده کند. حمید باید طوری این کار را انجام دهد که دست کم یک مسیر از $A$ به $B$ برای ایلیچ وجود داشته باشد. حمید دوست دارد تعداد خانههای کوتاهترین مسیر ممکن برای ایلیچ، بیشینه شود. این مقدار بیشینه چیست؟ توجه کنید خود $A$ و $B$ هم جزء مسیر حساب میشوند.
پاسخ
گزینهی ۴ درست است.
ابتدا روشی ارائه میدهیم که حمید بتواند طول کوتاهترین مسیر را به ۱۴ برساند. اگر حمید به شکل زیر خانهها را پر کند، مسیر ایلیچ یکتا و طول آن ۱۴ است:
حال ثابت میکنیم هر گونه که حمید خانهها را پر کند، مسیری به طول حداکثر ۱۴ برای ایلیچ وجود دارد. اگر طول کوتاهترین مسیر از ۱۴ بیشتر شود، در زیرمستطیل $2 \times 8$ سمت چپ، تعداد خانههای درون مسیر از ۱۲ بیشتر است. پس با افراز این زیرمستطیل به چهار مستطیل $2 \times 2$ طبق اصل لانهی کبوتری، زیرمستطیلی $2 \times 2$ وجود دارد که تمام خانههای آن در مسیر هستند. به وضوح میتوان طول این قسمت از مسیر را دو واحد کاهش داد که با فرض کوتاهترین بودن تناقض دارد.