Muz taşımacılığı (Çözüm)

Bu soru için sezgisel bir çözüm vereceğim ve bu çözümün en iyi sonucu verdiğini başka bir yazıya bırakacağım. 

Eğer deve 1000 adet muzu sırtlanıp bütün yolu geçmeye çalışırsa B şehrine geldiğinde hiç muz kalmamış olacaktır, çünkü 1000 km için 1000 adet muz yemesi gerekecek. Ayrıca A şehrinde kalan 2000 muzu almak için de geri dönemeyecek. 

Demek ki A şehrinden B şehrine doğrudan değil etaplar halinde gidilecek. Her etapta belli miktarda muz ara hedefe iletilecek. İlk etaplarda deve geri dönüp taşıyamadığı muzları geri alması gerekeceğinden bu mesafeler birden fazla sefer gidilecek ama son etapta devenin geri dönmesine gerek olmayacaktır. Yani deve son etabın başlangıç noktasında 1000 muz biriktirirse bir daha geri dönmeye gerek olmadan bu muzlar bir kerede hedefe taşınabilir. 

İlk etapta 3000 muzu taşımak için üç kere 1000 adet muzla yola çıkılacak ve iki defa da geri dönülecek. Yani ilk etabın mesafesine $x$ km dersek, deve bu mesafeyi beş kere gidecek ve bu sırada $5x$ adet muz yiyecek. İkinci etabın başlangıcında eğer 2000'den fazla muz birikmişse bu etapta ya yine beş sefer yapılacak ya da fazlalık muzlar burada bırakılmak şeklinde ziyan edilecek. Eğer 2000 muz biriktirilmişse ikinci etapta sadece üç sefer yapmak gerekecek, 1000 muz ileri, geri ve kalan 1000 muz ile tekrar ileri. 

İkinci etap başında 2000 muz kalması için ilk etabın 

$3000 - 5x = 2000 \implies x = \frac {1000}{5} = 200$ km olması lazım.

İkinci etapta üç sefer yapılacak ve aynı mantık kullanılacak. Yani son etap için 1000 muz kalacak şekilde mesafe seçeceğiz. Bu etabın mesafesine de $y$ dersek

$2000 - 3y = 1000 \implies y = \frac {1000}{3} = 333 \frac {1}{3}$ km

Deve kesirli muzlarla yürümediğinden tamsayılı bir çözüm kullanacağız ve sadece 333 km gideceğiz. Bu noktada son etaba başlamadan önce 1001 adet muz kalmış olacak. Deve sadece 1000 muz taşıyabildiğinden son etap için artan muzu bırakıp kalan mesafeyi, yani $1000 - (200 + 333) = 1000 - 533 = 467$ km'yi gidersek B şehrine $1000 - 467 = 533$ muz ulaştırabiliriz. Peki daha iyi bir sonuca ulaşabilir miyiz? Örneğin son etap başında artan bir muzu kurtarmanın yolu var mı? Sorunun soruluşuna dikkat edersek gerçekten de var. Deve yola her kilometreden önce muzu yiyor ve 1000 adet muz taşıyabiliyor. Bu durumda son etaptan önce 1001. muzu yiyerek kalan 1000 muzu bir kilometre daha ileri götürebiliriz. Böylece son etaba 533. km'de değil de 534. km'de başlayabiliriz ve bu da son etap mesafesi $1000 - 534 = 466$ km olacak demektir. Bu şekilde de B şehrine $1000 - 466 = 534$ muz ile ulaşabiliriz. 

Not: Eğer üç gidiş gelişli ara etap olmayan bir çözüm ararsak elde edeceğimiz sonuç beş gidiş gelişli bir etap ve tek gidişli bir ikinci etap çözümüne eşdeğer olacaktır. Bundan da

$3000 - 5x = 1000 \implies x = 400$ km ilk etap mesafesi bulunur. Yani kalan 1000 muz ile son 600 km gidilecektir ve geriye de sadece $1000 - 600 = 400$ muz kalacaktır. Bu da yukarıda bulduğumuz çözümden daha kötü bir cevaptır.