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