Ze zadani ulohy si nejsem jist, jak velbloud ji banany. Muze to mit urcity (byt nepatrny) vliv na vysledek. Napadaji me tri moznosti. a) Nejhorsi pripad: velbloud sni banan cestou, takze ho musim pocitat do tech 1000, ktere unese. b) Pocet bananu neni prirozene cislo, nybrz realne, takze velbloud zere banany spojite (coz je matematizace skutecnosti, ze mu davam banany po malych kouscich v prubehu mile) c) Nejlepsi pripad: ten banan mu dam na zacatku te mile, takze uveze jeste 1000 dalsich. Ja budu ulohu resit za predpokladu ,,a'', protoze imho nejlepe vystihuje skutecnost, ze velbloud zbasti banan BEHEM te mile. A ted reseni. Z pocatecniho stavu ,,3000 bananu 1000 mil od trziste'' lze prejit do stavu ,,2997 bananu 999 mil od trziste'' a tak dale, tedy 3000-3n bananu 999-n mil od trziste. Az dojdu do stavu ,,2001'' bananu 667 mil od trziste. ,,1998'' bananu 666 mil od trziste, nyni budu odcitat jen dva banany. Ujdedu tedy dalsich 499 mil (pricemz se napriklad kazdou mili vracim, abych mel banany pohromade) a mam: ,,1000'' bananu 167 mil od trziste. A nyni jiz snadno dostanu do trznice 833 bananu. Ted udelam takovou malou kontrolu spravnosti: provedu vypocet za predpokladu ,,b'', a bude mnohem jednodussi, a vyjde skoro stejne: Nejdriv kazda mile stoji 3 banany, s tim ujdu presne tretinu cesty (tj. jsem 666+2/3 mil od trznice) Pak mam 2000 bananu, kazda mile stoji 2 banany, s tim ujdu polovinu cesty. Jsem sestinu cesty od cile, kazda mile stoji 1 banan, cili ztratim 1000/6 bananu, zbyde mi jich 5/6 z 1000, to je o tretinu vic, nez v pripade ad a. Diky tomu verim, ze jsem se (v ad a) neprepocital. Dukaz : Za prve je intuitivne zrejme, ze bez ujmy na obecnosti muzeme predpokladat, ze se velbloud pohybuje na usecce mezi trzistem a vychozim skladistem bananu. Je snadne to dokazat exaktne. Poloha x bude znamenat, ze jsme x mil od trziste. Dale budu predpoladat, ze pocatek i cil kazdeho transportu bananu bude v celociselne vzdalenosti od trziste. K tomu mi opravnuje i zneni zadani, ktere nijak nenaznacuje, ze by velbloud mohl zastavit i jinde. (Viz poznamku 1) Necht je tedy R libovolne reseni, tedy rozumna posloupnost transferu bananu. (Rozumna = splnujici vyse uvedene pozadavky a neodvazejici z daneho mista vic bananu, nez kolik jich tam je.) Rozdeleni transferu ========= ========= S nim ekvivalentni (co do privezeneho i sezraneho poctu bananu) je reseni R1, ktere vznikne z R tak, ze kazdy transfer nahradime posloupnosti transferu o jednu mili. Poznamka 1: Kdyby se Vam nelibilo, ze nedovoluji velbloudum zastavovat mimo cela cisla, tak ono by se to dokazovalo stejne, akorat zde bychom transfer rozdelili prave ve vsech celociselnych bodech. Je tu ovsem vazna otazka, kolik by behem takoveho transferu velbloud zkonzumoval bananu - v celem tomto mailu totiz uvazuju variantu, kterou jsem ve svem reseni oznacil ,,a''. Konec poznamky. Zmena poradi ===== ====== Dale: Oznacme R2 reseni, ktere vznine z R1 zmenou poradi transferu: Nejprve provedeme vsechny transfery z 1000 do 999, potom vsechny transfery z 999 do 998 atd. Je zrejme, ze tato zmena nezpusobi ujmu na smysluplnosti (proveditelnosti) transferu, a ze je ekvivalentni (co do bananu kokncicich na trznici, resp. v zaludku velblouda) s R1 a tedy i R. Zefektivneni transferu =========== ========= Oznacme nyni R3 reseni, ktere vznikne z R2 tim, ze pro kazde prirozene n<1000 se budeme snazit vyridit transfery z n+1 do n co mozna nejmensim poctem nakladu, tedy budeme banany vozit po tisicich, (pripadne krome posledniho z transferu mezi n+1 a n). Nedopravene banany =========== ====== Je sice intuitivne zrejme, ze v optimalnim reseni nezustanou zadne banany nedopravene (presneji receno, mohli by zustat v nekterych optimalnich resenich, ale podstatne je, ze omezime-li se na reseni, ve kterych vsechny banany dopravime, neovlivni toto omezeni nejlepsi mozny pocet dopravenych bananu). Ale jednak by se to mozna spatne doazovalo (a u podobnych, treba jen nepatrne tezsich uloh, by to ani nemusela byt pravda), a krome toho to nebudu potrebovat. V resenich R, R1 i R2 tedy pripoustime moznost, ze nektere banany zustanou na ceste. A i pro ta reseni R2, kde tyto banany nezustanou, definujme R3 tak, ze pokud prechodem od R2 k R3 uchranime nejaky banan pred hladovou velbloudi tlamou, tak ho tam nechame lezet. Pocet bananu odvezenych z n+1 do n je tedy roven poctu bananu odvezenych v R2. Pocet bananu privezenych z n+1 do n muze byt vetsi o nesezrane banany. To ma vyznam jen pro n=0, kdy toho do trziste privezeme vic. Reseni R3 je tedy neostre lepsi, nez R2 a tedy i nez R. Srovnani R3 s mym resenim ======== == = === ======= Oznacme moje reseni S. Indukci pres prirozene cislo k (nula az 999) lze ukazat, ze pocet bananu odvezenych z 1000-k do 999-k je v reseni S vetsi nebo stejny jako v reseni R3. Pro k=0: v reseni R3 se z vychoziho mista odveze nejvys vsechno (obecne ale ne vsechno), v reseni S vsechno. (Opet nevim, zda mam do odvezenych bananu pocitat ty, na kterych si pochutnal velbloud, ale to neni podstatne.) A plati-li tvrzeni pro k, potom v reseni S bude do 999-k privezeno nejvetsi mozne mnozstvi bananu pri danem poctu bananu v 1000-k, tedy tvrzeni plati i pro k+1. Indukci dokazane tvrzeni tedy plati pro kazde k<1000. Z toho, ze plati pro k=999, dostavame, ze reseni R3 je neostre horsi, nez S. Je ovsem neostre lepsi, nez R. Jelikoz tuto uvahu lze udelat pro kazde reseni R, je S optimalni reseni.