سوال ۴

گزینه‌ی ۴ درست است.

ابتدا روشی ارائه می‌دهیم که حمید بتواند طول کوتاه‌ترین مسیر را به ۱۴ برساند. اگر حمید به شکل زیر خانه‌ها را پر کند، مسیر ایلیچ یکتا و طول آن ۱۴ است:

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