En Jeep kan sammanlagt ta 200 liter bensin i tanken och i lösa dunkar. Jeepen kommer 2,5 km på 1 liter bensin.
Anta att du ska färdas 1000 km in i öknen och att bränsle bara finns vid startpunkten och vid målet. Vill du klara färden måste du först placera ut bensin i depåer längs färdvägen. Hur mycket bränsle går det åt och vart ska dunkarna placeras ut? Hitta en lösning som är "så bra som möjligt", dvs att det går så lite bensin som möjligt.
Depåerna måste placeras ut med Jeepen, inte med nåt annat fordon. Kan du lösa detta problem?
eeeh... IQ-fiskpinne nekar sin egen existens.. till vilken nytta placera ut depåerna med jeepen om han ändå ska färda den där sträckan? SOm jag sa... IQ-fiskpinne! :e
eeeh... IQ-fiskpinne nekar sin egen existens.. till vilken nytta placera ut depåerna med jeepen om han ändå ska färda den där sträckan? SOm jag sa... IQ-fiskpinne! :e
Det är klart att depåerna behövs. För Jeepen kommer ju bara halva vägen, dvs 500 km på de 200 literna som den har i sig från början. Det gäller att klura ut hur man ska disponera depåerna för att bensinen ska räcka ändra fram och helst ska det gå så lite som möjligt.
Kom igen nu! Nåt geni finns det väl bland oss eller ska vi tappa tilltron till världen totalt???
Antag för enkelhets skull att jeepen rymmer 1 volymsenhet bensin och att jeepen kan köra 1 längdenhet på 1 volymsenhet bensin. I detta fall är alltså en volymsenhet 200 liter och en längdenhet 500 km. Vi börjar med att ställa frågan: Hur långt kommer jeepen om det finns F volymsenheter i lager vid utgångspunkten för resan. Om F är ett heltal f är svaret
1 + 1/3 + 1/5 + ... + 1/(2f - 1)
längdenheter. Om F inte är ett heltal kan vi skriva F = f + d där f är ett heltal och 0 < d < 1 och i så fall blir sträckan
1 + 1/3 + 1/5 + ... + 1/(2f - 1) + d/(2f + 1).
Vi visar att jeepen verkligen kan komma så långt då F = f är ett heltal med induktion över f. Då f = 1 är det självklart. Antag nu att påståendet är visat för f och att det finns f + 1 v.e. i lager. Välj ut en punkt P 1/(2f + 1) l.e. från start S. Jeepen tankar fullt och kör sträckan från S till P och tillbaka till S. Detta görs f gånger. Varje gång deponeras 1 - 2/(2f + 1) v.e. vid P (resten går åt för resan). Totalt deponeras f(1 - 2/(2f + 1)) v.e. Sista resan från S till P är enkel och när jeepen är framme vid P har den 1 - 1/(2f + 1) v.e. i tanken. Totalt i depån och tanken finns alltså f(1 - 2/(2f + 1)) + 1 - 1/(2f + 1) = f v.e. Enligt induktionsantagandet kommer jeepen 1 + 1/3 + 1/5 + ... + 1/(2f - 1) l.e. på dessa f v.e. och har alltså redan tillryggalagt 1/(2f + 1) l.e. Den totala sträckan på f + 1 v.e. bensin blir alltså
1 + 1/3 + 1/5 + ... + 1/(2f - 1) + 1/(2(f + 1) - 1).
Jag avstår från att visa att detta är den optimala lösningen. För ett bevis, se t ex Niven: Maxima and Minima Without Calculus.
I fallet att F inte är ett heltal skall den första depån placeras d/(2f + 1) l.e. från S.
Vi antar nu för enkelhets skull att F = f är ett heltal. Genom att räkna litet ser vi att
1 + 1/3 + 1/5 + ... + 1/13 < 2 < 1 + 1/3 + 1/5 + ... + 1/13 + 1/15.
Det måste alltså finnas f = 8 v.e. = 1600 l vid start. Den första depån skall placeras 500/15 km från start, den andra efter ytterligare 500/13 km, den tredje efter ytterligare 500/11 km osv.
Antag för enkelhets skull att jeepen rymmer 1 volymsenhet bensin och att jeepen kan köra 1 längdenhet på 1 volymsenhet bensin. I detta fall är alltså en volymsenhet 200 liter och en längdenhet 500 km. Vi börjar med att ställa frågan: Hur långt kommer jeepen om det finns F volymsenheter i lager vid utgångspunkten för resan. Om F är ett heltal f är svaret
1 + 1/3 + 1/5 + ... + 1/(2f - 1)
längdenheter. Om F inte är ett heltal kan vi skriva F = f + d där f är ett heltal och 0 < d < 1 och i så fall blir sträckan
1 + 1/3 + 1/5 + ... + 1/(2f - 1) + d/(2f + 1).
Vi visar att jeepen verkligen kan komma så långt då F = f är ett heltal med induktion över f. Då f = 1 är det självklart. Antag nu att påståendet är visat för f och att det finns f + 1 v.e. i lager. Välj ut en punkt P 1/(2f + 1) l.e. från start S. Jeepen tankar fullt och kör sträckan från S till P och tillbaka till S. Detta görs f gånger. Varje gång deponeras 1 - 2/(2f + 1) v.e. vid P (resten går åt för resan). Totalt deponeras f(1 - 2/(2f + 1)) v.e. Sista resan från S till P är enkel och när jeepen är framme vid P har den 1 - 1/(2f + 1) v.e. i tanken. Totalt i depån och tanken finns alltså f(1 - 2/(2f + 1)) + 1 - 1/(2f + 1) = f v.e. Enligt induktionsantagandet kommer jeepen 1 + 1/3 + 1/5 + ... + 1/(2f - 1) l.e. på dessa f v.e. och har alltså redan tillryggalagt 1/(2f + 1) l.e. Den totala sträckan på f + 1 v.e. bensin blir alltså
1 + 1/3 + 1/5 + ... + 1/(2f - 1) + 1/(2(f + 1) - 1).
Jag avstår från att visa att detta är den optimala lösningen. För ett bevis, se t ex Niven: Maxima and Minima Without Calculus.
I fallet att F inte är ett heltal skall den första depån placeras d/(2f + 1) l.e. från S.
Vi antar nu för enkelhets skull att F = f är ett heltal. Genom att räkna litet ser vi att
1 + 1/3 + 1/5 + ... + 1/13 < 2 < 1 + 1/3 + 1/5 + ... + 1/13 + 1/15.
Det måste alltså finnas f = 8 v.e. = 1600 l vid start. Den första depån skall placeras 500/15 km från start, den andra efter ytterligare 500/13 km, den tredje efter ytterligare 500/11 km osv.
Alltså hur orkar man... :o
257 ms totalt · 4 externa anrop · v20260731065814-full.86ec41c2
