Posted By: Hozik (Hozik) on 'CZriddles'
Title:     Re: snakova vyzva:-)
Date:      Mon Dec  8 10:54:39 1997

> 3) Zlaty hreb! Vypada to lehce, ale Lumiku, uskvaris se na tom:-))))):
> Velbloudi problem (pochazi z MFF, nedopidil jsem se vyreseni:-( )
> 
> snake
> 

No ja nejsem zadny velky matematik (viz i me pokusy o zrovnopravneni 
racionalnich a iracionalnich cisel :) ), ale pripada mi, ze reseni je 
takoveto:
                
            d = v     pro v sude,
            d = v-1   pro v liche.

d ... pocet dnu, po ktere muze karavana jit
v ... pocet velbloudu v karavane

Oduvodneni:
pozn. je to spis postup, jak jsem uvazoval, nikoli dukaz  :(

1) Kazdy velbloud se oznaci cislem. Karavana pro jeden den tak predstavuje 
cislo o v cifrach (napr. 123456). Tohle cislo lze rozlozit na usporadane 
dvojice (1,2  2,3  3,4  4,5  5,6). Pokud mam v velbloudu, tak muzu z nich 
vytvorit maximalne v * (v-1) usporadanych dvojic. Pro vytvoreni karavany 
potrebuju v-1 usporadanych dvojic.
2) Mam-li vytvorenou prvni karavanu, tak muzu hned vytvorit druhou: na prvni 
jsem pouzil v-1 usporadanych dvojic a na tu druhou pouziju v-1 INVERSNICH 
usporadanych dvojic! (inversni myslim: 1,2  ->  2,1 atd. ... mozna se tomu 
rika jinak). Tak napr. z karavany 123456 pro jeden den mohu udelat karavanu 
654321 pro druhy den ... velbloudi udelaji celem vzad.
Kdyz jsem vytvoril tyhle dve karavany, tak vim, ze v jeste nepouzitejch 
dvojich jsou od kazde inversni i neinversni. Vzhledem k tomu, jak mohu 
tvorit karavanu, muzu vzdy pouzit dvojice jen z jedne mnoziny (napr. jen 
neinversni). Proto pro vytvoreni karavany potrebuju mit v-1 nepouzitych 
neinversnich dvojic. Kdyz jich mam min, tak uz nemuzu karavanu vytvorit.
3) Na zacatku mam v * (v-1) dvojic, zadna neni pouzita. Z nich je v * (v-1)/2 
neinersnich (jednoho druhu). Pouze z nich mohu vytvaret karavany. Protoze na 
jednu potrebuju (v-1) dvojic, mohu vytvorit v * (v-1)/2 * 1/(v-1) karavan, 
tj. v/2 karavan. Ke kazde takto vytvorene karavane udelam dalsi tim, ze 
velbloudi udelaji celem vzad. Pak mam v karavan.
Ale: tohle plati jen pro v sude. Pak bude v/2 cele cislo. Proto pro sude v 
plati d = v.
Pokud je v liche, tak by v/2 bylo xxx.5, coz nelze ... nemuzu vytvorit pulku 
karavany. Proto muzu v tomhle pripade vytvorit jen v/2 - 0.5 karavan. K tem 
udelam karavany inversni a je to v-1 karavan. Proto pro liche v 
plati d = v - 1.

Nazorny priklad:
v=6
pocet dvojic ... 6 * 5 = 30

30/2 je vetsi jak 5 (tolik potrebuju), a proto pouziji 5 dvojic -> mam jich 
ted 30 - 5 = 25 ... ale mam karavanu pro prvni den.
Nyni tvorim karavanu inversni: 25 - 5 = 20 volnych dvojic ... ale mam karavanu 
pro druhy den (nemusim uz delit dvema, protoze pouziji dvojice inversni k 
tem, ktere jsem pouzil pro prvni den).
20/2 = 10     to je > 5   ... 20 - 5 = 15      treti den
15 - 5 = 10      ctvrty den
10/2 = 5   to je = 5   .... 10 - 5 = 5   paty den
5 - 5 = 0     sesty den
.... nyni uz nenam zadne dvojice


v=7
Obdobne muzu dojit do stavu, kdy mam volnych 18 dvojic a prave jsem vytvoril 
inversni karavanu.
18/2 = 9   to je > 6   ... 18 - 6 = 12   paty den
12 - 6 = 6     sesty den
Ted mam 6 volnych dvojic, z nich jsou ale 3 inversni a 3 neinversni ... proto 
uz nemuzu delat dalsi karavanu.
6/2 = 3   to je < 6    .... :-(

Proc to neni dukaz:
Jsem si jistej, ze ted me mnozi proklinate, ze tohle neni zadnej dukaz. 
Souhlasim, myslim si vsak, ze reseni je spravne. Overoval jsem to na pocitaci 
pro ruzna cisla a odpovidalo mi to (programek muzu na pozadani poslat). 
Jiste, ani tohle neni dukaz, ale je to verifikace hypotezy. Vy jste 
matematici, a tak ji zkuste vyvrati. Ja vidim nedstatek meho postupu ve dvou 
bodech:
1) Neni dokazano, ze pokud mam napr. 30 dvojic, ze z nich muzu vzdy udelat 6 
karavan ... ze na sebe budou cisla navazovat. Jak jsem to zkousel, tak to 
vzdycky jde, jen je nutne mit spravne kombinace. Jak tvorim jednotlive 
karavany, tak se muzu dostat na zcesti. Kdyz se ale vratim a neco predelam, 
tak se dostanu dale. (napr. jedno cislo nesmi nikdy byt na zacatku ci 
konci vice jak dvakrat). Vytvorit ty kombinace vsechny je nekdy zapeklity 
orisek, ale jde rozlousknout. Obecne je mozne radit: pokud se nekdy dostanete 
do obdobne situace, tak si poridte lichy pocet velbloudu. Onen maximalni 
pocet karavan se sestavuje mnohem lepe.
2) Neni dokazano, ze kdyz mam liche cislo, tak nelze vytvorit v velbloudu 
jinou kombinaci nez jak jsem uvedl: neinversni karavana, inversni, .... .
Zkousel jsem pro ruzna licha cisla, zda se, ze to nejde ... vzdy napr. 
posledni dvojice nehraje.

Pokud jsem svymi pohanskymi postupy urazil Vas matematicky jemnocit, tak se 
omlouvam.

S pozdravem 

Hozik