Belián nagybátyja, Buxtuc, afrikai kereskedő. Egyszer elhatározta, hogy 3000 kilónyi datolyáját nem helyben, hanem egy onnan 1000 kilométerre levő másik oázisban fogja értékesíteni, mert közismert, hogy ott a datolya sokkal jobb áron forog.
A szállításhoz egyetlen öreg tevéjét akarta felhasználni, aminek a teherbírása 1000kg, és minden egyes km megtétele előtt elfogyaszt 1 kg datolyát. Sajnálatos, hogy a tevét teljesen felpakolva elér ugyan a másik oázisig, viszont közben az összes áru el is fogy…
Adódik az ötlet, hogy vigyünk el egy darabig valamennyi datolyát, pakoljuk le, majd forduljunk vissza a tevével, és hozzunk egy másik kupacot. Buxtuc, hogy a bevételt tovább növelje, unokaöccséhez Beliánhoz fordult segítségért, hogy számítsa ki azt a stratégiát, amivel a lehető legtöbb datolya átszállítható a sivatagon.
Mit válaszolt Belián a kérdésre?
(Frissítve: a feladat eredetileg 200kg datolyáról, 100km távról és egy 100kg-os teherbírású tevéről szólt. Ezt kijavítottam, mert így valamivel érdekesebb a probléma.)
A válasz 533 datolya. A szállítás három szakaszra bontható:
--> <-- --> A --> P <-- Q --> B <-- --> -->
AP úton három forduló szükséges az összes datolya átszállításához. PQ úton két forduló is elég, végül Q-ból B-be már 1 fordulóval átmehet a teve. Természetesen az is szükséges, hogy az egyes útszakaszok megtételéhez legyen még elegendő datolyánk, ráadásul AP és PQ hossza nem lehet nagyobb mint 500 km, hiszen a teve egy rakománnyal legfeljebb ekkora utat tud oda-vissza megjárni.
Igazából az AP és PQ szakaszokon akárhány köztes rakodó állomást bevezethetünk, ez a végeredményt nem befolyásolja. Csak az a lényeg, hogy előbb minden datolyát szállítsunk el P-be, majd innen az összeset Q-ba.
P-ben legfeljebb 2000 datolya lehet nálunk, ez elérhető, ha az AP ötszöri megtételéhez összesen 1000 datolyát használunk fel. Ebből következik, hogy P 200km-re kell legyen A-tól.
Ugyanezen logika mentén, ahhoz, hogy Q-ban 1000 datolyánk maradjon a PQ távolságnak 333+1/3 km-nek kell lennie.
Innentől Q-ból B-be marad még 466+2/3 km, amihez 467 datolyát emészt fel a tevénk (feltettük ugyanis, hogy a mozgás előtt kell megetetni).
Így B-be 533 datolya szállítható.
Comments are closed.
és hogy jön vissza? vesz 100 kiló datolyát a visszaútra?
mert ha elvisszük a 100 kilót 50 kilométerre, akkor az odaútra kell 50 kiló, a visszaútra is 50.
ha elvisszünk 100 kilót 30 km-re, akkor elfogy 60 kiló datolya de van 40 kiló tőlünk 30 km-re
most a maradék 100 kilót felrakjuk, elmegyünk 30 km-re addig elfogy 30 kiló felvesszünk a 40-ből 30-at és megyünk még 70 km-t, azaz marad a végére 30.
ezz kéne optimalizálni, hogy a 10 se maradjon ott.
azaz, elviszünk 100 kilót 33,3333 km-re, visszamegyünk, elfogy az úton 66,67 kiló.
felvesszük a maradék 100 kilót.
elmegyünk 33,33 km-t, közben elfogy 33,33 kg. de sebaj, mert pont annyit kell felvenni.
tehát most 66,67 km-re vagyunk a piactól és van 100 kg datolyánk.
elmegyünk a piacra és marad 33,33 kg datolya
ebből is látszik, hogy nem könnyű a beduinok élete.
nyilván a 33,33 az (100/3) és a 66,67 az (200/3), csak így egyszerűbb volt.
Eredetileg a feladat 3000kg datolyáról és 1000km távolságról szólt. Mi a helyzet abban az esetben? És általánosan?
Azt is meg kéne mutatni, hogy a tiédnél jobb megoldás nem lehetséges.
@encse: de ha korábban pakolunk le, mint [egyharmad táv], akkor nem tudjuk a következő fordulóban magunkkal vinni az összes cuccot (lásd fenn).
[féltáv]-nál távolabb nem mehetünk lepakolni, mert akkor nem tudunk visszamenni.
tehát a megoldás [egyharmad táv] és [féltáv] között van. ha pedig közötte vagyunk, legyen mondjuk 40 km, akkor 20 kg ottmarad, 80 kg elfogy az úton, felvesszük a 100 kg-ot, elmegyünk 40 km-re, marad 60 kg, hozzátesszük a 20-at, az 80 kg, és hátravan 60km, azaz marad 20 kg.
ez pedig kevesebb, mint 33,3
tehát az optimum [egyharmadtáv]-nál van
lehetne egyenletezni, de minek.
nyilván a megtett út kétszeresével arányosan fogy a datolya, ha visszafordulunk. márpedig visszafordulás nélkül nem oldható meg.
tehát úgy kell visszafordulni, hogy második menetben a lehető legtöbb datolya legyen nálunk.
Ha jól értem, ez ugyanaz a feladat, mint amikor van két százemeletes toronyház, és nekünk kell kitalálnunk, hogy hányadik emeleten legyen a két épületet összekötő folyosó ahhoz, hogy a legtávolabbi pontokról se kelljen túl sokat menni.
Értelemszerűen nem az 50. emeletre rakjuk (hiszen akkor lesz, akinek 49 emeletet kell utaznia, hogy átmehessen a másik házba), hanem a 67. szintre, hiszen így a maximum gyaloglás 33 szintnyire csökken. (lévén az alsó 33 szintről már közelebb van lemenni az utcára és úgy átmenni a másik házba, mint felmenni a 67.-en lévő folyosóhoz.)
Na, ezt most jól elmondtam, kisssé off.
@terasz9: ezt most nem teljesen értem. CSAK az a cél, hogy egyik épületből átjussunk a másik épületbe?
mert úgy értem.
Na tessék szépen nekilátni a sajtóhibáktól megfosztott feladatnak még 1x… 🙂 A hibás feladat megfejtéésért azért jár a pont.
Szerintem 2 db datolyálya marad mire célbaér.
Én is harmadolással számoltam, azaz először 1000 kg-ot visz 333 km-re így oda-vissza úton elfogy 666, vagyis le tud tenni az első ponton 334-et. Ezt megismétli, így a második kör után már 668 van az első ponton. A harmadik kör után az első ponton 1000-333=667 + 668 = 1335 datolyálya van.
Ebből 1000-et felvéve és újabb 333 km-t megtéve a második ponton le tud tenni 334-et. ( Itt is az oda-vissza úton 666 szükséges). A második körre az első és második pont között csak 335 maradt az első pontnál, így azt felvéve mire a második pontra ér 333 km után marad 2 datolya.
A második ponton az ott lévő 334-et felvéve lesz összesen 336, a célig hátralévő 334 km-en elfogyaszt belőle 334-et, tehát marad összesen 2 datolyája eladni.
Nem egy jó üzlet… ráadásul a visszaútra sem marad semmi.
Ennél jóval több a helyes megoldás.
Első lépésben negyedútig vive félrakománnyit, majd egy következő úttal a depót a félútra áttelepítve – végül az utolsó úttal 500kg datolya átvihető a másik oázisba.
Ha megnézed, közben feltettem a megoldást 533 datolyával.