یک مربع $۱۰۰×۱۰۰$ را بهصورت شطرنجی رنگ کردهایم. شخصی در گوشهی بالا و سمت چپ این مربع که خانهای سفید است ایستاده است. این شخص میخواهد با حرکت در این مربع از هرکدام از خانهها حداقل یکبار ایستاده باشد. هزینهی رفتوآمد برای حرکت او به این صورت است:
• از هر خانه به هرکدام خانههای مجاور (حداکثر ۴ خانه )، ۱ تومان.
• از هر خانهی سیاه به هر خانهی سیاه دیگر، رایگان است.
حرکت بهغیراز دو صورت گفتهشده در بالا ممکن نیست. حداقل هزینهای که این شخص باید بپردازد چه قدر است؟
پاسخ
اولا باید توجه داشت که برای ورود و خروج هر مربع سفیدی مجموعا ۲تومان هزینه میشود و ثانیا به غیر از خانههای اول و آخر٬ ورود و خروج لازم دارند. واضع است که خانه اول ورود ندارد و نیز میتوان حرکات آخر را چنان چید(مطابق شکل)که آخرین خانه سفید باشد و خروجی لازم نداشته باشد که در این صورت هزینه انجام شده برابر $(5000\times2)-2$ یعنی ۹۹۹۸ خواهد شد.