Jeep in de woestijn

[Verwijderd]

Een tijdje geleden was hier een topic over een Wiskunde Olympiade (Wiskunde Olympiade!!! ). Na overleg met Captain Proton open ik nu een nieuw topic.

Nu hebben we hetzelfde probleem gekregen bij Wiskunde, maar dan als Praktische Opdracht, en daardoor ben ik intensief bezig met dit probleem. Mede door dat topic ben ik het probleem gaan begrijpen, maar ik zit nog met een paar vragen. Laat ik eerst eens opschrijven wat ik heb.

Het probleem

Een jeep heeft een tank van 100 L en rijdt door de woestijn. Onderweg mag hij uit zijn tank benzine halen en die als depot in de woestijn neerzetten. Hij moet wel genoeg benzine overhouden om terug te rijden. Helemaal aan het begin is een onuitputtelijke bron benzine.

Borganism plaatste volgens mij de beste oplossing voor 1600 km.

Verwijderd schreef op 23 november 2001 @ 11:47:
Ik kom op 346 2/3 en dit volgens mij het goede antwoord
poging tot uitleg: voor de laatste 1000km heb 100 liter nodig dus op 600 km moet er 100 liter aanwezig zijn om die 100 liter daar te krijgen moet een keer extra heen en weer rijden vanuit een punt waar 200 liter is. Dat punt ligt op 600 - ((10*100)/3) = 266 2/3 km om op dat punt 200 liter te hebben moet van een ander waar 300 liter is gehaald worden. Dat punt ligt op 266 2/3 -((10*100)/5) = 66 2/3 km. Om de benzine daar vanaf het begin punt te krijgen kost 7* 1/10 * 66 2/3 liter = 46 2/3 + de 300 = 346 2/3 liter.

Naar aanleiding van zijn post heb ik het volgende programma geschreven voor de Ti-83:

Programma


Dit programma kan vast een stuk fraaier, maar zo werkt hij in ieder geval voor afstanden van 1600 km en meer.


Maar nu zit ik nog met een paar probleempjes om alles te bewijzen.

Q - ( 1000 / D ) --> E
voor de laatste 1000km heb 100 liter nodig dus op Q moet er 100 liter aanwezig zijn om die 100 liter daar te krijgen moet een keer extra heen en weer rijden vanuit een punt waar 200 liter is.

Dat punt ligt op Q - ((10*100)/3) = U km

Is dit een bewijs waardig? Volgens mij niet, want ik kan niet echt aantonen dat je een extra keer heen en weer moet rijden vanuit een punt waar 200 liter is. En wat ik nog veel vager vindt is dat je 1000 moet delen door het aantal keer heen of weer rijden om de plaats van het volgende depot te berekenen.

Verwijderd schreef op 23 November 2001 @ 12:47:
[...]


het is vrij simpel je zorgt dat je op het laatste depot die op 1 tank afstand van het eind 1 tank vol hebt.
Op het een na laatste die op 1/3 tank van de laatste ligt zorg je dat je daar 2 tanks vol hebt.
Op de twee na laatste die op 1/5 tank ligt van de ene laatste zorg dat je 3 tanks vol hebt enz.
Ik heb geen bewijs maar ben er 99% zeker van.
(Dit is mijn grote probleem met wiskunde, ik weet het antwoordt wel maar niet waarom )

dat is inderdaad het probleem. Waarom op 1/3 , 1/5 van een tank enzo.

Ik hoop dat iemand mij nog wijzer kan maken in dit probleem, het antwoord enzo heb ik wel al, maar een goed bewijs ontbreekt nog.


Waarom 1/3 van een tank , 1/5 , 1/7 enzovoorts, en vooral waarom deel je 1000 door 3,5,7,9,11 enzovoorts. 1000 is wat je op 1 tank kunt rijden, maar waarom deel je dat door het aantal keer dat je heen of weer rijdt?

[Verwijderd]

edit:
Als je niks te melden hebt, post dan niet Dit is de HK niet...

[ Voor 87% gewijzigd door Verwijderd op 28-02-2003 13:33 ]

[Verwijderd]

Is het nou wel de bedoeling dat als 'ie aan de overkant is (1600 km), ook weer helemaal terug moet, of niet? Dit kon ik niet echt duidelijk opmaken uit je omschrijving.

[p_m]

Hij hoeft niet terug.

[Verwijderd]

Nee hij hoeft niet terug als hij er is nee.
Ik ben ondertussen weer wat verder. Ik snap hem nu eigenlijk helemaal, alleen moet ik het nog goed opschrijven, dus als ik m helemaal af heb laat ik weer van me horen

[p_m]

Ik heb die ook gemaakt als PO, mail me maar als je 'm wilt hebben.

[Verwijderd]

Voor een willekeurige afteleggen afstand geldt dus (zoals al opgemerkt):

De eerste (of eigenlijk de laatste) 1000(/1) km kosten 1 liter per 10 km.
De volgende 1000/3 = 333 km kosten 3 liter per 10 km.
De daarna volgende 1000/5 km = 200 km kosten 5 liter per 10 km.
En zo verder. Dus:
Op het n-de stuk van 1000/(2n-1) km kost 10km rijden 2n-1 liter.

Voor 1600 km is dat dus 100 liter voor de laatste 1000 km + 100 liter voor de 333.3 km daarvoor + 100 liter voor 200 km daarvoor + 66.6*7/10 = 46.6 liter voor de laatste 1600-1000-333.3-200= 66.6 km.
=
346.6 liter.

Hoe is dit te begrijpen?
Voor mij werd het probleem makelijker als je uit ging van depots elke 10 km. (of nog flauwer een volledig continu depot).
Twee dingen zijn duidelijk:
- je wil zo veel mogelijk van je brandstof zo dicht mogelijk bij je beginpunt opslaan
- het laatste depot mag maximaal 1000 km van het eindpunt liggen.
- als de afstand groter is 1000km zijn er stukken die je vaker dan 1 keer moet afleggen.

We gaan de afstand nu in delen in stukken aan de hand van de aantal keer dat ze afgelegd moeten worden. De stukken gaan we nummer met 1 = het laatste stuk, 2 het stuk daarvoor, etc.
Het is duidelijk dat het laatste stuk (1) maar een keer hoeft te worden af gelegd.
Het stuk daarvoor (2) moet echter drie keer worden afgelegd: 1 keer in de laatste rit en een keer op en neer om depots aan te leggen.
Het stuk daarvoor (3) zal vijf keer bezocht worden: 1x in de laatste rit+ 2x om de depots in (2) aan te leggen + 2x om de depots in (3) aan te leggen.
Over het algemeen zal gelden dat het n-de stuk 1+2(n-1)=2n-1 keer afgelegd moet worden.
Nu gaan we de maximale lengte van het n-de stuk uit rekenen. Voor de minimale oplossing geldt dat er een maximale hoeveelheid brandstof zo vroeg mogelijk opgeslagen staat. De depots moet dus zo aangelegd worden dat bij de eerste passage van een stuk genoeg brandstof wordt achtergelaten voor alle volgende keer dat het stuk gepasseerd wordt. De eerste passage van een stuk kost dus (2n-1)/10 keer de lengte van het stuk aan benzine. Alle volgende keren kost het passeren niks meer. Dit brengt de maximale lengte van een stuk dus op 100/((2n-1)/10)=1000/(2n-1) km.
En hiermee zijn we dus op de oplossing.

Merk overigen op dat op deze manier een willekeurig grote afstand afgelegd kan worden. De reeks: sum[1000/(2n-1),{n,1,inf}] is namelijk divergent.

(want sum[1000/(2n-1),{n,1,inf}] < sum[1000/(2n),{n,1,inf}] = 500 sum[1/n,{n,1,inf}] en sum[1/n,{n,1,inf}] is divergent.

[Verwijderd]

Jongens, bedankt
Ondertussen had ik het zelf al een beetje uitgevogeld, met waarom 1,3,5 enzo, en volgens mij kan ik het nu op papier zetten zodat het ook echt een bewijs is, niet alleen vermoedens

Thnx

[ Voor 1% gewijzigd door Verwijderd op 01-03-2003 16:10 . Reden: tiepvout ]

[p_m]

graag gedaan

(is het nog gelukt met dat PDF'je?)

[Verwijderd]

Ja, nog bedankt

Morgen moet ie af zijn geloof ik, dus dan post ik mijn resultaat ook nog wel ff, dus gewoon wat ik ervan heb gebakken