سوال ۳۶

برای انتقال یک لیتر بنزین به مخزن شهر مجاور دو لیتر بنزین هدر می‌رود ( یک لیتر برای رفت و یک لیتر برای برگشت). برای انتقال یک لیتر بنزین به مخزن شهری که با شهر مبدا دو واحد فاصله دارد ۸ لیتر بنزین هدر می‌رود٬ زیرا اگر شهر مبدا در شکل مقابل شهر $A$ و شهر مقصد شهر $C$ باشد٬ فاصله بین شهر $A$ و $B$ سه بار و فاصله‌ی بین $B$ تا $C$ یک بار به صورت رفت و برگشت طی می‌شود تا از شهر $A$ به شهر $C$ یک لیتر بنزین منتقل شود.

به همین ترتیب ثابت می‌شود که برای انتقال یک لیتر بنزین به مخزن شهری که با شهر مبدا سه واحد فاصله دارد ۲۶ لیتر بنزین هدر می‌رود. با این توضیحات معلوم می‌شودکه بهترین شهر برای مبدا شهر $A$ می‌باشد که در این صورت برای انتقال یک لیتر بنزین به شهر‌های $F، E ، D ، C ، B$ و $G$ به ترتیب ۸٬۸٬۸٬۲٬۲ و ۲ لیتر بنزین هدر می‌رود که با بنزین‌های موجود در مخازن که باید حداقل یک لیتر در هر مخزن باشد مجموعا ۳۷ لیتر می‌شود که از ۳۰ لیتر بیش‌تر است.